**큐(Queue)**는 데이터의 삽입과 삭제가 서로 다른 끝에서 일어나는 선형 자료구조입니다. 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First-In First-Out) 구조를 가집니다.
1. 큐의 핵심 용어와 FIFO 원리
줄 서기(Waiting line)처럼 먼저 들어온 요청이나 데이터가 먼저 처리되는 구조입니다.
- 전단(Front): 데이터가 삭제(출력)되는 위치.
- 후단(Rear): 데이터가 삽입(입력)되는 위치.
- FIFO (First-In First-Out): 먼저 들어간 데이터가 먼저 나오는 방식.
2. 큐의 기본 연산 및 변종 구조
| 구 분 | 핵심 특징 및 연산 |
|---|---|
| 기본 연산 | enqueue(item)(후단 삽입), dequeue()(전단 삭제), peek(), isEmpty() |
| 선형 큐 (Linear Queue) | 배열로 구현 시 삭제 연산 후 앞쪽 공간이 낭비되는 이동 오버헤드 발생 |
| 원형 큐 (Circular Queue) | 배열의 처음과 끝을 연결하여 메모리를 효율적으로 재사용하는 큐 (rear = (rear + 1) % capacity) |
| 덱 (Deque, Double-Ended Queue) | 양쪽 끝(Front, Rear) 모두에서 삽입과 삭제가 가능한 확장 큐 |
| 우선순위 큐 (Priority Queue) | 들어온 순서와 상관없이 데이터의 우선순위에 따라 먼저 출력되는 큐 (보통 힙(Heap)으로 구현) |
3. 원형 큐(Circular Queue)의 구현 원리
선형 큐의 공간 재사용 문제를 극복하기 위해 모듈로 연산(%)을 활용합니다.
class CircularQueue:
def __init__(self, capacity=5):
self.capacity = capacity
self.queue = [None] * capacity
self.front = 0
self.rear = 0
def is_empty(self):
return self.front == self.rear
def is_full(self):
return (self.rear + 1) % self.capacity == self.front
def enqueue(self, item):
if self.is_full():
raise OverflowError("Queue is full")
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = item
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty")
self.front = (self.front + 1) % self.capacity
item = self.queue[self.front]
self.queue[self.front] = None
return item
4. 실무에서의 큐 활용 분야
- 프로세스 및 스케줄링: 운영체제의 CPU 작업 스케줄링(RR 스케줄링), 프린터 인쇄 대기열.
- 네트워크 버퍼: 패킷 수신 대기 버퍼, 비디오 스트리밍 데이터 버퍼링.
- 너비 우선 탐색 (BFS): 그래프 및 트리 탐색 알고리즘에서 방문 예정 노드 관리.
5. 자주 묻는 질문 (Q&A)
Q. 파이썬 리스트로 큐를 사용할 때의 성능상 문제는 무엇인가요?
A. 리스트의 pop(0) 연산은 첫 항목 삭제 후 나머지 $N-1$개 요소를 모두 앞으로 당겨야 하므로 $O(N)$의 시간 복잡도가 소요됩니다. 따라서 $O(1)$ 연산을 보장하는 collections.deque를 사용해야 합니다.