**queue(큐)**는 FIFO(First-In, First-Out, 선입선출) 컬렉션입니다. 원소는 **뒤(back)**에서 추가되고 **앞(front)**에서 제거되며, 줄을 선 사람들과 같습니다.
연산
text
enqueue(1) enqueue(2) enqueue(3) dequeue()->1
front ->[1][2][3]<- back front ->[2][3]<- back
예시
python
from collections import deque
queue = deque()
queue.append('a') # enqueue (뒤)
queue.append('b')
first = queue.popleft() # dequeue (앞) -> 'a'
일반 Python list는 pop(0)을 O(n) 연산으로 만들기 때문에, 양 끝에서 **O(1)**을 얻으려면 deque를 사용하세요.
| 연산 | 시간 (deque) |
|---|---|
| enqueue | O(1) |
| dequeue | O(1) |
| 앞 peek | O(1) |
일반적인 용도
- 작업 / 잡 스케줄링 — 도착 순서대로 작업을 처리함.
- 너비 우선 탐색(BFS) — 노드를 레벨 단위로 방문함.
- 버퍼링 — 생산자/소비자 파이프라인, 프린트 스풀러, 요청 큐.
왜 중요한가
queue는 공정성과 순서를 보장하며, 이는 스케줄러, 메시징 시스템, BFS에 핵심적입니다.
작업을 "도착한 순서대로" 처리해야 할 때마다 queue가 자연스러운 선택입니다.