자바(Java) PriorityQueue

 

PriorityQueue

• 일반적인 큐의 구조 FIFO(First In First Out)를 가짐.
• 단, 우선순위 기준을 정하고 우선순위가 높은 데이터가 먼저 나가는 자료구조.

 

 

 

 

 

특징

• 우선순위의 요소 높은 순으로 처리하는 구조.
  비교가 가능한 기준이 있어야 함. => 따라서 null 값을 허용하지 않음.
• 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어짐.
• 수정이 이루어지면 내부적으로 재정렬을 계속 한다.
• 시간 복잡도는 O(NLogN).

 

 

 

 

 

객체 선언 형식

 

import java.util.PriorityQueue;
import java.util.Collections;

// 오름차순 int 형 우선순위 큐 선언
PriorityQueue<Integer> qL = new PriorityQueue<>();

// 내림차순 int 형 우선순위 큐 선언
PriorityQueue<Integer> qH = new PriorityQueue<>(Collections.reverseOrder());

 

 

 

 

 

메소드 종류

 

1. add / offer (삽입)

 

// add(value) 메서드의 경우, 만약 삽입에 성공하면 true를 반환 
// 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생
qL.add(1);
qL.offer(100);

qH.add(1);
qH.offer(100);

 

 

 

2. poll / remve / peek / element / clear (제거)

 

// 첫번째 값을 반환하고 제거 비어있다면 null
qL.poll();

// 첫번째 값 제거 비어있다면 예외 발생
qL.remove(); 

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 null을 반환
qL.peek();

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 예외 발생
qL.element();

// 초기화
qL.clear();

 

 

 

3. 비교 기준 설정

 

예를 들어, 아래와 같이 숫자와 문자열을 같이 받는 생성자를 만든다고 했을 때

compareTo를 override 하여 우선순위를 정한다.

아래의 경우, 기존의 숫자가 더 크면 양수 반환 / 작으면 음수 반환

 

class GG implements Comparable<GG> {

    private int writeRowNumber;
    private String content;

    public GG(int writeRowNumber, String content) {
        this.writeRowNumber = writeRowNumber;
        this.content = content;
    }

    public int getWriteRowNumber() {
        return this.writeRowNumber;
    }

    public String getContent() {
        return this.content;
    }

    @Override
    public int compareTo(GG gg) {
        if (this.writeRowNumber > gg.getWriteRowNumber())
            return 1;
        else if (this.writeRowNumber < gg.getWriteRowNumber())
            return -1;
        return 0;
    }
}

 

 

 

그래서 위의 기준을 적용한 큐를 아래처럼 사용이 가능하다.

 

  public static void main(String[] args) {

        PriorityQueue<GG> Q = new PriorityQueue<>();

        Q.add(new GG(4, "네번째 순서"));
        Q.add(new GG(2, "두번째 순서"));
        Q.add(new GG(1, "첫번째 순서"));
        Q.add(new GG(3, "세번째 순서"));

        while (!Q.isEmpty()) {
            GG gg = Q.poll();
            System.out.println("순서 : " + gg.getWriteRowNumber() + " / 내용 : " + gg.getContent());
        }
    }
    
    
    
 /* 실행 결과
순서 : 1 / 내용 : 첫번째 순서
순서 : 2 / 내용 : 두번째 순서
순서 : 3 / 내용 : 세번째 순서
순서 : 4 / 내용 : 네번째 순서
 */