[5] 스택(Stack)

스택(Stack)은 LIFO(Last-In-First-Out) 리스트이다.

즉, 가장 나중에 들어온 원소가 가장 처음 나가도록 한다.

 

스택에 원소가 들어오는 것을 push 라고 하고

스택에서 원소가 나가는 것을 pop 이라고 한다.

또한 스택에서 가장 마지막에 들어온 원소, 즉 가장 위에 있는 원소를 top 이라고 한다.

 

예시를 보면 더 쉽게 이해할 수 있다.

 

A 원소를 스택에 push 하면, 원소 A는 top 이 된다.

 

B를 스택에 push 하면 A위에 B가 쌓이고, 원소 B가 top이 된다. 

 

C를 스택에 push 하면 B위에 C가 쌓이고, 원소 C가 top이 된다.

 

이번엔 스택에서 pop 하면

스택은 다음과 같이 A와 B만 쌓여 있고 C는 리턴된다.

 

한번 더 스택에서 pop 하면

스택은 다음과 같이 A만 쌓여 있고, B는 리턴된다.

 

C 언어 코드

#define MAX_STACK_SIZE 100
typedef struct {
    int key;
    // 다른 필드들
}element;
element stack[MAX_STACK_SIZE];
int top = -1;

위와 같이 스택을 정의한다.

 

void push(element item) {
    if (top >= MAX_STACK_SIZE)
        stackFull();
    stack[++top] = item;
}

스택에 원소를 삽입하는 push 함수

 

element pop() {
    if (top == -1)
        return stackEmpty();
    return stack[top--];
}

스택에서 원소를 삭제하고 리턴하는 pop 함수

 

위의 stackFull과 stackEmpty는 스택이 모두 찼을 때의 에러를 출력하는 함수이다. (생략)