스택 (Stack)

1. 개요

스택 (stack)은 한쪽 끝에서만 자료를 추가하거나 꺼낼 수 있는 자료구조이다. 스택은 Last In First Out (LIFO)의 구조로 동작하기 때문에 스택에 접근할 때는 가장 최근에 추가된 자료부터 읽는다. 스택에 자료를 추가하는 연산을 push, 자료를 꺼내는 연산을 pop이라고 한다.

[그림 1] 스택의 동작

스택은 많은 프로그램에서 광범위하게 사용되고 있는 자료구조로써, 가장 대표적인 활용으로는 시스템 스택이 있다. 다소 복잡해보일 수도 있는 함수 호출이나 재귀적 실행을 스택이라는 자료구조를 통해 간단히 구현할 수 있다. 아래의 [코드 1]은 main에서 func1을 호출하고 func1에서는 func2를, func2에서는 func3를 호출하도록 동작한다. 그러나 실질적인 프로그램의 실행은 func3가 실행되고 그 다음 func2, func1, 마지막으로 main이 실행된다. 즉, 콘솔창에는 "abc"가 출력되는 것이 아니라 "cba"가 출력된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void func1() {
    func2();
    printf("a");
}
 
void func2() {
    func3();
    printf("b");
}
 
void func3() {
    printf("c");
}
 
int main() {
    func1();
 
    return 0;
}
cs

[코드 1] 함수 호출

소스 코드의 순서와 프로그램이 실행되는 것을 고려하면, 소스 코드상으로 마지막에 나타나는 코드가 가장 먼저 실행되는 것을 알 수 있다. [코드 1]에 작성된 프로그램의 실행 단계에서는 소스 코드 상의 함수들이 [그림 1]과 같이 배치되고, 시스템은 최상위 부분부터 소스 코드를 실행한다. 스택은 이러한 구조를 가장 잘 나타낼 수 있는 자료구조이기 때문에 시스템의 프로그램의 실행 구조를 구현할 때 많이 이용된다.