우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)란?

---

우선순위 큐(Priority Queue)는 데이터를 저장하고 관리하는 자료구조 중 하나입니다. 일반적인 큐(Queue)와 유사하게 요소를 저장하는 방식으로 FIFO(First In First Out)의 구조를 가집니다.

 

그러나 우선순위 큐(Priority Queue)는 삽입된 순서로 요소를 처리하는 것이 아니라, 우선순위에 따라 정렬되어 우선순위가 높은 요소가 먼저 처리됩니다.

 

 

우선순위 큐(Priority Queue) 특징

• 요소들이 우선순위에 따라 정렬되어 저장된다. 즉 가장 높은 우선순위를 갖는 요소가 가장 먼저 처리된다.
• 내부 요소가 Heap으로 구성되어 이진트리 구조로 이루어져 있다.
• 빠른 삽입과 삭제 연산을 빠르게 수행할 수 있다.
• 시간 복잡도는 0(NLogN)이다.

 

우선순위 큐(Priority Queue) 사용법

---

Priority Queue 선언

import java.util.PriorityQueue;

// 우선순위가 낮은 숫자 순 (default)
PriorityQueue<Element> priorityQueue = new PriorityQueue<>();

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

Java에서 우선순위 큐를 사용하기 위해서 java. util.PriorityQueue 클래스를 import합니다. 우선순위 큐를 별도 설정없이 초기화하면 요소는 기본적으로 오름차순에 따라 정렬됩니다.

 

만약 높은 숫자가 우선순위로 되게 하고 싶다면 선언 시 Collections.reverseOrder() 메서드를 활용합니다.

 

 

Priority Queue 메서드 정리

메서드	설명
add()	요소 추가, 성공시  true 반환 (큐에 여유 공간이 없어 추가할 수 없는 경우 IllealStateException 예외 발생)
offer()	요소 추가, 성공 시 true 반환 (큐에 여유 공간이 없어 추가할 수 없는 경우 false 반환)
poll()	우선순위를 갖는 요소를 반환하고 큐에서 제거 (비어 있다면 null 반환)
remove()	우선순위를 갖는 요소를 반환하고 큐에서 제거 (비어 있다면 NoSuchElementException 예외 발생)
peek()	우선순위 요소를 참조 (값을 꺼내지 않고 그대로 보관)
isEmpty()	큐가 비어있다면 true, 그렇지 않으면 false 반환
clear()	큐 초기화
size()	큐에 포함되어 있는 요소의 수 반환

 

 

값 추가

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

큐에 값을 추가하고 싶다면 add() 또는 offer() 메서드를 사용합니다. 두 메서드 동일한 동작을 수행하나, add() 메서드는 큐의 여유 공간이 없어 추가할 수 없다면 IllegalStateException 예외를 발생시킵니다. 이와 다르게 offer() 메서드는 요소를 추가할 공간이 없는 경우 false를 반환하게 됩니다.

 

 

값 반환 및 삭제

priorityQueue.poll(); // 우선순위 요소를 반환하고 제거 (비워져있다면 null 반환)
priorityQueue.remove(); // 우선순위 요소를 반환하고 제거 (비워져있다면 예외 발생)
priorityQueue.peek(); // 우선순위 요소를 반환

우선순위 큐에서 값을 꺼내고 싶다면 poll() 또는 remove() 메서드를 사용하면 됩니다. 둘다 동일한 동작을 수행하며, 값이 비워져있다면 poll() 메서드는 null를 반환하며, remove() 메서드는 NoSuchElementException 예외가 발생하게됩니다. 이와 다르게 peek() 메서드는 값을 꺼내지 않고 참조만 할 수 있습니다.

 

 

이외 메서드

priorityQueue.clear(); // 큐 초기화
priorityQueue.isEmpty(); // 큐가 비워져있는지 확인 (true/false 반환)
priorityQueue.size(); // 큐에 보관되어 있는 요소의 수