> [!abstract] Introduction
> 스택(*Stack*)은 가장 나중에 들어온 원소가 가장 먼저 나가는 LIFO(*Last-In, First-Out*) 정책을 따르는 선형 자료구조입니다. 접시를 쌓아 올리듯, 마지막에 올린 접시를 가장 먼저 꺼내는 구조와 같습니다. [[Depth-First Search|DFS]]의 탐색 경계를 관리하거나, 함수 호출의 실행 흐름을 추적하거나, 수식의 괄호 짝을 검사하는 등 "되돌아가기"가 필요한 곳이면 어디든 쓰입니다. 이 글에서는 스택의 핵심 연산과 동작 원리, 구현 방법, 재귀 및 DFS와의 관계, 그리고 활용 사례를 살펴봅니다.
## 핵심 연산
모든 핵심 연산이 $O(1)$이라는 점이 스택의 강점이다. 삽입과 삭제가 모두 한쪽 끝에서만 일어나기 때문에, 다른 원소를 밀거나 당길 필요가 없다.
![[stackConcept.svg]]
### `push(x)`
원소 $x$를 스택의 꼭대기(*top*)에 추가한다. $O(1)$의 시간복잡도를 가진다.
### `pop()`
스택의 꼭대기에서 원소를 꺼내 반환한다. $O(1)$의 시간복잡도를 가진다.
### `peek()`
`top()`이라고도 종종 부른다. 꼭대기 원소를 꺼내지 않고 확인만 한다. 시간복잡도는 $O(1)$이다.
### `is_empty()`
스택이 비어 있는지 확인한다. 시간복잡도는 $O(1)$이다.
## 동작 원리
스택은 내부적으로 `top`이라는 인덱스 하나로 상태를 관리한다. `top`은 가장 최근에 삽입된 원소의 위치를 가리킨다. `push`하면 `top`이 1 증가하고 해당 위치에 원소를 저장한다. `pop`하면 `top` 위치의 원소를 반환하고 `top`을 1 감소시킨다.
![[stackOperations.svg]]
CLRS의 의사코드로 표현하면 다음과 같다.
$
\texttt{STACK-EMPTY}(S): \quad \text{if } S.top == 0 \text{ return } \text{True} \text{ else return } \text{False}
$
$
\texttt{PUSH}(S, x): \quad S.top = S.top + 1; \quad S[S.top] = x
$
$
\texttt{POP}(S): \quad \text{if } \texttt{STACK-EMPTY}(S) \text{ then error "underflow"} \quad \text{else } S.top = S.top - 1; \quad \text{return } S[S.top + 1]
$
`push`할 때 `top`이 배열 크기를 초과하면 **오버플로**(*overflow*)가 발생하고, `pop`할 때 스택이 비어 있으면 **언더플로**(*underflow*)가 발생한다[^stack-overflow]. 이 두 가지 경계 조건을 항상 검사해야 한다.
## 구현 방법
### 배열 기반
배열로 스택을 구현하면 `top` 인덱스 하나만 관리하면 되므로 가장 단순하다. 배열의 인덱스 0부터 차례로 원소를 쌓고, `top`은 마지막으로 삽입된 원소의 인덱스를 가리킨다.
```python
class ArrayStack:
def __init__(self, capacity: int):
self._data = [None] * capacity
self._top = -1
self._capacity = capacity
def push(self, x):
if self._top == self._capacity - 1:
raise OverflowError("Stack overflow")
self._top += 1
self._data[self._top] = x
def pop(self):
if self._top == -1:
raise IndexError("Stack underflow")
val = self._data[self._top]
self._top -= 1
return val
def peek(self):
if self._top == -1:
raise IndexError("Stack is empty")
return self._data[self._top]
def is_empty(self) -> bool:
return self._top == -1
```
배열 기반 구현의 한계는 용량이 고정되어 있다는 점이다. 용량을 초과하면 더 큰 배열을 할당하고 기존 원소를 복사해야 한다. Python의 `list`는 내부적으로 동적 배열[^dynamic-array]이므로 이 과정을 자동으로 처리한다.
### 연결 리스트 기반
[[연결 리스트]]로 구현하면 크기 제한이 없다. 새 원소를 리스트의 `head`에 삽입하면 `push`, `head`에서 제거하면 `pop`이 된다. 배열과 달리 용량 초과 걱정이 없지만, 각 노드마다 포인터를 위한 추가 메모리가 필요하고 캐시 지역성[^cache-locality]이 떨어진다.
### Python `list`
Python에서 스택을 사용할 때 가장 실용적인 방법은 내장 `list`를 그대로 쓰는 것이다. `append()`가 `push`, `pop()`이 `pop` 역할을 한다.
```python
stack = []
stack.append("A") # push
stack.append("B")
stack.append("C")
print(stack.pop()) # pop → "C"
print(stack.pop()) # "B"
print(stack[-1]) # peek → "A"
```
`collections.deque`도 스택으로 쓸 수 있다. `append()`와 `pop()`이 양쪽 끝에서 $O(1)$을 보장하므로, `list`의 동적 배열 리사이징에 의한 간헐적 $O(n)$이 걱정될 때 대안이 된다.
## 스택과 재귀의 관계
스택과 [[Recursion|재귀]]는 본질적으로 같은 메커니즘이다. 프로그램이 함수를 호출하면, 운영체제는 **호출 스택**(*call stack*)에 해당 함수의 지역 변수, 매개변수, 복귀 주소를 담은 **스택 프레임**(*stack frame*)을 `push`한다. 함수가 반환되면 해당 프레임을 `pop`하여 이전 함수의 실행 지점으로 되돌아간다.
이 원리 때문에 모든 재귀 알고리즘은 명시적 스택을 사용하는 반복 알고리즘으로 변환할 수 있다. [[Depth-First Search]]의 재귀 구현이 자연스러운 이유도, 재귀 호출 자체가 시스템의 호출 스택을 DFS의 탐색 스택으로 활용하기 때문이다. 반대로 재귀 깊이가 너무 깊어 스택 오버플로가 우려될 때는, 명시적 스택을 사용한 반복 구현으로 전환하면 된다[^recursion-to-iteration].
## 스택과 DFS
[[Depth-First Search]]는 스택의 대표적인 응용이다. DFS가 한 경로를 끝까지 따라간 뒤 막히면 가장 최근의 갈림길로 되돌아오는 동작은, 스택의 LIFO 정책과 정확히 대응된다.
```
function DFS-Iterative(graph, start) returns visited order
stack ← empty stack
visited ← empty set
stack.push(start)
while stack is not empty do
current ← stack.pop()
if current not in visited then
visited.add(current)
for each neighbor of current do
if neighbor not in visited then
stack.push(neighbor)
```
`push`로 탐색할 이웃을 스택에 넣고, `pop`으로 다음에 탐색할 노드를 꺼낸다. 스택이 LIFO이므로 가장 나중에 발견된 이웃(가장 깊은 방향)이 먼저 탐색되어 깊이 우선 탐색이 자연스럽게 이루어진다. [[Breadth-First Search|BFS]]가 [[Queue|큐]](FIFO)를 사용하여 너비 방향으로 탐색하는 것과 대비된다.
## 스택과 다른 자료구조의 관계
**[[Queue|큐]]**는 FIFO 정책을 따르는 자료구조로, 스택과 정반대의 순서로 원소를 꺼낸다. [[Breadth-First Search|깊이 우선 탐색]]에서 사용된다. **덱**(*deque*, double-ended queue)은 양쪽 끝에서 삽입과 삭제가 가능한 일반화된 자료구조로, 스택으로도 큐로도 쓸 수 있다. **[[Priority Queue|우선순위 큐]]**는 우선순위에 따라 원소를 꺼내는 자료구조로, 내부적으로 [[Heap|힙]]을 사용한다.
## 어디에 쓰이는가
스택은 "되돌아가기"와 "짝 맞추기"가 필요한 곳에서 빛난다. 웹 브라우저의 뒤로 가기 버튼은 방문 기록을 스택에 쌓아서 구현한다. 텍스트 에디터의 실행 취소(*undo*) 기능도 편집 동작을 스택에 기록한다. 컴파일러는 수식의 괄호 짝을 검사할 때 여는 괄호를 `push`하고 닫는 괄호를 만나면 `pop`하여 짝이 맞는지 확인한다[^parenthesis-matching]. 중위 표기법을 후위 표기법으로 변환하는 알고리즘(Shunting Yard)이나, 후위 표기법 수식을 평가하는 알고리즘도 스택을 핵심으로 사용한다.
시스템 수준에서는 앞서 살펴본 호출 스택이 프로그램의 함수 호출 흐름 전체를 관리한다. 인터럽트 처리에서도 현재 실행 상태를 스택에 저장한 뒤 인터럽트 핸들러를 실행하고, 처리가 끝나면 스택에서 복원하여 원래 흐름으로 돌아간다.
---
## 출처
- Cormen, T. H. et al. (2022) *Introduction to Algorithms*. 4th edn. Cambridge, MA: MIT Press. Chapter 10.1.
- Python Software Foundation (2025) *Data Structures — More on Lists*. Available at: https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-stacks.
[^stack-overflow]: 용어 "스택 오버플로"(*stack overflow*)는 자료구조의 배열 용량 초과뿐 아니라, 프로그램의 호출 스택이 시스템이 할당한 메모리 한도를 넘는 경우에도 쓰인다. 재귀가 너무 깊으면 후자의 스택 오버플로가 발생한다.
[^dynamic-array]: 동적 배열(*dynamic array*)은 용량이 가득 차면 보통 2배 크기의 새 배열을 할당하고 기존 원소를 복사한다. 개별 `push`는 최악의 경우 $O(n)$이지만, 상각 분석(*amortized analysis*)으로 평균 $O(1)$이 보장된다. Cormen et al. (2022), Chapter 16.3 참조.
[^cache-locality]: 캐시 지역성(*cache locality*)은 CPU 캐시가 인접한 메모리 주소를 미리 적재하는 특성이다. 배열은 원소가 연속된 메모리에 저장되므로 캐시 히트율이 높지만, 연결 리스트는 노드가 메모리 곳곳에 흩어져 있어 캐시 미스가 자주 발생한다.
[^recursion-to-iteration]: 재귀를 반복으로 변환할 때, 재귀 호출 시점에 스택에 `push`하고 재귀 반환 시점에 `pop`하면 된다. 꼬리 재귀(*tail recursion*)의 경우 스택 없이 단순 반복문으로 변환할 수 있다.
[^parenthesis-matching]: 괄호 검사 알고리즘은 여는 괄호 `(`, `[`, `{`를 만나면 스택에 `push`하고, 닫는 괄호를 만나면 스택에서 `pop`하여 짝이 맞는지 비교한다. 수식 끝까지 처리한 뒤 스택이 비어 있으면 모든 괄호의 짝이 올바른 것이다.