큐와 덱 차이는 자료구조 입문에서는 간단해 보이지만, 코딩테스트에서는 의외로 오래 헷갈리는 주제입니다. queue는 FIFO라고 외웠는데 어떤 문제에서는 deque가 더 자연스럽게 나오고, 또 어떤 문제에서는 deque를 써도 되지만 굳이 queue로 좁혀 생각해야 하는 경우가 있기 때문입니다.
이번 글에서는 queue와 deque를 정의로만 구분하지 않고, 문제에서 어떤 신호가 보일 때 deque를 먼저 떠올려야 하는지를 코딩테스트 기준으로 자세히 정리하겠습니다.
queue와 deque를 가장 짧게 구분하면
- queue: 뒤에서 넣고 앞에서 빼는 FIFO 구조
- deque: 양쪽 끝에서 넣고 뺄 수 있는 double-ended queue
정의만 보면 차이가 단순해 보입니다. 하지만 실전에서는 이 차이가 “문제를 어떤 흐름으로 모델링할 수 있는가”를 바꿉니다. queue는 흐름이 한 방향으로 고정된 문제에 강하고, deque는 앞과 뒤를 모두 다뤄야 하는 상황에서 훨씬 자연스럽습니다.
std::queue 설명을 보면 FIFO 흐름이 핵심이라는 점이 분명합니다. 반면 deque는 단순 구현체가 아니라 양끝 제어 자체가 문제 풀이 전략이 되는 경우가 많습니다.
왜 입문자는 queue만으로 충분하다고 느끼기 쉬울까
처음 배우는 대표 예시가 보통 일반 BFS, 프린터 대기열, 작업 순서 처리처럼 순수한 FIFO 문제이기 때문입니다. 그래서 “앞에서 빼고 뒤에 넣으면 되네”라는 감각이 강하게 자리 잡습니다.
문제는 코딩테스트가 항상 순수 FIFO만 요구하지 않는다는 점입니다. 앞 원소를 버리면서 뒤 원소를 넣거나, 비용에 따라 앞과 뒤 중 어디에 넣을지 달라지거나, 양쪽 끝을 번갈아 만지는 순간이 나오면 queue만으로는 사고가 답답해집니다.
deque를 떠올려야 하는 대표 신호
- 양쪽 끝에서 삽입/삭제가 모두 일어난다
- 현재 구간의 앞 원소를 버리고 뒤 원소를 새로 넣는 흐름이 반복된다
- 비용 0과 비용 1처럼 앞/뒤 삽입 우선순위가 갈린다
- 문제를 FIFO 하나로 표현하면 불필요한 이동이나 복잡한 분기가 생긴다
이 네 가지 신호가 보이면 deque 가능성을 먼저 의심하는 편이 좋습니다. 핵심은 “양끝 제어가 문제 모델에 직접 들어가느냐”입니다.
일반 BFS는 왜 queue로 충분할까
일반 BFS는 먼저 방문한 정점을 먼저 꺼내고, 그 정점에서 갈 수 있는 다음 정점을 뒤에 붙이는 구조입니다. 즉 레벨 순서가 중요하고, 이미 들어간 순서를 뒤집을 이유가 거의 없습니다.
from collections import deque
q = deque([start])
visited[start] = True
while q:
cur = q.popleft()
for nxt in graph[cur]:
if not visited[nxt]:
visited[nxt] = True
q.append(nxt)이 코드에서는 deque를 구현체로 쓰더라도 개념은 queue입니다. 앞에서 빼고 뒤에만 넣기 때문입니다. 즉 자료구조 라이브러리로 deque를 쓴다고 해서 문제 자체가 deque 문제인 것은 아닙니다.
BFS 감각은 BFS 문제 풀이 패턴 글에서 더 자세히 연결해 볼 수 있습니다.
0-1 BFS에서는 왜 deque가 자연스러울까
0-1 BFS는 간선 비용이 0 또는 1일 때 쓰는 대표 패턴입니다. 비용이 0이면 같은 우선순위이므로 앞에 넣고, 비용이 1이면 뒤에 넣습니다. 즉 삽입 위치가 값에 따라 달라집니다.
from collections import deque
dq = deque([start])
dist[start] = 0
while dq:
cur = dq.popleft()
for nxt, w in graph[cur]:
nd = dist[cur] + w
if nd < dist[nxt]:
dist[nxt] = nd
if w == 0:
dq.appendleft(nxt)
else:
dq.append(nxt)이 문제를 순수 queue처럼 생각하면 “왜 앞에도 넣어야 하지?”에서 막히기 쉽습니다. 하지만 deque로 보면 훨씬 자연스럽습니다. 즉 데이터 구조를 바꾸면 문제 설명이 더 짧아지는 경우가 있습니다. 그게 좋은 자료구조 선택 신호입니다.
슬라이딩 윈도우에서도 왜 deque 감각이 중요할까
슬라이딩 윈도우는 구간의 오른쪽 끝을 늘리면서, 조건이 깨지면 왼쪽 끝을 줄이는 흐름이 자주 나옵니다. 즉 앞 원소는 빠지고 뒤 원소는 들어오는 식으로 양끝이 동시에 움직입니다.
단순 합만 관리하는 문제라면 투 포인터처럼 인덱스만으로도 충분할 수 있습니다. 하지만 윈도우 안의 최댓값이나 최솟값 후보를 유지하려면 양끝 처리를 잘하는 deque가 훨씬 강력합니다.
슬라이딩 윈도우 감각은 슬라이딩 윈도우 글과 같이 보면 더 분명합니다.
queue와 deque를 헷갈릴 때 스스로 던질 질문
- 삽입 위치가 항상 뒤로 고정되는가?
- 삭제 위치가 항상 앞으로 고정되는가?
- 앞과 뒤를 모두 움직여야 문제 모델이 자연스러운가?
- appendleft 또는 pop 같은 양끝 연산이 나오면 설명이 단순해지는가?
앞의 두 질문이 모두 yes라면 queue 쪽일 가능성이 큽니다. 세 번째와 네 번째 질문이 강하게 yes라면 deque 쪽일 가능성이 큽니다.
실전에서 자주 하는 실수
- deque가 필요한 문제를 억지로 queue 사고방식으로 풀려 한다
- deque를 단순히 queue의 상위호환으로만 본다
- 라이브러리 구현체가 deque라는 이유만으로 문제도 deque 문제라고 착각한다
- 0-1 BFS와 일반 BFS의 차이를 삽입 위치 관점에서 보지 못한다
특히 세 번째 실수가 많습니다. 파이썬에서는 queue 대신 deque를 구현체로 자주 쓰지만, 그게 항상 deque적 사고를 의미하는 것은 아닙니다. 중요한 것은 사용하는 연산의 방향입니다.
마무리
큐와 덱 차이의 핵심은 정의 암기가 아니라, 문제 흐름이 한 방향인지 양끝 제어가 필요한지 구분하는 데 있습니다.
즉 queue는 순수 FIFO 흐름, deque는 양끝 제어가 필요한 흐름으로 이해하면 코딩테스트에서 훨씬 빠르게 떠올릴 수 있습니다.
