> [!abstract] Introduction
> 놀이기구에서 줄을 서면 가장 먼저 선 사람이 가장 먼저 입장합니다. 이런 상황을 컴퓨터 프로그램으로 구현할 때 우리는 큐*Queue*라는 자료구조를 사용합니다.
# 핵심 연산
큐의 가장 핵심적인 특징은 먼저 들어간 자료가 먼저 나온다는*First-In-First-Out, FIFO* 것이다.
![[queueConcept.svg]]
그래서 어떤 자료구조를 큐라고 부르기 위해서는 어떤 원소 $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)$이지만 배열 앞쪽이 낭비된다.
![[circularQueue.svg]]
원형 큐*circular queue*는 이 트레이드오프를 동시에 해결한다. 나머지(`%`) 연산으로 인덱스를 순환시켜 빈 공간을 재활용하면서도 $O(1)$을 유지한다.
```python
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()`연산을 수행하며, 노드 할당/해제 비용이 있지만, 중간에 사용자가 직접 크기를 바꿀 필요가 없다는 장점이 있다.
![[linkedListQueue.svg]]
### Python `collections.deque`
Python 표준 라이브러리의 `collections.deque`는 양쪽 끝에서 $O(1)$ 삽입/삭제를 지원하는 양방향 큐*double-ended queue, deque*다. 큐로도, 스택으로도 쓸 수 있어 가장 실용적인 선택이다.
```python
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|스택]]*Stack*은 LIFO*Last-In, First-Out* 정책을 따르는 자료구조로, 큐와 정반대의 순서로 원소를 꺼낸다. [[Depth-First Search|깊이 우선 탐색]]에서 사용된다. [[Priority Queue|우선순위 큐]]*Priority Queue*는 큐의 변형으로, 먼저 들어온 원소 대신 우선순위가 가장 높은 원소를 먼저 꺼낸다. 내부적으로 [[Heap|힙]]*Heap*을 사용하기 때문에 $O(\log n)$에 삽입과 추출을 수행한다. 또한 양방향 큐는*deque*은 앞뒤 양쪽에서 삽입과 삭제가 가능한 일반화된 큐다. 큐는 [[Breadth-First Search|너비 우선 탐색]]에서 탐색 경계*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.