우선순위큐(PriorityQueue)

1. PriorityQueue 란?

일반적인 큐는 먼저 들어간 데이터가 먼저 나가는 구조인 FIFO 형식의 자료구조입니다.

반면에 우선순위 큐의 경우 들어가는 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다.

우선순위 큐의 경우 힙 자료구조를 통해서 구현될 수 있습니다. ( 또한 다른 자료구조를 통해서 구현될 수 있음 )

2. PriorityQueue 선언 방법

// 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>();
 
// 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());

3. 기본적인 메소드

add() :  　    우선순위 큐에 원소를 추가. 큐가 꽉 찬 경우 에러 발생
offer()  :       우선순위 큐에 원소를 추가. 값 추가 실패 시 false를 반환
poll() :         우선순위 큐에서 첫 번째 값을 반환하고  제거, 비어있으면 null 반환
remove() :   우선순위 큐에서 첫 번째 값을 반환하고  제거, 비어있으면 에러 발생
isEmpty() :   우선순위 큐에서 첫 번째 값을 반환하고  제거, 비어있으면 에러 발생
clear() :       우선순위 큐를 초기화
size() :         우선순위 큐에 포함되어 있는 원소의 수를 반환

4. PriorityQueue 기본적인 사용방법

import java.util.PriorityQueue;
 
public class Example {
    public static void main(String[] args) {
 
        // 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
 
        pQ.offer(1);    // pQ에 원소 1 추가
        pQ.offer(6);    // pQ에 원소 6 추가
        pQ.offer(2);    // pQ에 원소 2 추가
        
        // pQ가 비어있면: true, 그렇지 않으면 : false
        while(!pQ.isEmpty()) {
            // pQ에 첫 번째 값을 반환하고 제거, 비어있다면 null 반환
            System.out.println("pQ.poll() = " + pQ.poll());
        }
 
    }
}

우선순위큐를 이용한 최소힙/최대힙