큐

🎯 학습 목표

이 강을 마치면 큐(queue)의 FIFO 원리를 설명하고, 파이썬에서 collections.deque로 큐와 덱을 구현할 수 있습니다. 그리고 왜 리스트로 큐를 만들면 안 되는지를 복잡도로 설명하고, 큐가 답이 되는 문제 유형을 알아보게 됩니다.

큐는 24강 BFS(너비 우선 탐색)의 핵심 도구입니다. 여기서 덱을 익혀 두면 그래프 단원이 훨씬 수월해집니다.

💡 FIFO — 먼저 넣은 것이 먼저 나온다

큐는 한쪽으로 넣고 반대쪽으로 빼는 자료구조입니다. 먼저 들어간 것이 먼저 나오므로 FIFO(First In, First Out)라고 합니다. 줄 서기와 같습니다.

스택과 큐의 차이

  [스택 · LIFO]              [큐 · FIFO]

     ↓ push  ↑ pop            ↓ enqueue
   ┌────────────┐            ┌──────────────┐
   │  3         │            │ 1  2  3      │
   │  2         │            └──────────────┘
   │  1         │              ↑ dequeue
   └────────────┘
   넣고 빼는 곳이 같다        넣는 곳과 빼는 곳이 반대

  push 1,2,3 후 pop          enqueue 1,2,3 후 dequeue
   → 3, 2, 1 순서             → 1, 2, 3 순서

  ▲ 큐가 쓰이는 곳
   · 순서대로 처리하는 작업 대기열
   · 프린터 인쇄 대기
   · BFS — 가까운 곳부터 차례로 탐색 (24강)
   · 캐시·버퍼

큐의 기본 연산은 두 가지입니다.

연산	의미	덱으로는	복잡도
enqueue	뒤에 넣기	q.append(x)	O(1)
dequeue	앞에서 빼기	q.popleft()	O(1)
맨 앞 보기	빼지 않고 확인	q[0]	O(1)
비었는지	-	not q	O(1)

📖 리스트로 큐를 만들면 안 되는 이유

파이썬 리스트로도 큐를 흉내 낼 수는 있습니다. append로 넣고 pop(0)으로 빼면 됩니다. 그런데 이것이 시간 초과의 단골 원인입니다.

왜 pop(0) 이 느린가  (3강 복습)

  [1, 2, 3, 4, 5] 에서 pop(0) 을 하면

  1을 꺼낸 뒤, 나머지를 전부 한 칸씩 앞으로 당긴다
     _ │ 2 │ 3 │ 4 │ 5
     ←───────────────      4개 이동

  → 한 번의 pop(0) 이 O(n)
  → n개를 전부 꺼내면 O(n²)

  덱은 어떻게 O(1)인가

  덱은 내부적으로 여러 블록을 연결한 구조라
  양쪽 끝을 가리키는 위치만 옮기면 된다.
  원소를 이동시키지 않는다.

     [앞 포인터] 1 2 3 4 5 [뒤 포인터]
      ↑ popleft 는 이 포인터만 한 칸 옮긴다

  n = 100,000 일 때 (예시)
   list  + pop(0)   : 약 50억 번의 원소 이동
   deque + popleft(): 약 10만 번의 포인터 이동

  ▲ 결론
    큐가 필요하면 무조건 deque 를 쓴다.
    코딩 테스트에서 BFS 를 list 로 구현하면
    로직이 맞아도 시간 초과가 난다.

참고로 파이썬 표준 라이브러리에는 queue.Queue도 있습니다. 다만 이것은 여러 스레드가 안전하게 쓰도록 잠금 처리가 들어 있어 단일 스레드 알고리즘 문제에서는 덱보다 느립니다. 코딩 테스트에서는 collections.deque를 쓰세요.

덱(deque)은 "double-ended queue"의 줄임말로 양쪽 끝 모두에서 O(1)로 넣고 뺄 수 있는 자료구조입니다. 큐로도 쓸 수 있고 스택으로도 쓸 수 있습니다.

메서드	동작	복잡도
append(x)	오른쪽에 추가	O(1)
appendleft(x)	왼쪽에 추가	O(1)
pop()	오른쪽에서 제거	O(1)
popleft()	왼쪽에서 제거	O(1)
d[i]	인덱스 접근	O(n) ← 주의

마지막 줄이 덱의 유일한 약점입니다. 중간 인덱스 접근은 리스트보다 느립니다. 양 끝만 쓸 때 덱을, 임의 접근이 필요하면 리스트를 쓰는 것이 원칙입니다.

💻 실전 예제 — 큐와 회전

덱의 두 가지 대표 활용을 보겠습니다.

from collections import deque


def josephus(n, k):
    """1~n번이 원으로 서서 k번째마다 제거될 때 순서 반환"""
    q = deque(range(1, n + 1))
    result = []
    while q:
        q.rotate(-(k - 1))        # k-1명을 뒤로 보낸다
        result.append(q.popleft())  # k번째 사람 제거
    return result


def sliding_window_max(nums, k):
    """크기 k 창을 밀며 각 구간의 최댓값 → O(n)"""
    q = deque()                   # 값이 아니라 '인덱스'를 담는다
    answer = []
    for i, num in enumerate(nums):
        # ① 창을 벗어난 인덱스는 왼쪽에서 버린다
        if q and q[0] <= i - k:
            q.popleft()
        # ② 새 값보다 작은 값들은 쓸모없으므로 오른쪽에서 버린다
        while q and nums[q[-1]] < num:
            q.pop()
        q.append(i)
        if i >= k - 1:
            answer.append(nums[q[0]])   # 맨 앞이 항상 최댓값
    return answer


print(josephus(7, 3))                       # [3, 6, 2, 7, 5, 1, 4]
print(sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

코드를 줄 단위로 보겠습니다.

• deque(range(1, n + 1)) — 1부터 n까지를 덱으로 만듭니다. 리스트처럼 초기값을 넣을 수 있습니다.
• q.rotate(-(k - 1)) — 덱을 회전시킵니다. 음수는 왼쪽으로 밀어 앞의 원소를 뒤로 보냅니다. 원형 구조를 다룰 때 매우 편리한 기능이고, 리스트에는 없습니다.
• q.popleft() — 회전 후 맨 앞에 온 사람이 k번째가 됩니다. 그 사람을 제거합니다.
• enumerate(nums) — 인덱스와 값을 동시에 꺼냅니다. for i in range(len(nums))보다 간결합니다.
• if q and q[0] <= i - k — 슬라이딩 윈도우에서 창 밖으로 나간 인덱스를 버립니다. q가 비었는지 먼저 확인해야 오류가 나지 않습니다.
• while q and nums[q[-1]] < num — 핵심입니다. 새로 들어온 값보다 작은 값은 앞으로 절대 최댓값이 될 수 없으므로 뒤에서 버립니다. 그 결과 덱은 항상 내림차순을 유지하고, 맨 앞이 곧 최댓값이 됩니다.
• 각 인덱스는 한 번 들어가고 최대 한 번 나오므로, 이중 반복문처럼 보여도 전체는 O(n)입니다. 매 구간마다 max()를 호출하는 O(n × k) 방식보다 훨씬 빠릅니다.

두 번째 예제는 12강 슬라이딩 윈도우에서 다시 다룹니다. 여기서는 덱을 쓰면 최댓값 관리를 O(1)에 할 수 있다는 점만 확인하면 충분합니다.

⚠️ 자주 하는 실수

첫째, BFS를 리스트로 구현합니다. 이 강에서 가장 중요한 경고입니다. queue = []로 시작해 queue.pop(0)을 쓰면 로직이 완벽해도 시간 초과가 납니다. from collections import deque를 습관처럼 먼저 쓰세요.

둘째, 덱에 인덱스로 자주 접근합니다. d[i]는 O(n)입니다. 반복문 안에서 중간 인덱스를 훑어야 한다면 덱이 아니라 리스트가 맞습니다.

셋째, 빈 덱에서 꺼냅니다. popleft()도 비어 있으면 오류입니다. while q:나 if q and ...로 반드시 확인하세요. 특히 and의 왼쪽에 q를 두는 순서가 중요합니다. 파이썬은 왼쪽이 거짓이면 오른쪽을 평가하지 않기 때문입니다.

넷째, 큐에 넣을 때가 아니라 꺼낼 때 방문 처리를 합니다. BFS에서 흔한 실수입니다. 꺼낼 때 표시하면 같은 원소가 큐에 여러 번 들어가 메모리와 시간이 폭증합니다. 넣는 순간 방문 표시가 원칙입니다. 24강에서 자세히 다룹니다.

다섯째, maxlen을 모르고 직접 관리합니다. deque(maxlen=k)로 만들면 크기가 k를 넘을 때 반대쪽이 자동으로 밀려 나갑니다. 최근 k개만 유지하는 문제에서 코드가 크게 줄어듭니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	큐는 FIFO — 먼저 넣은 것이 먼저
2	파이썬 큐는 collections.deque
3	pop(0)은 O(n), popleft()는 O(1)
4	덱은 양쪽 끝 모두 O(1) — 스택으로도 쓸 수 있다
5	덱의 중간 인덱스 접근은 O(n)
6	rotate()로 원형 구조를 쉽게 다룬다
7	BFS는 반드시 덱으로

지금 해 볼 것은 같은 작업을 list.pop(0)과 deque.popleft()로 각각 10만 번 돌려 시간을 재 보는 것입니다. 3강 예제 코드를 조금만 고치면 됩니다. 체감하면 다시는 리스트로 큐를 만들지 않게 됩니다.

다음 7강 「해시(딕셔너리)」에서는 평균 O(1) 조회의 원리를 다룹니다. 1강에서 "집합이 왜 빠른가"를 결과로만 봤다면, 이번에는 해시 함수가 어떻게 위치를 계산하는지를 들여다봅니다.

📚 참고 자료

• collections.deque — Python 공식 문서
• Using Lists as Queues — Python 공식 문서
• queue — A synchronized queue class — Python 공식 문서