자바로 정리한 우선순위큐(PriorityQueue)

큐는 자료구조 형식이 선입선출(FIFO) 이다.

말 그대로 먼저 입력된 자료가 먼저 출력된다.

큐를 이해하는 방법은 줄서기를 생각하면 된다.

먼저 줄을 기다린 사람이 표를 끊거나 개인 용무를 볼 수 있다.

나중에 온 사람은 당연히 자기 순번까지 기다려야 하는게 인지상정.

하지만 우선순위 큐(Priority Queue)는 다른다. 

들어온 순서에 상관 없이 우선순위가 높은 데이터가 먼저 출력이 된다는 말이다. 

고양시에서 강남까지 가는 방법 (대중교통, 자가용, 도보, 자전거) 의 방식이 있다.

대중교통은 1시간 10분 정도 걸리고

자가용은 45분

도보는 6시간 40분 

자전거는 2시간 5분 걸린다.

여기서 시간이 제일 적게 걸리는 순서로 정렬해보면 자가용, 대중교통, 자전거, 도보 순이다.

우선순위큐에 저장한뒤 하나씩 데이터를 추출하면 자가용, 대중교통, 자전거, 도보 순으로 추출이 된다.

하지만 우선순위 큐가 아닌 큐 라면 대중교통 자가용 도보 자전거 순으로 추출될 것이다. 

소스를 보면서 우선순위 큐에 대해서 알아보자.

---

class Vehicle implements Comparable<Vehicle>{
    private String name;
    private int time;
    
    public Vehicle(String name, int time) {
        this.name = name;
        this.time = time;
    }
    public String getName() {
        return this.name;
    }
    public int getTime() {
        return this.time;
    }
    
    @Override
    public int compareTo(Vehicle target) {
        // 자신의 값이 작으면 -1
        // 자신의 값과 같으면 0
        // 자신보다 값이 크면 1
        if(this.time < target.getTime()) return -1;
        else if(this.time > target.getTime()) return 1;
        return 0;
    }
}

Vehicle 이라는 클래스를 만들었다. 

자바에서 PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable 인터페이스를 구현해야한다.

Comparable 인터페이스를 구현하면 compareTo라는 메서드를 override 하게 되고 저기에 우선순위 조건을 리턴해주면 PriorityQueue 가 알아서 우선순위가 높은 객체를 추출 해준다. 

목표는 시간이 작은 순서기 때문에 오름차순으로 작성을 하였다. 

만약 시간이 오래걸리는 방식으로 우선순위 큐를 작성하고 싶다면 리턴 값을 서로 바꿔주면 된다.

Vehicle 클래스 소스를 다 만들었으니 이제 우선순위 큐에 저장한뒤 하나하나 추출해보겠다.

import java.util.PriorityQueue;
 
public class Priority_Queue {
 
    public static void main(String[] args) {
        PriorityQueue<Vehicle> pQueue = new PriorityQueue<Vehicle>();
        
        pQueue.offer(new Vehicle("대중교통", 70));
        pQueue.offer(new Vehicle("자가용", 45));
        pQueue.offer(new Vehicle("도보", 400));
        pQueue.offer(new Vehicle("자전거", 125));
        
        while(!pQueue.isEmpty()) {
            Vehicle v = pQueue.poll();
            System.out.println(v.getName() + " 시간 :" + v.getTime());
        }
    }
 
}

소스를 보게 되면 pQueue 이름의 PriorityQueue를 생성했고 pQueue에 offer로 Vehicle 객체를 저장했다.

저장한것을 while문을 돌면서 하나씩 추출해보면 우선순위가 높은 시간의 오름차순으로 데이터가 추출되는것을 알 수 있다.

자가용 시간 :45

대중교통 시간 :70

자전거 시간 :125

도보 시간 :400