스택(Stack)은 후입선출(LIFO, Last In First Out) 원칙으로 동작하는 선형 자료구조다. 가장 나중에 삽입된 데이터가 가장 먼저 제거된다. 접시를 쌓고 꺼내는 방식과 같다. 함수 호출 스택, 괄호 검사, 되돌리기(Undo) 기능 등 프로그래밍 전반에 걸쳐 핵심적으로 활용된다.
핵심 연산
초기 상태: []
push(1): [1] top=1
push(2): [1, 2] top=2
push(3): [1, 2, 3] top=3
pop(): [1, 2] top=2 (3 반환)
peek(): top = 2 (제거 없이 조회)
| 연산 | 설명 | 시간복잡도 |
|---|
| push(x) | top에 삽입 | O(1) |
| pop() | top 제거·반환 | O(1) |
| peek() / top() | top 조회 (제거 없음) | O(1) |
| isEmpty() | 비어있는지 확인 | O(1) |
스택 vs 큐
| 항목 | 스택 (Stack) | 큐 (Queue) |
|---|
| 원칙 | LIFO (후입선출) | FIFO (선입선출) |
| 삽입·제거 위치 | top (같은 쪽) | 양쪽 (rear 삽입, front 제거) |
| 비유 | 접시 쌓기 | 줄 서기 |
언어별 구현
python
# Python (리스트로 스택 사용)
stack = []
stack.append(1) # push
stack.append(2)
stack.append(3)
stack.pop() # pop → 3
stack[-1] # peek → 2
java
// Java
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // push
stack.push(2);
stack.pop(); // pop → 2
stack.peek(); // peek → 1
javascript
// JavaScript
const stack = [];
stack.push(1); // push
stack.push(2);
stack.pop(); // pop → 2
stack[stack.length - 1]; // peek → 1
콜 스택 (Call Stack)
프로그램 실행 시 함수 호출 순서를 관리하는 스택.
main() 호출
↓ push(main)
factorial(3) 호출
↓ push(factorial(3))
factorial(2) 호출
↓ push(factorial(2))
factorial(1) 호출
↓ push(factorial(1)) → return 1
pop(factorial(1)) → factorial(2) 재개
pop(factorial(2)) → factorial(3) 재개
pop(factorial(3)) → main 재개
pop(main)
재귀 함수 호출이 너무 깊으면 스택 오버플로우(Stack Overflow) 발생.
주요 활용
| 분야 | 활용 예시 |
|---|
| 함수 호출 | 콜 스택, 재귀 함수 |
| 괄호 검사 | ({[]}) 유효성 검사 |
| 수식 계산 | 후위 표기법(Postfix) 계산 |
| 되돌리기 | 편집기 Undo/Redo |
| 브라우저 | 뒤로 가기 기록 |
| DFS | 깊이 우선 탐색 |
| 컴파일러 | 구문 분석(Parsing) |
괄호 검사 예시
python
def is_valid(s):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for c in s:
if c in '({[':
stack.append(c)
elif c in ')}]':
if not stack or stack[-1] != pairs[c]:
return False
stack.pop()
return len(stack) == 0
is_valid("({[]})") # True
is_valid("([)]") # False
관련 개념
참고문헌
- •Cormen et al. (2009). Introduction to Algorithms — Chapter 10
- •Sedgewick & Wayne. Algorithms, 4th Edition
