**stack(스택)**은 LIFO(Last-In, First-Out, 후입선출) 컬렉션입니다. 마지막에 push된 원소가 가장 먼저 pop됩니다. 오직 **top(맨 위)**만 다룰 수 있습니다.
연산
text
push(3) push(7) pop()->7 peek()->3
[ 3 ] [ 7 ] [ 3 ] [ 3 ]
[ 3 ] top
top
예시
python
stack = []
stack.append('a') # push
stack.append('b') # push
top = stack[-1] # peek -> 'b'
stack.pop() # pop -> 'b'
dynamic array나 linked list로 뒷받침될 때 모든 연산은 **O(1)**입니다.
| 연산 | 시간 |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |
일반적인 용도
- 함수 호출 스택(call stack) — 활성 호출과 지역 변수를 추적함.
- 실행 취소/다시 실행(undo/redo) — 각 동작을 push하고, 취소하려면 pop함.
- 수식 평가 / 파싱 — 괄호 짝 맞추기, 중위 표기를 후위 표기로 변환.
- 백트래킹 & DFS — 어디로 되돌아갈지 기억함.
왜 중요한가
stack은 "가장 최근의 것을 먼저 처리한다"를 모델링하며, 이는 재귀부터 브라우저 뒤로 가기 버튼까지 어디에나 등장합니다.
LIFO 패턴을 인식하면 즉시 stack을 떠올리게 되고, 엉킨 문제가 깔끔한 몇 줄의 push/pop으로 정리되는 경우가 많습니다.