[Java] PriorityQueue(우선순위 큐) 사용하기

Queue vs PriorityQueue

1. Queue(큐)
   1) 데이터를 가로로 쌓는 자료구조
   2) FIFO(First In First Out | 선입선출) : 줄을 선 순서대로 먼저 처리됨! ▼
   

   

2. PriorityQueue(우선순위 큐)
   1) 데이터를 가로로 쌓는 것은 동일
   2) 선입선출X, 우선순위를 먼저 결정한 후 우선순위가 높은 엘리먼트부터 처리

---

PriorityQueue 특징

1. 우선순위 큐에 넣을 객체는 필수적으로 Comparable Interface를 구현해야 함 (우선순위 조건 만드는 것!)
2. PriorityQueue가 자동으로 높은 우선순위 요소를 먼저 꺼내어 처리
3. 힙을 이용하여 구현되어 이진트리 구조로 이루어짐
4. 힙으로 구성되어 시간 복잡도는 O(NLogN)
5. 우선순위를 중요시해야 하는 상황에서 사용됨 (ex. 응급실)

---

PriorityQueue 사용하는 방법

🧩 PriorityQueue 선언

import java.util.PriorityQueue;
import java.util.Collections;

// 낮은 숫자가 우선순위 - int형
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

// 높은 숫자가 우선순위 - int형
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

// String 형도 마찬가지! <Integer 대신 String>

🧩 PriorityQueue 메소드

1. 값 넣기, 값 추가 - add(), offer()

priorityQueue.add(1);		// priorityQueue 값 1 추가
priorityQueue.add(2);		// priorityQueue 값 2 추가
priorityQueue.offer(3);		// priorityQueue 값 3 추가

• 삽입에 성공하면 true 반환
• 큐에 여유 공간이 없어 삽입 실패시 IllegalStateException 발생

이미지 출처 : https://coding-factory.tistory.com/603

2. 값 삭제 - poll(), remove()

priorityQueue.poll();		// 첫번째 값 반환 후 제거
priorityQueue.remove();		// 첫번째 값 제거

• 우선순위가 가장 높은 값이 제거 됨!
• poll()은 우선순위 큐가 비어있을 때 null 반환

이미지 출처 : https://coding-factory.tistory.com/603

2-1. PriorityQueue 전체 초기화 - clear()

priorityQueue.clear();		// 초기화

• Queue의 모든 요소가 제거 됨!

3. 값 출력 - peek()

priorityQueue.peek(); 		// 우선순위가 가장 높은 값 출력

• Comparable Interface를 거치며 정해진 우선순위 기준으로 가장 높은 값 출력

---

PriorityQueue 예시

// int형 PriorityQueue 선언
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

priorityQueue.add(1);		// priorityQueue 값 1 추가
priorityQueue.add(2);		// priorityQueue 값 2 추가
priorityQueue.offer(3);		// priorityQueue 값 3 추가

priorityQueue.peek(); 		// 가장 작은 숫자인 1 반환

참고 : https://coding-factory.tistory.com/603