컴퓨터공학 300 주제 시리즈의 043번째 글이다. 전체 지도는 여기.

한 줄 요약

스택은 한쪽 끝에서만 넣고(push) 빼는(pop) LIFO(Last-In, First-Out) 구조이고, “지금 하던 일을 잠깐 미뤄 두고 더 안쪽 일을 먼저 끝낸다”는 모든 상황의 기본 도구다.

왜 필요한가

스택은 연산이 가장 적은 자료구조다. 넣기, 빼기, 맨 위 보기. 그런데 쓰임은 가장 넓다. 함수를 호출하면 CPU 와 런타임은 돌아올 주소와 지역 변수를 스택에 쌓는다. 괄호가 제대로 닫혔는지 확인하는 컴파일러, 브라우저의 뒤로 가기, 편집기의 실행 취소, 깊이 우선 탐색, 그리고 파이썬과 자바 가상 머신의 바이트코드 실행까지 모두 스택이다.

이런 문제들의 공통점은 중첩이다. 괄호 안에 괄호가 있고, 함수 안에서 함수를 부르고, 폴더 안에 폴더가 있다. 안쪽을 먼저 끝내야 바깥으로 돌아갈 수 있다. 가장 최근에 열린 것이 가장 먼저 닫힌다는 규칙이 바로 LIFO 다.

핵심 개념

연산과 비용

연산 의미 비용
push(x) 맨 위에 x 를 올림 O(1) (동적 배열이면 분할 상환)
pop() 맨 위를 꺼내 돌려줌 O(1)
peek() / top() 맨 위를 보기만 함 O(1)
is_empty() 비었는지 O(1) 
push(1) push(2) push(3)        pop() → 3

   ┌───┐                         
   │ 3 │ ← top                   ┌───┐
   ├───┤                         │ 2 │ ← top
   │ 2 │                         ├───┤
   ├───┤                         │ 1 │
   │ 1 │                         └───┘
   └───┘

구현: 배열 끝이 곧 스택 꼭대기

스택은 동적 배열의 끝을 꼭대기로 쓰면 그대로 만들어진다. 앞 글에서 본 것처럼 배열 끝에서 넣고 빼는 것은 O(1) 이다. 배열 앞을 꼭대기로 쓰면 매번 O(n) 이 되니 방향을 잘못 잡으면 안 된다. 연결 리스트의 머리를 꼭대기로 써도 O(1) 이지만, 캐시와 할당 비용 때문에 대개 배열 쪽이 빠르다.

언어별로는 이렇다.

  • 파이썬: list 의 append / pop(). 공식 튜토리얼이 “리스트를 스택으로 쓰기” 절에서 이 방법을 안내한다(Python Tutorial — Data Structures).
  • 자바: 오래된 Stack 클래스 대신 Deque 를 쓰라고 공식 문서가 권한다. Deque 인터페이스 문서에는 “레거시 Stack 클래스보다 이 인터페이스를 우선 사용해야 한다”고 적혀 있다(Java SE 21 Deque). 구현체로는 ArrayDeque 를 쓴다.
  • C++: std::stack 은 다른 컨테이너(기본 std::deque)를 감싼 어댑터다.

호출 스택(call stack)

함수 f 가 g 를 부르면, 런타임은 f 의 지역 변수와 “g 가 끝나면 돌아올 위치”를 담은 프레임을 쌓고 g 의 프레임을 그 위에 올린다. g 가 끝나면 프레임을 빼고 f 로 돌아간다. 재귀가 너무 깊어지면 이 스택이 넘치는데, 이것이 스택 오버플로다. MDN 의 호출 스택 용어 설명도 스택이 할당된 공간보다 커지면 “stack overflow” 오류가 난다고 설명한다(MDN — Call stack).

파이썬은 C 스택이 실제로 넘쳐 프로세스가 죽기 전에 막으려고 재귀 깊이 한도를 둔다. sys.setrecursionlimit 문서는 이 한도가 “무한 재귀가 C 스택 오버플로를 일으켜 파이썬이 죽는 것을 막는다”고 설명한다(Python sys).

스택 기계: 바이트코드도 스택으로 계산한다

JVM 명세는 각 프레임이 피연산자 스택(operand stack) 을 가진다고 정의한다(JVM Specification SE 21, Chapter 2). 산술 명령은 스택에서 값을 꺼내 계산하고 결과를 다시 넣는다. CPython 도 같은 방식이다. (a + b) * c 를 디스어셈블하면 다음과 같다(파이썬 3.12).

LOAD_NAME   a        스택: [a]
LOAD_NAME   b        스택: [a, b]
BINARY_OP   +        스택: [a+b]
LOAD_NAME   c        스택: [a+b, c]
BINARY_OP   *        스택: [(a+b)*c]
RETURN_VALUE

이것은 정확히 후위 표기법(postfix) a b + c * 의 계산 순서다. 괄호가 사라지고 순서만 남는다. 컴파일러는 중위식을 후위식 순서로 바꾸고, 기계는 스택 하나로 그것을 계산한다.

재귀는 숨은 스택이다

재귀 함수는 호출 스택을 자료구조처럼 빌려 쓰는 것이다. 그래서 어떤 재귀든 명시적 스택을 써서 반복문으로 바꿀 수 있다. 깊이 우선 탐색(DFS)이 대표적이다. 재귀 한도에 걸리는 깊은 구조(긴 연결 체인, 깊은 디렉터리)를 다룰 때 이 변환이 실제로 필요하다.

직접 해 보기

괄호 짝 검사와 후위식 계산을 스택으로 구현한다.

PAIRS = {")": "(", "]": "[", "}": "{"}

def balanced(s):
    stack = []
    for i, ch in enumerate(s):
        if ch in "([{":
            stack.append((ch, i))
        elif ch in PAIRS:
            if not stack or stack[-1][0] != PAIRS[ch]:
                return f"위치 {i} 의 '{ch}' 짝이 안 맞음"
            stack.pop()
    if stack:
        ch, i = stack[-1]
        return f"위치 {i} 의 '{ch}' 가 닫히지 않음"
    return "OK"

def eval_postfix(tokens):
    stack = []
    ops = {"+": lambda a, b: a + b, "-": lambda a, b: a - b,
           "*": lambda a, b: a * b, "/": lambda a, b: a / b}
    for t in tokens.split():
        if t in ops:
            b = stack.pop(); a = stack.pop()   # 순서 주의: 나중에 넣은 게 오른쪽
            stack.append(ops[t](a, b))
        else:
            stack.append(float(t))
        print(f"{t:>3} → {stack}")
    return stack.pop()

for s in ["a[i] = f(x, {k: v})", "(a + b]", "((x)"]:
    print(f"{s!r:24} {balanced(s)}")
print(eval_postfix("3 4 + 2 * 7 -"))

'a[i] = f(x, {k: v})'    OK
'(a + b]'                위치 6 의 ']' 짝이 안 맞음
'((x)'                   위치 0 의 '(' 가 닫히지 않음
  3 → [3.0]
  4 → [3.0, 4.0]
  + → [7.0]
  2 → [7.0, 2.0]
  * → [14.0]
  7 → [14.0, 7.0]
  - → [7.0]
7.0

(3 + 4) * 2 - 7 = 7 이 맞게 나온다. 빼기에서 b 를 먼저 꺼낸다는 점이 흔한 실수 지점이다.

다음은 재귀를 명시적 스택으로 바꾼 예다. 깊이 5000 짜리 일렬 구조의 깊이를 잰다.

import sys
print("기본 재귀 한도:", sys.getrecursionlimit())

def depth_rec(i, n):
    return 0 if i == n else 1 + depth_rec(i + 1, n)

def depth_iter(n):
    stack, best = [(0, 0)], 0          # (노드, 깊이)
    while stack:
        i, d = stack.pop()
        best = max(best, d)
        if i < n:
            stack.append((i + 1, d + 1))
    return best

try:
    print(depth_rec(0, 5000))
except RecursionError as e:
    print("재귀 버전:", type(e).__name__)
print("명시적 스택 버전:", depth_iter(5000))

기본 재귀 한도: 1000
재귀 버전: RecursionError
명시적 스택 버전: 5000

한도를 올리는 방법도 있지만, 한도를 너무 올리면 실제 C 스택이 넘쳐 프로세스가 죽을 수 있다. 명시적 스택은 힙 메모리를 쓰므로 그런 걱정이 없다.

현업에서는

  • 스택 트레이스 읽기. 장애 로그의 예외 스택 트레이스는 사고 시점 호출 스택의 사진이다. 맨 위(또는 언어에 따라 맨 아래)가 가장 안쪽 프레임이다. 이 방향을 알고 읽어야 원인 함수를 빨리 찾는다.
  • 스레드 스택 크기. 스레드마다 호출 스택용 메모리가 따로 잡힌다. 스레드를 수천 개 띄우는 서버는 이 메모리만으로 상당한 양을 쓴다. 컨테이너 메모리 한도를 정할 때 힙만 보면 안 되는 이유다.
  • 실행 취소, 뒤로 가기. 편집기의 undo, 브라우저 뒤로 가기는 스택 두 개(undo·redo)로 만드는 것이 기본형이다.
  • 파서와 템플릿 엔진. JSON, YAML, HTML 파서는 중첩을 스택으로 추적한다. “닫히지 않은 태그” 오류 메시지가 어디를 가리키는지는 스택 맨 위에 무엇이 남았는지로 정해진다.

확인 문제

  1. 빈 스택에 push 1, push 2, pop, push 3, push 4, pop, pop 을 하면 꺼낸 값의 순서와 남은 내용은?
  2. 동적 배열로 스택을 만들 때 배열의 앞을 꼭대기로 쓰면 어떤 문제가 생기는가?
  3. 중위식 (5 - 1) * (2 + 3) 의 후위식을 쓰고, 스택으로 계산한 값은?
  4. 자바에서 스택이 필요할 때 공식 문서가 권하는 타입은?
  5. 재귀 DFS 를 반복문으로 바꿀 때 필요한 것은 무엇이고, 바꾸면 무엇이 좋아지는가?

풀이

  1. 꺼낸 순서는 2, 4, 3. 남은 것은 [1].
  2. push 와 pop 마다 나머지 원소를 모두 밀거나 당겨야 해서 O(n) 이 된다.
  3. 5 1 - 2 3 + *, 값은 4 × 5 = 20.
  4. Deque 인터페이스(구현은 보통 ArrayDeque). 레거시 Stack 은 권하지 않는다.
  5. 명시적 스택(예: 리스트). 재귀 깊이 한도나 호출 스택 오버플로에서 벗어나고, 스택 크기를 힙에서 관리할 수 있다.

더 읽을거리 (References)