먼저 넣은 것을 먼저 꺼내는(FIFO, First-In-First-Out) 자료구조. 줄 서기와 같다.
연산
enqueue(x) / offer(x) — 뒤에 넣기 O(1)
dequeue() / poll() — 앞에서 빼기 O(1)
peek() — 앞을 보기 O(1)
양 끝을 쓴다 — 뒤로 넣고 앞에서 뺀다. 스택과의 결정적 차이다.
배열로 구현하면 생기는 문제와 원형 큐
앞에서 빼면 나머지를 다 당겨야 해서 O(n)이 된다. 그래서 머리와 꼬리 인덱스를 따로 두고, 끝에 닿으면 앞으로 돌아간다.
front rear
↓ ↓
[ _ ][ B ][ C ][ D ][ _ ][ _ ]
└─ front를 옮기기만 하면 O(1)
rear가 끝에 닿으면 → 0번으로 순환 (원형 큐)
rear = (rear + 1) % capacity
ArrayDeque가 정확히 이 방식이다.
변형
| 종류 | 특징 | 자바 |
|---|---|---|
| 덱(Deque) | 양쪽에서 넣고 뺄 수 있음 | ArrayDeque |
| 우선순위 큐 | 넣은 순서가 아니라 우선순위 순으로 나옴 | PriorityQueue(힙 기반) |
| 블로킹 큐 | 비었으면 대기, 꽉 찼으면 대기 | LinkedBlockingQueue |
| 원형 버퍼 | 고정 크기, 꽉 차면 오래된 것을 덮어씀 | 로그 버퍼 등 |
우선순위 큐는 FIFO가 아니다 — 이름에 큐가 붙었지만 힙으로 구현되며 꺼낼 때 가장 우선순위 높은 것이 나온다.
어디에 쓰이나
- BFS — 가까운 곳부터 탐색하려면 먼저 발견한 것을 먼저 처리해야 한다
- 스레드 풀의 작업 큐 — 들어온 순서대로 처리
- 메시지 큐 — 시스템 간 비동기 통신의 기본 모델
- 프로세스 스케줄링 — 라운드 로빈의 준비 큐
- 버퍼링 — 생산 속도와 소비 속도가 다를 때 완충
생산자-소비자 문제
큐가 등장하는 가장 전형적인 동시성 패턴이다.
생산자 ──put──► [ 큐 ] ──take──► 소비자
큐가 비었을 때 소비자는? → 대기해야 한다
큐가 꽉 찼을 때 생산자는? → 대기해야 한다
BlockingQueue가 이 대기를 내부에서 처리해 준다. 직접 만들면
wait/notify나 조건 변수를 써야 하고, 깨우기를 놓치면 영영 멈춘다.
BlockingQueue<Task> q = new LinkedBlockingQueue<>(1000); // 크기 제한
q.put(task); // 꽉 찼으면 대기 → 자연스러운 배압(backpressure)
Task t = q.take(); // 비었으면 대기
크기를 제한하는 것이 중요하다. 무제한 큐는 소비자가 느릴 때 메모리를 다 먹고 OOM으로 끝난다 — 스레드 풀 설정에서 자주 나오는 사고다.