큐란?
큐(Queue)는 먼저 들어온 것이 먼저 나가는(FIFO, First-In-First-Out) 자료구조입니다. 매표소 앞에 줄을 선 사람들을 떠올리면 됩니다 — 가장 먼저 줄을 선 사람이 가장 먼저 표를 삽니다.
뒤로 넣는 연산을 enqueue, 앞에서 빼는 연산을 dequeue라고 합니다. BFS(너비 우선 탐색), 작업 대기열, 프린터 큐, 네트워크 버퍼 등 "도착한 순서대로 처리"가 필요한 곳마다 등장합니다.
스택과의 차이
| 스택(Stack) | 큐(Queue) | |
|---|---|---|
| 규칙 | LIFO(후입선출) | FIFO(선입선출) |
| 넣기 | push(맨 위) | enqueue(뒤) |
| 빼기 | pop(맨 위) | dequeue(앞) |
스택은 "마지막에 쌓은 것"부터, 큐는 "가장 먼저 넣은 것"부터 나옵니다.
핵심은 원형 큐(circular queue)
배열로 큐를 만들 때 가장 흔한 함정은 앞에서 빼면서 나머지를 한 칸씩 당기는 것입니다. 이러면 dequeue가 O(n)이 됩니다.
해법은 앞(front)·뒤(rear) 인덱스를 따로 두고, 끝에 도달하면 0으로 돌아오게 하는 원형 큐입니다. 실제로 원소를 옮기지 않고 인덱스만 (i + 1) % capacity로 굴리면 enqueue·dequeue가 모두 O(1)이 됩니다.
동작 원리
1단계. front = rear = 0, 크기 0으로 시작합니다.
2단계. enqueue(x): arr[rear] = x 후 rear = (rear + 1) % cap, 크기 +1. (가득 찼으면 거부)
3단계. dequeue(): arr[front]를 반환하고 front = (front + 1) % cap, 크기 -1. (비었으면 거부)
4단계. 가득참/빔 구분: front와 rear만으로는 둘을 구분하기 어려워 크기(size) 변수를 따로 두는 것이 안전합니다.
알고노트 시각화는 front·rear 포인터가 원형으로 도는 모습과 큐가 차고 비는 과정을 보여줍니다.
시간복잡도와 공간복잡도
| 연산 | 복잡도 |
|---|---|
| enqueue / dequeue | O(1) |
| 앞 원소 확인(peek) | O(1) |
| 공간 | O(n) |
예시로 따라가기
용량 3짜리 원형 큐:
- •enqueue A, B → [A, B, _], front=0, rear=2
- •dequeue → A 반환, front=1
- •enqueue C, D → C는 인덱스2, D는
(3)%3=0자리로 → [D, B, C], 인덱스가 원형으로 감김
먼저 넣은 A·B가 먼저 나오는 순서가 그대로 유지됩니다.
자주 하는 실수
- •앞에서 shift:
arr.shift()같은 연산은 O(n). 큐엔 front 인덱스나 원형 큐, 또는 덱(deque)을 쓰세요. - •빈 큐 처리: dequeue 전에 비었는지 확인하지 않으면 잘못된 값을 읽습니다.
- •가득참 판정: size 변수 없이 front==rear만 보면 "가득참"과 "빔"을 헷갈립니다.
알고노트에서 직접 확인하세요
원소가 뒤로 들어가고 앞에서 나가며 front·rear 포인터가 원형으로 도는 과정을 알고노트에서 단계별로 확인할 수 있습니다.