[JAVA] 우선순위(PriorityQueue) 큐

1. 개요

---

일반적으로 Queue라는 자료구조는 '선입선출'(First-In, First-Out)의 대기열 규칙(queuing discipline)을 가지고 있다. 말그대로 먼저들어온 놈이 먼저 나간다는 것이다.

하지만 JAVA에서 제공하는 'PriorityQueue'는 우선순위를 결정하여 들어온 순서와 상관없이 그 우선순위가 높은 엘리먼트가 나가게 된다. 이제부터 간단한 예제를 통해 알아보겠다.


2. 예제

---

아래와 같은 Prisoner(죄수) 클래스가 있다.

class Prisoner {

    String name;
    int weight; // 형량

    public Prisoner(String name, int weight) {
        super();
        this.name = name;
        this.weight = weight;
    }
}

이 클래스는 'name' 와 'weight(형량)' 의 2가지 필드가 있다. 이 Prisoner 클래스를 PriorityQueue에 넣고, 형량에 따라 큐에서 나오게(출소하게) 하려고 한다.

물론 일반적으로, 형량이 낮으면 먼저 출소하는 것이 인지상정. 이제 이 Prisoner 클래스에 Comparable 인터페이스를 구현 해보자.

class Prisoner implements Comparable<Prisoner> {

    String name;
    int weight; // 형량

    public Prisoner(String name, int weight) {
        super();
        this.name = name;
        this.weight = weight;
    }

    @Override
    public int compareTo(Prisoner target) {
        if (this.weight > target.weight) {
            return 1;
        } else if (this.weight < target.weight) {
            return -1;
        }
        return 0;
    }
}

위에 'Comparable' 인터페이스를 구현한 Prisoner 클래스에 있다. 형량이 낮은 Prisoner 객체를 먼저 꺼내기 위해 compareTo 메소드를 오름차순으로 정렬 되도록 구현하였다.

* PriorityQueue 사용

먼저 테스트 클래스에 'getPriorityQueue' 메소드를 구현한다. 이 메소드는 5개의 'Prisoner' 객체를 생성하여 'PriorityQueue'에 넣고 해당 'PriorityQueue' 객체를 반환한다.

private static PriorityQueue<Prisoner> getPriorityQueue() {

    Prisoner prisoner1 = new Prisoner("james", 5);
    Prisoner prisoner2 = new Prisoner("schofield", 99);
    Prisoner prisoner3 = new Prisoner("alex", 14);
    Prisoner prisoner4 = new Prisoner("silvia", 10);
    Prisoner prisoner5 = new Prisoner("thomson", 1);

    PriorityQueue<Prisoner> priorityQueue = new PriorityQueue<Prisoner>();

    priorityQueue.offer(prisoner1);
    priorityQueue.offer(prisoner2);
    priorityQueue.offer(prisoner3);
    priorityQueue.offer(prisoner4);
    priorityQueue.offer(prisoner5);
    
    return priorityQueue;
}

5명의 죄수 객체를 생성하여 우선순위 큐에 넣었다. 이 죄수 객체들은 각각 형량이 다르다.

만약 'Prisoner' 클래스에 Comparable 인터페이스를 구현하지 않은채 PriorityQueue에 집어넣으면 어떻게 될까? 우선순위 큐의 'offer'는 큐 한쪽 끝에 엘리먼트를 저장하는데, 이때 '다형성'을 이용하여 추가 되는 엘리먼트 객체를 'Comparable' 인터페이스로 'Up Casting' 한다. 하지만 'Comparable' 인터페이스를 구현한 객체가 아니라면 당연히 아래와 같은 에러메시지가 노출 될 것이다.

Exception in thread "main" java.lang.ClassCastException: Prisoner cannot be cast to java.lang.Comparable

이제 main 메소드를 구현하여 돌려보자.

public static void main(String[] args) {

        PriorityQueue<Prisoner> priorityQueue = getPriorityQueue();

        System.out.println("=============== Normal Order");

        while (!priorityQueue.isEmpty()) {
            Prisoner prisoner = priorityQueue.poll();
            System.out.println(prisoner.name);
        }
}

결과 >

=============== Normal Order
thomson
james
silvia
alex
schofield

형량이 낮은 'thomson' 이라는 녀석부터 출소한다. 형량이 '99년'인 schofield는 제일 나중에 나올 것이다.

이것이 우선순위 큐(PriorityQueue) 이다.

* Reversed Order

갑자기 교도소의 정책이 바뀌었다. 교도소장 생일을 맞이하여(.. 억지스럽더라고 걍 넘어가자) 형량이 가장 높은 죄수부터 차례로 출소하게 된것이다. 이럴때는 어떻게 해야할까? 'compareTo' 메소드를 오름차순에서 내림차순으로 바꿔서 구현해야 할까?

기존의 코드를 그대로 두고 Order를 뒤집는 방법이 있다. 아래와 같다.

public static void main(String[] args) {

        PriorityQueue<Prisoner> priorityQueue = getPriorityQueue();

        PriorityQueue<Prisoner> reversedPriorityQueue = 
         new PriorityQueue<Prisoner>(priorityQueue.size(), Collections.reverseOrder());
        reversedPriorityQueue.addAll(priorityQueue);

        System.out.println("=============== Reversed Order!");

        while (!reversedPriorityQueue.isEmpty()) {
            Prisoner prisoner = reversedPriorityQueue.poll();
            System.out.println(prisoner.name);
        }
}

결과 >

=============== Reversed Order!
schofield
alex
silvia
james
thomson

'Collections.reverseOrder()' 메소드를 살펴보면 알겠지만, 두 Camparable 객체를 비교하는 순서를 뒤집은 'Comparator' 객체를 리턴한다. 이로서 'reversedPriorityQueue' 컨테이너가 생성이 되고, 바로 위에 생성한 오름차순의 'priorityQueue' 컨테이너를 'addAll' 하게되면 'reversedPriorityQqueue'의 우선순위 정책으로 인해서 컨테이너 안의 엘리먼트의 우선순위가 뒤바뀐다.

그래서 위와 같은 결과를 도출 하는 것이다.