✔️ 한 줄 요약
Queue는 FIFO(First-In-First-Out) 구조를 따르는 자료구조 인터페이스이며,
PriorityQueue는 이를 구현한 클래스 중 하나로 우선순위 기반 정렬 큐를 제공한다.
1. Queue란?
Queue는 선입선출(FIFO) 구조를 따르는 컬렉션으로,
먼저 추가된 요소가 먼저 제거되는 구조를 가진 인터페이스이다.
인터페이스이므로 직접 객체 생성은 불가능하고, LinkedList, PriorityQueue 등 구현체를 사용한다.
Queue<String> queue = new LinkedList<>();
queue.add("A");
queue.add("B");
System.out.println(queue.poll()); // A2. PriorityQueue란?
PriorityQueue는 Queue 인터페이스를 우선순위 기반으로 구현한 클래스다.
즉, 먼저 넣은 순서가 아닌 값의 크기나 지정한 우선순위 기준에 따라 요소가 처리된다.
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(30);
pq.add(10);
pq.add(20);
System.out.println(pq.poll()); // 10위 코드처럼 30 → 10 → 20 순으로 데이터를 넣어도,
우선순위가 가장 높은 값인 10이 먼저 poll()로 꺼내진다.
기본 정렬 방식
기본적으로 오름차순 정렬(Min-Heap) 으로 작동하며,
Comparator.reverseOrder()를 통해 내림차순(Max-Heap)으로 바꿀 수 있다.
// 오름차순 정렬 (기본)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 내림차순 정렬
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); 🔧 내부 구조
Java의 PriorityQueue는 힙(Heap) 자료구조를 기반으로 구현되어 있다.
힙(Heap)은 완전 이진 트리 형태로 구성되며,
요소를 삽입하거나 제거할 때마다 자동으로 우선순위를 유지하도록 정렬된다.
- 기본적인 PriorityQueue는 최소 힙(Min-Heap)이며, 가장 작은 값이 루트에 위치
Comparator.reverseOrder()를 사용하면 최대 힙(Max-Heap)으로 동작 가능
힙은 정렬된 배열이 아니며, 항상 우선순위가 가장 높은 요소만 빠르게 꺼낼 수 있도록 정렬된 트리 구조다.
3. Queue와 PriorityQueue의 주요 메서드
1. offer(E e)
Queue<String> queue = new LinkedList<>();
queue.offer("A"); // 큐에 "A" 추가설명 : 큐의 끝에 요소를 추가한다. 공간이 부족하면 false 반환
시그니처 : boolean offer(E e)
매개변수 : e – 큐에 추가할 요소
사용 상황 : 큐에 안전하게 요소를 추가하고, 실패 시 예외 대신 false를 받고 싶을 때
2. poll()
Queue<String> queue = new LinkedList<>();
queue.offer("A");
String item = queue.poll(); // "A" 반환 및 제거설명 : 큐의 맨 앞 요소를 제거하고 반환한다. 비어 있으면 null 반환
시그니처 : E poll()
매개변수 : 없음
사용 상황 : 큐에서 안전하게 요소를 꺼내고, 비어 있을 경우 null 처리하고 싶을 때
3. remove()
Queue<String> queue = new LinkedList<>();
queue.offer("A");
String item = queue.remove(); // "A" 반환 및 제거설명 : 큐의 맨 앞 요소를 제거하고 반환한다. 비어 있으면 예외 발생
시그니처 : E remove()
매개변수 : 없음
사용 상황 : 큐가 비어 있지 않다고 확신할 수 있을 때, 예외로 처리하고 싶은 경우
4. peek()
Queue<String> queue = new LinkedList<>();
queue.offer("A");
String front = queue.peek(); // "A" 반환, 큐는 그대로설명 : 큐의 맨 앞 요소를 제거하지 않고 반환한다. 비어 있으면 null 반환
시그니처 : E peek()
매개변수 : 없음
사용 상황 : 현재 큐의 앞에 있는 값을 미리 확인하고 싶을 때
5. element()
Queue<String> queue = new LinkedList<>();
queue.offer("A");
String front = queue.element(); // "A" 반환, 큐는 그대로설명 : 큐의 맨 앞 요소를 제거하지 않고 반환한다. 비어 있으면 예외 발생.
시그니처 : E element()
매개변수 : 없음
사용 상황 : 큐가 비어 있지 않을 때, 요소가 반드시 존재해야 할 때
6. isEmpty()
Queue<String> queue = new LinkedList<>();
boolean empty = queue.isEmpty(); // true설명 : 큐가 비어 있는지 여부를 반환한다.
시그니처 : boolean isEmpty()
매개변수 : 없음
사용 상황 : 큐가 비어있는지 확인하고 처리 분기하고 싶을 때
7. size()
Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
int count = queue.size(); // 2설명 : 큐에 현재 저장된 요소의 개수를 반환한다.
시그니처 : int size()
매개변수 : 없음
사용 상황 : 큐의 상태(비어있는지/가득 찼는지 등)를 판단하고자 할 때
4. Queue와 PriorityQueue의 차이점
| 항목 | Queue | PriorityQueue |
|---|---|---|
| 처리 기준 | 순서대로(FIFO) | 우선순위 높은 값부터 |
| 정렬 방식 | 없음 (삽입 순서 유지) | 자동 정렬 (작은 값부터 꺼냄, 힙 기반) |
| null 허용 | 구현체에 따라 가능 (LinkedList는 허용) | X (넣으면 예외 발생) |
| 내부 구조 | 리스트 구조 (LinkedList, ArrayDeque) | 힙(Heap) 구조 |
| 대표 사용처 | BFS, 단순 대기열 | 다익스트라, 작업 우선순위 처리 |
Queue는 요소가 들어온 순서대로(FIFO) 처리되는 반면,
PriorityQueue는 요소의 값에 따라 우선순위가 높은 요소부터 처리된다.
Queue는 LinkedList로 구현될 경우 null 을 추가할 수 있지만,
PriorityQueue는 내부 정렬 로직(Heap 구조) 때문에 null을 추가하면 NullPointerException이 발생하므로 주의해야 한다.
5. 알고리즘 활용 팁
☑️ Queue
-
BFS (너비 우선 탐색)
- 그래프 탐색 알고리즘에서 노드를 순차적으로 방문할 때 사용
- FIFO 구조 덕분에 레벨 단위 탐색이 가능함
- 예시: 미로 탈출, 최소 이동 거리 계산 등
-
작업 대기열 (Task Queue)
- 순차적으로 실행해야 하는 작업을 저장하는 큐
- 예: 웹 요청 처리 순서, 비동기 이벤트 큐
-
Producer-Consumer 패턴
- 멀티스레드 환경에서 BlockingQueue로 안전하게 데이터 전달
- 예: 로그 수집, 메시지 큐 시스템 구현
☑️ PriorityQueue
-
다익스트라 알고리즘 (최단 경로)
- 거리가 가장 짧은 노드를 우선 처리해야 하므로
- 우선순위 큐를 사용해 O(log n)으로 꺼낼 수 있음
-
힙 정렬 (Heap Sort)
- PriorityQueue에 모두 넣고 하나씩 꺼내면 자동 정렬
- 최대 힙: 내림차순 정렬, 최소 힙: 오름차순 정렬
-
시뮬레이션 문제 (우선순위 처리)
- 예: 응급환자 먼저 처리, 문서 인쇄 순서, CPU 스케줄링 등
- 값 외에도 우선순위를 정의하고
Comparator로 커스터마이징 가능
