『Java』 Priority Queue

우선순위 큐

 

일반적인 큐(Queue)는 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 구조다. 반면에 우선순위 큐(Priority Queue)는 들어가는 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조다.

 

우선순위 큐 내부의 엘리먼트들은 새로운 요소가 추가되거나 기존 요소가 제거될 때마다 정렬된다.

 

우선순위 큐는 힙(Heap) 자료구조를 통해 구현되며 다른 자료구조를 통해서도 구현될 수 있다.

 

 

선언 방법

Java에서 PriorityQueue는 기본적으로 최소 힙(min-heap) 구조로 작은 숫자가 먼저 나오도록 설계되어 있다.

 

높은 숫자(큰 숫자)가 먼저 나오도록 하려면 Collections.reverseOrder()를 사용하여 최대 힙(max-heap) 구조로 변경할 수 있다.

 

메서드

add(E e)	우선순위 큐에 원소를 추가한다. 큐가 꽉 찬 경우 IllegalStateException이 발생한다.
offer(E e)	우선순위 큐에 원소를 추가한다. 추가에 실패하면 false를 반환한다.
poll()	우선순위 큐에서 첫 번째 값을 반환하고 제거한다. 비어있으면 null을 반환한다.
remove()	우선순위 큐에서 첫 번째 값을 반환하고 제거한다. 비어있으면 NoSuchElementException이 발생한다.
peek()	우선순위 큐에서 첫 번째 값을 반환하지만 제거하지 않는다. 비어있으면 null을 반환한다.
isEmpty()	큐가 비어있는지 여부를 반환한다.
clear()	우선순위 큐를 초기화한다.
size()	우선순위 큐에 포함된 원소의 수를 반환한다.

 

 

사용 방법

 

실행 결과

PriorityQueue는 우선순위에 따라 요소를 자동으로 정렬하여 처리한다.

 

 

클래스 객체 우선순위 정의

정수형 데이터의 경우 기본적으로 숫자의 크기에 따라 우선순위가 결정된다. 하지만 사용자 정의 객체를 우선순위 큐에 넣고자 할 때는 우선순위를 명시적으로 정의해야 한다.

 

예를 들어, Student 클래스의 객체를 우선순위 큐에 넣고 다음과 같은 우선순위를 적용해 보자.

• 수학 점수가 낮은 학생이 우선순위가 높다.
• 수학 점수가 같을 경우 영어 점수가 높은 학생이 우선순위가 높다.

 

Comparator 인터페이스 구현을 통한 우선순위 정의

Comparator 인터페이스를 구현하여 객체의 우선순위를 정의할 수 있다.

 

실행 결과

StudentComparator 클래스에서 compare() 메서드를 구현하여 우선순위를 정의했다.

이 메서드는 우선순위 큐가 내부적으로 객체를 비교할 때 사용된다.

 

 

주의사항

• 우선순위는 스레드로부터 안전하지 않으므로 멀티스레드 환경에서 사용하려면 PriorityBlockingQueue를 사용하는 것이 좋다.
• 우선순위 큐에 null 요소를 추가할 수 없다.
• 우선순위 큐에 요소를 추가한 후 해당 요소의 속성을 변경하면 우선순위가 제대로 유지되지 않을 수 있다.
• 사용자 정의 객체를 우선순위 큐에 넣을 때 Comparable 인터페이스를 구현하여 compareTo() 메서드를 정의하는 방법도 있다.