언제 쓰나
- “가장 최근 것부터 처리”, 괄호 짝 맞추기, 되돌리기(undo), DFS → 스택
- “들어온 순서대로 처리”, 대기열, 단계별 확산, BFS → 큐
문제를 읽으며 “가장 최근에 넣은 것을 먼저 봐야 하는가, 먼저 들어온 것을 먼저 처리해야 하는가”를 물으면 답이 갈린다.
핵심 아이디어
둘 다 값을 순서대로 보관하지만, 꺼내는 방향이 다르다.
스택 (LIFO) 큐 (FIFO)
push(3) ↓ ↑ pop()→3 offer(1) → [1 2 3] → poll()→1
[3] ↑앞(front)에서 꺼내고
[2] 뒤(rear)로 넣는다
[1]
접시 쌓기 — 맨 위부터 줄 서기 — 먼저 온 사람부터스택은 DFS, 백트래킹, 괄호 검사처럼 “최근 상태를 먼저 처리해야 하는 문제”에 쓰인다. 재귀 호출도 내부적으로 스택이다 — 가장 나중에 호출된 함수가 먼저 끝난다. 큐는 BFS, 작업 대기열처럼 “들어온 순서대로 처리해야 하는 문제”에 맞고, BFS에서는 현재 위치에서 갈 수 있는 후보를 큐에 넣고 먼저 발견한 후보부터 탐색한다.
코드 템플릿
파이썬에서 스택은 리스트로 충분하다. 큐는 반드시 deque를 쓴다.
from collections import deque
# 스택 — 리스트의 끝을 top으로
stack = []
stack.append(1) # push
stack.append(2)
stack[-1] # peek → 2
stack.pop() # pop → 2, O(1)
# 큐 — deque의 양 끝
queue = deque()
queue.append(1) # 뒤로 넣고
queue.append(2)
queue[0] # front 확인 → 1
queue.popleft() # 앞에서 꺼낸다 → 1, O(1)괄호 검사는 스택의 대표 패턴이다. 여는 괄호는 쌓고, 닫는 괄호가 오면 top과 짝을 맞춘다.
def is_valid(s):
pair = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif not stack or stack.pop() != pair[ch]:
return False
return not stack풀이 과정 따라가기
괄호 검사 템플릿이 ([{}])를 검사하는 과정이다.
함정
list.pop(0)은O(n)이다. 리스트로 큐를 흉내 내면 앞 원소를 뺄 때마다 나머지 전체가 밀린다. BFS처럼 큐 연산이 수만 번 일어나는 문제에서는 이 차이만으로 시간 초과가 갈린다 — 큐는deque.popleft().- 빈 컨테이너 pop.
stack.pop()은 비어 있으면 예외를 던진다. 꺼내기 전에if stack:으로 확인하는 습관을 들인다. - deque의 중간 접근은 느리다.
deque[k]는O(n)이다. 인덱스 접근이 많으면 리스트, 양 끝 삽입·삭제가 많으면 deque로 고른다.