우선순위 큐(PriorityQueue)에 대하여

우선순위 큐(PriorityQueue) 란?

일반적으로 큐는 선입선출구조인 FIFO형식의 자료구조이다.

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

 

우선순위 큐는 보통 힙의 자료구조를 통해서 구현하기 때문에 힙에 대해 알고계시는 것이 좋습니다.

힙에 대한 정리글 : https://dodledd.tistory.com/105

힙과 힙 정렬 알고리즘

 

우선순위 큐 사용 법

자바에서는 우선순위 큐를 Queue인터페이스에서 상속받아 PriorityQueue라는 클래스를 지원한다.

(때문에 큐 인터페이스에서 정의된 메소드들도 사용할 수 있습니다.)

 

 

선언부

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

 

 

메소드

• add() : 우선순위 큐에 원소를 추가합니다. (큐가 full인 경우 에러를 발생합니다)
• offer() : 우선순위 큐에 원소를 추가합니다. (큐가 full인 경우 false를 반환합니다)
• poll() : 우선순위 큐에서 첫 번째 값을 반환하고 제거 합니다. (큐가 비어있으면 null반환합니다)
• remove() : 우선순위 큐에서 첫 번째 값을 반환하고 제거 합니다. (큐가 비어있으면 에러를 발생합니다.)
• isEmpty() : 우선순위 큐가 비어있는지 검사. (큐가 비어있다면 true, 비어있지 않다면 false)
• clear() : 우선순위 큐 초기화
• size() : 우선순위 큐에 포함되어 있는 원소의 수를 반환합니다

 

그럼 우선순위를 우리 멋대로 바꾸고 싶을 땐 어떻게 해야할까요?

 

이건 백준 11286번 절댓값 힙을 보면서 알아보겠습니다.

 

우선순위만 커스텀하는 코드를 먼저 보면

PriorityQueue<Integer> pQ = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                int absA = Math.abs(a);
                int absB = Math.abs(b);
                if (absA == absB) {
                    return a - b; // 절댓값이 같으면 원래 값으로 비교
                } else {
                    return absA - absB; // 절댓값으로 비교
                }
            }
        });

@Override해서 compare 메소드를 다시 재정의 해줍니다.

참고로 compare은 매개 변수 2개를 받아 비교를하고 compareTo는 매개 변수 하나만을 받아서 비교합니다.

 

그럼 전체적인 코드를 보고 마무리하겠습니다!

package src.week2;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

public class S11286 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(bf.readLine());
		
		PriorityQueue<Integer> pQ = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                int absA = Math.abs(a);
                int absB = Math.abs(b);
                if (absA == absB) {
                    return a - b; // 절댓값이 같으면 원래 값으로 비교
                } else {
                    return absA - absB; // 절댓값으로 비교
                }
            }
        });
		
		for(int i = 0; i < n ; i++) {
			int x = Integer.parseInt(bf.readLine());
			
			if(x != 0) {
				pQ.add(x);
			}else {
				if(pQ.isEmpty()) {
					System.out.println(0);
				} else {
					System.out.println(pQ.poll());
				}
			}
		}

	}

}