[JAVA] PriorityQueue - 우선순위 큐

기존에 큐에 대해서 다룬적이 있었는데, 이번 주차 알고리즘은 '그래프'! 였다!

그래프 이론에 대해 공부하다가 우선순위 큐에 대해 알아야할 것 같아서 따로 빠르게 정리해보고자 한다!

 

01. PriorityQueue란?

• 일반적인 큐의 구조 FIFO(First In First Out)를 가짐
• 대신, 들어온 순서대로 나가는 것이 아닌 우선순위를 먼저 결정하고 높은 데이터가 먼저 나가는 자료구조

* 우선순위큐에 저장할 객체는 Comparable Interface를 구현해야한다

->이때 comparaTo method를 오바라이드하여 구현해줘야한다!

이 부분에서 우선순위 조건을 리턴해주면, 해당 조건으로 우선순위가 적용되도록 객체를 추출해주는 방식!

02. PriorityQueue 선언 및 메소드

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

 

*메소드는 아래와 같다.

• add() : 큐에 원소 추가, 큐가 꽉 차면 에러발생
• offer(): 큐에 원소 추가. 실패시 false 반환
• poll(): 큐에 맨 첫번째 값 반환 후 제거, 비어있으면 null 반환
• remove(): 큐에 첫번째 값 반환 후 제거, 비어있으면 에러발생
• isEmpty(): 큐에 첫번째 값 반환 후 제거, 비어있으면 에러발생 <- 보통 요거로 while문과 함께 사용
• clear(): 큐 초기화
• size(): 큐에 포함된 원소 갯수 반환

 

03. 예제

PriorityQueue<Integer> pq = new PriorityQueue<>();
 
pq.offer(3);    // pQ에 원소 3 추가
pq.offer(4);    // pQ에 원소 4 추가
pq.offer(1);    // pQ에 원소 1 추가
        
// pq가 비어있면: true, 그렇지 않으면 : false
while(!pq.isEmpty()) {
    // pq 첫 번째 값을 반환하고 제거, 비어있다면 null 반환
    System.out.println("pq.poll() = " + pq.poll());
}

 

아래와 같이 1,3,4 순으로 나오는걸 확인할 수 있음!!

//출력
pq.poll() = 1
pq.poll() = 3
pq.poll() = 4

 

04. 응용

기본값이 작은 숫자 이고, 내가 원한 객체를 원하는 대로 우선순위를 바꾸고 싶다면, Comparable 인터페이스를 구현해야하는데, 

 

class Node implements Comparable<Node>{
	int idx // 노드
    int cost;  // 비용
    
    Node(int idx, int cost){
        this.idx = idx;
        this.cost = cost;
    }
    
    //비용으로 우선순위 정하기
    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.cost, other.cost); 
    }
    
    //출력을 위한 오버라이드
    @Override 
    public String toString() {
        return "Node{" + "idx=" + idx + ", cost=" + cost + '}';
    }
   
}
public static void main(String[] args) {
    PriorityQueue<Node> pq = new PriorityQueue<>();
}

 

위처럼 초기화를 해주고, 

public class Example {
    public static void main(String[] args) {
        PriorityQueue<Student> pQ = new PriorityQueue<>();
        
        pq.offer(new Node(1, 10));
        pq.offer(new Node(2, 5));
        pq.offer(new Node(3, 20));

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
      }
   }
}

 

+)

//혹은 바로 이렇게 적용시켜도 된다
PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.cost, o2.cost));

 

<출력>

Node{idx=2, cost=5}
Node{idx=1, cost=10}
Node{idx=3, cost=20}

 

 

+)숫자형 비교:

Integer.compareTo(a,b) 혹은 a.compareTo(b)

a>b : 1, a=b : 0, a<b: -1

 

문자열 비교:

기준형과 비교대상이 아예 같으면 : 0

다르면-> 글자수 만큼 반환