[JAVA] PriorityQueue 우선순위 큐 사용법

 

1. PriorityQueue 란? 

 일반적인 큐는 먼저 들어간 데이터가 먼저 나가는 구조인 FIFO 형식의 자료구조입니다.  반면에 우선순위 큐의 경우 들어가는 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다.  우선순위 큐의 경우 힙 자료구조를 통해서 구현될 수 있습니다. ( 또한 다른 자료구조를 통해서 구현될 수 있음 )

 

 

 

2. PriorityQueue 선언 방법

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

3. 기본적인 메소드

• add() :  　    우선순위 큐에 원소를 추가. 큐가 꽉 찬 경우 에러 발생
• offer()  :       우선순위 큐에 원소를 추가. 값 추가 실패 시 false를 반환
• poll() :         우선순위 큐에서 첫 번째 값을 반환하고  제거, 비어있으면 null 반환
• remove() :   우선순위 큐에서 첫 번째 값을 반환하고  제거, 비어있으면 에러 발생
• isEmpty() :   우선순위 큐에서 첫 번째 값을 반환하고  제거, 비어있으면 에러 발생
• clear() :       우선순위 큐를 초기화
• size() :         우선순위 큐에 포함되어 있는 원소의 수를 반환

 

 

4.  PriorityQueue 기본적인 사용방법

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

import java.util.PriorityQueue;   public class Example {     public static void main(String[] args) {           // 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)         PriorityQueue<Integer> pQ = new PriorityQueue<>();           pQ.offer(1);    // pQ에 원소 1 추가         pQ.offer(6);    // pQ에 원소 6 추가         pQ.offer(2);    // pQ에 원소 2 추가                  // pQ가 비어있면: true, 그렇지 않으면 : false         while(!pQ.isEmpty()) {             // pQ에 첫 번째 값을 반환하고 제거, 비어있다면 null 반환             System.out.println("pQ.poll() = " + pQ.poll());         }       } }

 

 

pQ.poll() = 1
pQ.poll() = 2
pQ.poll() = 6

5. PriorityQueue 클래스 객체 우선순위 정의하기

 

 위 예제와 같이 정수형을 우선순위 큐에 넣고 꺼내고자 할 때는 기본적으로 정의된 우선순위에 따라서 가장 작은 값이 나옵니다. 그렇다면 객체를 우선순위 큐에 넣고 이를 꺼낼 때는 우선순위를 어떻게 판단을 할까요? 또한 우선순위를 정의하고 싶을 때는 어떻게 해야 될까요? 이에 대한 방법을 살펴보도록 하겠습니다.

 

 

import java.util.PriorityQueue;
public class Example {
    private class Student {
        int mathScore; // 수학점수
        int engScore;  // 영어점수
        Student(int mathScore, int engScore){
            this.mathScore = mathScore;
            this.engScore = engScore;
        }
    }
    public static void main(String[] args) {
        PriorityQueue<Student> pQ = new PriorityQueue<>();
    }
}

 

5 - 1.  PriorityQueue 클래스 객체 우선순위 정의하기 방법 

 

import java.util.Comparator;
import java.util.PriorityQueue;
 
class Student {
    int mathScore; // 수학점수
    int engScore;  // 영어점수
 
    public Student(int mathScore, int engScore){
        this.mathScore = mathScore;
        this.engScore = engScore;
    }
}
// 클래스 객체의 우선순위를 위한 클래스
class StudentComparator implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        if (o1.mathScore == o2.mathScore) {
            return o2.engScore - o1.engScore;
        } else {
            return o1.mathScore - o2.mathScore;
        }
    }
}
 
public class Example {
 
    public static void main(String[] args) {
 
        // 클래스 객체에 대한 우선순위 기준 제공
        PriorityQueue<Student> pQ = new PriorityQueue<>(1, new StudentComparator());
 
        pQ.offer(new Student(70, 50));  // 우선순위 큐에 클래스 객체를 추가
        pQ.offer(new Student(60, 50));  // 우선순위 큐에 클래스 객체를 추가
        pQ.offer(new Student(70, 40));  // 우선순위 큐에 클래스 객체를 추가
 
        while (!pQ.isEmpty()) {
            Student s = pQ.poll();
            System.out.printf("Student\'s MathScore and engScore: %d, %d \n", s.mathScore, s.engScore);
        }
    }
}

 

 

Student's MathScore and engScore: 60, 50 
Student's MathScore and engScore: 70, 50 
Student's MathScore and engScore: 70, 40 

1. 수학점수가 낮은 학생이 우선순위가 더 높다
2. 수학점수가 같은 경우 영어점수가 높은 학생이 우선순위가 더 높다.

 

참고자료

---

https://coding-factory.tistory.com/603

https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html