브라우저에서 함수가 함수를 부르고, 그 안에서 또 다른 함수를 부를 때를 떠올려보겠습니다. 가장 나중에 들어간 함수부터 끝나야 원래 자리로 돌아올 수 있습니다. 반대로 프린터 대기열이나 메시지 처리 대기열은 보통 먼저 들어온 작업부터 꺼내는 흐름이 더 자연스럽습니다. 스택과 큐 차이는 바로 이 두 장면의 차이에서 시작합니다.
그래서 이 주제는 FIFO와 LIFO를 외우는 문제라기보다, 작업이 되감기듯 돌아가야 하는가, 아니면 기다리던 순서대로 흘러가야 하는가를 보는 문제에 가깝습니다. 이 글에서는 정의보다 먼저 장면을 보고, 그다음에 콜 스택, undo, DFS와 BFS, 메시지 처리 흐름으로 연결해보겠습니다.
한 줄 정리
짧게 말하면 이렇습니다. 스택은 가장 최근 것이 먼저 나와야 자연스러운 구조이고, 큐는 먼저 들어온 것이 먼저 처리되어야 자연스러운 구조입니다.
스택은 뒤로 되감기, 큐는 차례대로 처리라고 기억하면 실전 판단이 훨씬 쉬워집니다.
스택이 맞는 장면
스택은 위에 올리고 위에서 꺼내는 구조입니다. 그래서 가장 마지막에 시작한 일이 가장 먼저 끝나야 할 때 잘 맞습니다. 대표 장면은 함수 호출, undo, DFS 같은 깊이 우선 흐름입니다.
콜 스택
함수 main이 a를 부르고, a가 다시 b를 부른다고 해보겠습니다. 이때는 b가 끝나야 a로 돌아갈 수 있고, a가 끝나야 다시 main으로 돌아갈 수 있습니다. 즉 가장 최근에 들어간 호출이 먼저 빠져나와야 합니다. 이 흐름은 MDN의 call stack 설명처럼 호출이 쌓이고 끝나면 최근 호출부터 제거되는 방식으로 이해하면 됩니다.
call_stack = []
call_stack.append("main")
call_stack.append("a")
call_stack.append("b")
print(call_stack.pop()) # b
print(call_stack.pop()) # a
print(call_stack.pop()) # main이 예시는 단순하지만 감각은 정확합니다. 돌아갈 자리를 기억해야 하면 스택이 자연스럽습니다.
undo
문서 편집기에서 굵게 만들고, 한 줄을 지우고, 문장을 붙여 넣었다고 해보겠습니다. undo를 누르면 방금 한 붙여넣기부터 취소되어야 자연스럽습니다. 그다음은 줄 삭제, 그다음은 굵게 만들기입니다. 즉 최근 작업부터 거꾸로 되감아야 하므로 스택 감각이 잘 맞습니다.
DFS
미로를 걷는다고 상상해보겠습니다. 갈 수 있는 길이 보이면 일단 한 방향으로 끝까지 내려가 보고, 막히면 바로 직전 갈림길로 돌아옵니다. 이 흐름은 가장 최근에 들어간 분기점으로 복귀하는 구조입니다. 그래서 DFS는 재귀 호출의 콜 스택이나 명시적 스택으로 자주 구현됩니다.
graph = {
1: [2, 3],
2: [4],
3: [5],
4: [],
5: []
}
stack = [1]
visited = []
while stack:
node = stack.pop()
if node in visited:
continue
visited.append(node)
for nxt in reversed(graph[node]):
stack.append(nxt)
print(visited) # [1, 2, 4, 3, 5]여기서 핵심은 구현 문법이 아닙니다. 깊게 들어갔다가 가장 최근 갈림길로 되돌아오는 흐름 자체가 스택적이라는 점입니다. DFS와 BFS 관점 비교는 이 글에서 더 자세히 이어서 볼 수 있습니다.
큐가 맞는 장면
큐는 뒤에 넣고 앞에서 꺼내는 구조입니다. 그래서 먼저 기다린 일이 먼저 처리되어야 할 때 잘 맞습니다. 대표 장면은 줄 서기, 메시지 처리 대기열, BFS 같은 너비 우선 흐름입니다.
작업 대기열
작업이 1번, 2번, 3번 순서로 들어왔다고 해보겠습니다. 특별한 우선순위가 없다면 1번부터 처리하는 쪽이 예측 가능하고 자연스럽습니다. Oracle의 Queue 문서도 큐를 처리 전 요소를 보관하는 컬렉션으로 설명하고, 일반적으로 FIFO로 동작한다고 정리합니다. 물론 실제 시스템은 우선순위, 재시도, 병렬 소비자처럼 더 복잡할 수 있지만 기본 직관은 여전히 유효합니다.
from collections import deque
jobs = deque()
jobs.append("email")
jobs.append("thumbnail")
jobs.append("publish-check")
print(jobs.popleft()) # email
print(jobs.popleft()) # thumbnail
print(jobs.popleft()) # publish-checkPython 공식 문서도 collections.deque를 양 끝에서 빠르게 append/pop 가능한 컨테이너로 설명합니다. 그래서 스택 예시와 큐 예시를 모두 보여주기에 좋습니다.
BFS
이번에는 미로에서 한 갈래를 끝까지 파고들지 말고, 현재 위치에서 한 칸 떨어진 곳들을 먼저 다 확인한다고 생각해보겠습니다. 그다음에는 두 칸 떨어진 곳들, 그다음에는 세 칸 떨어진 곳들로 넓혀 갑니다. 이 흐름은 먼저 발견한 후보를 먼저 처리해야 유지됩니다. 그래서 BFS는 큐가 자연스럽습니다.
from collections import deque
graph = {
1: [2, 3],
2: [4],
3: [5],
4: [],
5: []
}
queue = deque([1])
visited = [1]
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
if nxt not in visited:
visited.append(nxt)
queue.append(nxt)
print(order) # [1, 2, 3, 4, 5]DFS가 깊이를 먼저 본다면, BFS는 넓이를 먼저 봅니다. 이 차이는 알고리즘 선택 문제이기도 하지만, 그 전에 스택과 큐가 세상을 처리하는 순서가 다르다는 이야기이기도 합니다.
breadth vs depth
스택과 큐를 가장 짧게 대비하면 이렇게 말할 수 있습니다. 스택은 지금 막 들어간 맥락을 먼저 처리하고, 큐는 먼저 기다리기 시작한 맥락을 먼저 처리합니다. 그래서 스택은 depth와 가깝고, 큐는 breadth와 가깝습니다.
스택은 한 줄기를 더 파고들게 만들고, 큐는 같은 거리의 후보를 넓게 펼쳐 보게 만듭니다. 이 감각을 잡고 나면 DFS와 BFS 차이도 훨씬 덜 헷갈립니다.
선택 기준
스택 신호
- 가장 최근 작업부터 되돌려야 하는가
- 지금 하던 맥락으로 다시 돌아와야 하는가
- 깊게 들어갔다가 직전 분기점으로 복귀해야 하는가
- 중첩된 호출이나 괄호처럼 닫는 순서가 역순이어야 하는가
대표 예시는 콜 스택, undo, DFS, 괄호 검사입니다.
큐 신호
- 먼저 들어온 요청부터 처리해야 공정한가
- 대기 중인 작업을 순서대로 흘려야 하는가
- 같은 거리의 후보를 먼저 훑어야 하는가
- 생산자와 소비자 사이에 대기열이 필요한가
대표 예시는 프린터 대기열, 메시지 처리, BFS, 작업 스케줄링의 기본 대기열입니다.
자주 헷갈리는 점
- FIFO와 LIFO를 외웠다고 끝났다고 생각하기 쉽다. 하지만 실제로는 왜 그 순서가 자연스러운지를 이해해야 문제에서 떠올릴 수 있다.
- 큐는 무조건 공정하고 스택은 무조건 비효율적이라고 생각하기 쉽다. 둘 중 무엇이 더 좋다가 아니라 흐름에 맞는 구조가 무엇인가가 더 중요하다.
- DFS와 BFS를 알고리즘 이름으로만 외우고 그 아래 자료구조 감각을 놓치기 쉽다. DFS가 왜 스택인지, BFS가 왜 큐인지 이해하면 훨씬 덜 헷갈린다.
마무리
스택과 큐 차이는 결국 암기 문제가 아닙니다. 스택은 최근 맥락부터 꺼내야 할 때 자연스럽고, 큐는 기다린 순서대로 흘려야 할 때 자연스럽습니다. 그래서 함수 호출, undo, DFS에서는 스택 감각이 잘 맞고, 메시지 처리, 작업 대기열, BFS에서는 큐 감각이 잘 맞습니다.
이 작업은 최근 것부터 되감아야 하는가, 아니면 먼저 온 것부터 흘려야 하는가? 이 질문에 답이 나오면 스택과 큐도 거의 같이 따라옵니다.
같이 보면 좋은 글
DFS와 BFS는 언제 다르게 써야 할까: 그래프 탐색을 문제 풀이 관점에서 비교
