3. 스택(Stack)

▣ 스택(Stack)

■ 스택이란 후입선출(LIFO : Last In, First Out) 구조를 가지는 자료 구조입니다. 가장 나중에 삽입(push) 된 데이터가 가장 먼저 삭제(pop)되는 자료구조입니다. 그리고 자료의 추가와 삭제는 항상 Stack의 Top에서만 이루어집니다.

 

■ 어려운 개념은 아니지만 예를 들자면, 회전초밥집에 갔을 때 쌓여있는 접시를 생각하면 좋을 것 같습니다. 제일 처음 먹은 접시가 제일 아래에 놓이게 되고, 제일 나중에 먹은 접시가 제일 위에 놓이게 됩니다. 그리고 계산할 때 접시를 하나씩 빼면서 접시의 개수를 센다고 하면, 가장 위에 놓인 접시가 가장 먼저 꺼내집니다. 스택도 마찬가지로 가장 나중에 스택에 들어온 데이터가 가장 먼저 삭제됩니다.

 

Stack의 구조

■ 위 그림의 용어의 명칭은 아래와 같습니다.

- Push : 스택에 데이터(element)를 추가

- Pop : 스택에서 데이터 제거 

- Top : 마지막 push가 일어난 부분

- Bottom : 가장 처음 push가 일어난 부분

- 스택은 LIFO라고 했으므로 데이터의 추가(Push) 또는 삭제(Pop) 또한 Stack의 Top에서만 발생하게 됩니다.

 

 스택의 사용 예시로는 function call과 return이 있습니다. 함수가 호출되면 Stack에 함수 호출 정보를 Push하고, 반환되면 Stack에서 함수 호출 정보를 Pop합니다.

 

■ 스택을 구현하는 방법에는 2가지가 있습니다.

1. 전역변수(global variable)를 사용한 스택

2. 구조체(struct)를 사용한 스택

 

 사실 두 스택 구현 방법에 큰 차이가 있는 것은 아니고 비슷하다고 생각하시면 됩니다. 자세한 내용은 아래에서 코드 구현을 통해 확인해보겠습니다.

 

# 전역변수를 사용한 스택

#include <stdio.h>
#include <stdlib.h>
 
#define MAX_STACK_SIZE 100
typedef int element;
element stack[MAX_STACK_SIZE];
int top = -1;
 
// Stack이 비어있는지 검출
int is_empty() {
    return top == -1;
}
 
 
// Stack이 가득 차있는지 검출
int is_full() {
    return top == MAX_STACK_SIZE - 1;
}
 
void push(element data) {
    if (is_full()) {
        fprintf(stderr, "Stack is full\n");
        exit(1);
    }
    else stack[++top] = data;
}
 
element pop() {
    if (is_empty()) {
        fprintf(stderr, "Stack is empty\n");
        exit(1);
    }
    else return stack[top--];
}
 
 
int main() {
    push(1);
    push(2);
    push(3);
    printf("data : %d\n", pop());
    printf("data : %d\n", pop());
    printf("data : %d\n", pop());
}
 

 스택을 구현하기 위해 is_empty(), is_full(), push, pop() 등의 함수가 사용되었습니다. 저는 C언어로 구현했지만, 어떤 언어로 구현하든 위와 비슷한 함수와 코드 구조를 사용할 수 있습니다. 시나리오를 살펴보면 스택에 data(item, element라고도 합니다) 가 push 될 때마다 top이 1씩 증가하고, 스택에서 data가 pop될 때마다 top이 1씩 감소합니다.

 위 코드에서 MAX_STACK_SIZE가 100이기 때문에 스택이 비어있으면 top == -1, 스택이 가득 차있으면 top == 99입니다. 그리고 스택에는 데이터가 하나 저장될 때마다(push()를 수행할 때마다) 최소 0부터 최대 99까지 증가합니다. 예를 들어 현재 스택에 10개의 data가 저장되어 있다면 top == 9이고, 다음에 push()가 이루어지면 data는 stack[10]에 저장됩니다.

 

# 구조체를 사용한 스택

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
 
typedef int element;
typedef struct {
    element stack[MAX_STACK_SIZE];
    int top;
} StackType;
 
void init_stack(StackType* s)
{
    s->top = -1;
}
int is_empty(StackType* s)
{
    return (s->top == -1);
}
int is_full(StackType* s)
{
    return (s->top == (MAX_STACK_SIZE - 1));
}
void push(StackType* s, element item)
{
    if (is_full(s)) {
        fprintf(stderr, "Stack is full\n");
        exit(1);
    }
    else s->stack[++(s->top)] = item;
}
element pop(StackType* s)
{
    if (is_empty(s)) {
        fprintf(stderr, "Stack is empty\n");
        exit(1);
    }
    else return s->stack[(s->top)--];
}
int main(void)
{
    StackType s;
    init_stack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
}

 

 

 

 구조체를 이용한 스택도 전역변수를 이용한 스택과 크게 다르지 않습니다. 다만 스택을 초기화하기 위해서 init_stack()이라는 함수가 사용되었고, 조금 더 복잡해보이는 구조를 가지고 있습니다. 하지만 보기에만 복잡해 보일 뿐 실제 구조는 두 구현 방식 모두 동일합니다. 

 실행 결과 또한 두 구현 방식 모두 동일합니다. '1', '2', '3' 순서대로 push() 했으므로 '3', '2', '1' 순서대로 pop() 되는 것을 확인할 수 있습니다. 이는 위에서 설명 드렸듯이 스택이 후입선출 구조를 가지는 자료구조이기 때문입니다.

 

[참고자료]

1. 신동하, 자료구조

2. 생능출판사, C언어로 쉽게 풀어쓴 자료구조