# 핵심 연산

큐의 가장 핵심적인 특징은 먼저 들어간 자료가 먼저 나온다는First-In-First-Out, FIFO 것이다.

그래서 어떤 자료구조를 큐라고 부르기 위해서는 어떤 원소 $x$에 대하여 다음의 네가지 연산을 지원해야 한다.

• enqueue(x) — 원소 $x$를 큐의 뒤쪽rear에 추가한다. $O(1)$.
• dequeue() — 큐의 앞쪽front에서 원소를 꺼내 반환한다. $O(1)$.
• peek() (또는 front()) — 앞쪽 원소를 꺼내지 않고 확인만 한다. $O(1)$.
• is_empty() — 큐가 비어 있는지 확인한다. $O(1)$.

이때 모든 핵심 연산이 $O(1)$이라는 점이 큐의 강점이다.

구현 방법

배열 기반 — 원형 큐

배열로 큐를 구현하면 각각 큐의 앞과 뒤를 가리키는 두 인덱스(아래 코드에서는 front와 rear)를 관리하게 된다. 단순 배열에서 dequeue()를 수행하면 front 앞쪽에 빈 공간이 생기는데, 이를 처리하는 방법은 두 가지다.

1. 남은 원소를 앞으로 이동(shift)시키면 공간 낭비는 없지만 매번 $O(n)$이 든다.
2. 빈 공간을 그대로 방치하면 $O(1)$이지만 배열 앞쪽이 낭비된다.

원형 큐circular queue는 이 트레이드오프를 동시에 해결한다. 나머지(%) 연산으로 인덱스를 순환시켜 빈 공간을 재활용하면서도 $O(1)$을 유지한다.

class CircularQueue:
    def __init__(self, capacity: int):
        self._data = [None] * capacity
        self._front = 0
        self._rear = 0
        self._size = 0
        self._capacity = capacity

    def enqueue(self, x):
        if self._size == self._capacity:
            raise OverflowError("Queue is full")
        self._data[self._rear] = x
        self._rear = (self._rear + 1) % self._capacity
        self._size += 1

    def dequeue(self):
        if self._size == 0:
            raise IndexError("Queue is empty")
        val = self._data[self._front]
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return val

(self._rear + 1) % self._capacity로 인덱스가 배열 끝에 도달하면 다시 0으로 돌아가도록 해 배열 공간을 재활용한다.

연결 리스트 기반

큐를 구현하는 또다른 방법은 연결 리스트Linked List로 구현하는 것이다. 이 방법의 가장 큰 장점은 크기 제한이 없다는 것이다. head 포인터에서 dequeue()연산을 수행하고 tail 포인터에서 enqueue()연산을 수행하며, 노드 할당/해제 비용이 있지만, 중간에 사용자가 직접 크기를 바꿀 필요가 없다는 장점이 있다.

Python collections.deque

Python 표준 라이브러리의 collections.deque는 양쪽 끝에서 $O(1)$ 삽입/삭제를 지원하는 양방향 큐double-ended queue, deque다. 큐로도, 스택으로도 쓸 수 있어 가장 실용적인 선택이다.

from collections import deque

q = deque()
q.append("A")      # enqueue
q.append("B")
q.append("C")
print(q.popleft())  # dequeue → "A"
print(q.popleft())  # "B"

큐와 다른 자료구조의 관계

스택Stack은 LIFOLast-In, First-Out 정책을 따르는 자료구조로, 큐와 정반대의 순서로 원소를 꺼낸다. 깊이 우선 탐색에서 사용된다. 우선순위 큐Priority Queue는 큐의 변형으로, 먼저 들어온 원소 대신 우선순위가 가장 높은 원소를 먼저 꺼낸다. 내부적으로 힙Heap을 사용하기 때문에 $O(\log n)$에 삽입과 추출을 수행한다. 또한 양방향 큐는deque은 앞뒤 양쪽에서 삽입과 삭제가 가능한 일반화된 큐다. 큐는 너비 우선 탐색에서 탐색 경계frontier를 관리하는 데 쓰인다. BFS가 레벨 순서대로 노드를 방문하는 것이 바로 큐 덕분이다. 운영체제에서는 프로세스 스케줄링의 준비 큐ready queue에, 네트워크에서는 라우터의 패킷 버퍼에 큐가 쓰인다. 메시지 큐message queue 시스템(RabbitMQ, Kafka)은 분산 시스템에서 비동기 통신을 구현하는 데 큐 개념을 확장한 것이다.

---

출처

• Cormen, T. H. et al. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press. Chapter 10.1.
• Python Software Foundation (2025) collections.deque. Available at: https://docs.python.org/3/library/collections.html#collections.deque.