Concept
단방향에서 Insertion, Deletion 이 발생하는 First in last out 자료구조
Time Complexity
Worst Case
Access : 스택의 바닥에 있는 값까지 n번 움직여야 함 - O(n)
Search : 값이 스택의 가장 바닥에 있을 때 n번 움직여야 함 - O(n)
Insertion : 바로 push 가능 - O(1)
Deletion : 바로 pop 가능 - O(1)
Average Case
Access : Theta(n)
Search : Theta(n)
Insertion : Theta(1)
Deletion : Theta(1)
Space Complexity
Worst Case
n개의 데이터를 저장할 노드가 n개만큼 필요함 - O(n)
Example
#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
struct _node *next;
int value;
} Node;
typedef struct _stack {
Node *top;
} Stack;
Stack *newStack() {
Stack *stack = (Stack *) malloc(sizeof(Stack));
stack->top = NULL;
return stack;
}
void push(Stack *stack, int value) {
Node *node = (Node *)malloc(sizeof(Node));
node->value = value;
node->next = stack->top;
stack->top = node;
}
int pop(Stack *stack) {
Node *old = stack->top;
if(stack->top == NULL) return -1;
int value = old->value;
stack->top = old->next;
free(old);
return value;
}
int main() {
Stack *stack = newStack();
push(stack, 1);
push(stack, 2);
printf("%d ", pop(stack));
printf("%d ", pop(stack));
return 0;
}
Remark
스택은 바닥을 향하는 단방향 링크드 리스트로 구현하면 된다.
Top의 위치만 가지고 있으면 됨.