큐 (Queue)

관련 문제

문제	난이도	핵심
10845번 — 큐	실버 IV	큐 기본 구현
1966번 — 프린터 큐	실버 III	큐 시뮬레이션
18258번 — 큐 2	실버 IV	큐 기본 구현
11286번 — 절댓값 힙	실버 I	우선순위 큐 응용
1927번 — 최소 힙	실버 II	우선순위 큐 기본

---

1. 개념

큐(Queue)는 먼저 넣은 데이터가 먼저 나오는(FIFO, First In First Out) 자료구조다.

먼저 줄 선 사람이 먼저 나간다.

BFS 구현의 핵심 자료구조이며, 순서가 중요한 시뮬레이션 문제에서 자주 사용된다.

offer(1) → offer(2) → offer(3) → poll() → poll() → poll()
[1] → [1,2] → [1,2,3] → [2,3] → [3] → []
반환값:                            1       2       3

---

2. 동작 과정

프린터 큐 예시: 우선순위 [1, 1, 9, 1], 3번째 문서가 몇 번째로 출력되는가?

단계	큐 상태	동작	출력 순서
초기	[(1,1), (1,2), (9,3), (1,4)]	—	—
1	[(1,2), (9,3), (1,4), (1,1)]	1번 앞으로 → 뒤로	—
2	[(9,3), (1,4), (1,1), (1,2)]	2번 앞으로 → 뒤로	—
3	[(1,4), (1,1), (1,2)]	9번(3번 문서) 출력	1번째
4	[(1,1), (1,2)]	4번 출력	2번째
...	...	...	...

---

3. 큐의 종류

종류	특징	Java 구현체
일반 큐	FIFO	ArrayDeque
덱 (Deque)	양쪽 삽입/삭제	ArrayDeque
우선순위 큐	우선순위 높은 것부터	PriorityQueue

---

4. 핵심 포인트 2가지

Java에서 Queue는 ArrayDeque로 구현한다

LinkedList도 Queue를 구현하지만, ArrayDeque가 메모리와 속도 면에서 더 효율적이다.

// ❌ 느린 방식
Queue<Integer> queue = new LinkedList<>();

// ✅ 빠른 방식
Queue<Integer> queue = new ArrayDeque<>();

우선순위 큐는 기본이 최솟값 우선이다

Java의 PriorityQueue는 기본적으로 오름차순(최소 힙) 이다.
최댓값 우선(최대 힙)으로 바꾸려면 Collections.reverseOrder()를 사용한다.

// 최소 힙 (기본)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 최대 힙
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

---

5. 코드

기본 연산

Queue<Integer> queue = new ArrayDeque<>();

queue.offer(1);          // offer: 맨 뒤에 추가
queue.offer(2);
queue.offer(3);

int front = queue.peek();  // peek: 맨 앞 값 확인 (꺼내지 않음) → 1
int val = queue.poll();    // poll: 맨 앞 값 꺼내기 → 1

boolean empty = queue.isEmpty();  // 비어 있는지 확인
int size = queue.size();          // 현재 원소 개수

덱 (Deque) — 양방향 큐

Deque<Integer> deque = new ArrayDeque<>();

deque.offerFirst(1);   // 앞에 추가
deque.offerLast(2);    // 뒤에 추가

int front = deque.peekFirst();  // 앞 값 확인
int back = deque.peekLast();    // 뒤 값 확인

deque.pollFirst();     // 앞에서 꺼내기
deque.pollLast();      // 뒤에서 꺼내기

우선순위 큐

// 기본 — 숫자 최솟값 우선
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);
pq.poll();  // → 1 (가장 작은 값)

// 커스텀 정렬 — 절댓값 기준, 같으면 작은 수 우선
PriorityQueue<Integer> pq2 = new PriorityQueue<>((a, b) -> {
    if (Math.abs(a) != Math.abs(b)) return Math.abs(a) - Math.abs(b);
    return a - b;
});

---

6. 시간복잡도

자료구조	연산	시간복잡도
일반 큐	offer / poll / peek	O(1)
우선순위 큐	offer	O(log N)
우선순위 큐	poll	O(log N)
우선순위 큐	peek	O(1)

우선순위 큐는 내부적으로 힙(Heap)으로 구현되어 삽입/삭제가 O(log N)이다.

---

7. 주의사항

• poll 전에 isEmpty() 확인을 습관화하라. 빈 큐에서 poll하면 null을 반환하고, peek도 마찬가지다. int로 바로 받으면 NullPointerException이 발생한다.
• 우선순위 큐는 전체 정렬이 아니다. poll할 때만 최솟값이 보장되며, 내부 배열을 순서대로 출력하면 정렬된 결과가 나오지 않는다.
• 커스텀 Comparator에서 정수 오버플로우 주의. (a, b) -> a - b 방식은 값 차이가 크면 오버플로우가 날 수 있다. Integer.compare(a, b) 사용을 권장한다.
• 덱을 스택처럼 쓸 때와 큐처럼 쓸 때 메서드를 혼용하지 마라. push/pop(스택)과 offer/poll(큐)을 섞으면 의도치 않은 방향에서 원소가 나올 수 있다.