[Queue]우선순위 큐

우선순위 큐 : priorityQueue<E>

1. 큐는 FIFO(First In First Out) 형식의 자료구조이다.

2. 우선순위 큐는 거기서 먼저 들어오는 데이터가 아니라 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조

3. 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있다.

4. 내부 구조가 힙으로 구성되어 있어 O(NlogN)의 시간복잡도를 갖는다.

 

사용법

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

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

동작

삽입 - .add() / offer()

priorityQueueLowest.add(1);
priorityQueueLowest.add(10);
priorityQueueLowest.offer(100);

priorityQueueHighest.add(1);
priorityQueueHighest.add(10);
priorityQueueHighest.offer(100);

*add() - boolean add(E e) 형태로 정의되며, 큐에 요소를 추가 , 성공적으로 큐에 추가하면 항상 true를 반환합니다. 만약 용량이 제한된 경우에도 큐에 추가되지 않을 경우 예외(IllegalStateException)를 던진다.

 

*offer() - boolean offer(E e) 형태로 정의되며, 큐에 요소를 추가, 성공적으로 큐에 추가하면 true를 반환하고, 큐가 용량 제한 등으로 인해 요소를 추가할 수 없으면 false를 반환

 

용량 제한이 있는 경우에는 offer() 메서드를 사용하여 요소를 추가하는 것이 안전하며, 용량 제한이 없는 경우에는 두 메서드 모두 사용할 수 있다.

 

삭제 - .romove() / poll() / clear()

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

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

// 초기화
priorityQueueLowest.clear();

 

꺼내기 - peek() / element()

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

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

객체를 저장하는 경우 우선순위 조절

Comparable 인터페이스 구현:

• 저장하려는 객체가 Comparable 인터페이스를 구현하도록 만듭니다.
• Comparable 인터페이스는 compareTo() 메서드를 구현해야 하며, 해당 메서드에서 객체의 우선순위를 기준으로 비교 및 정렬 로직을 구현합니다.
• 우선순위 큐는 Comparable 인터페이스를 사용하여 객체들의 우선순위를 비교하여 저장하고 정렬합니다.

import java.util.PriorityQueue;

class Person implements Comparable<Person> {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Person other) {
        // 나이(age)를 기준으로 비교하여 정렬
        return Integer.compare(this.age, other.age);
    }
    //또는
    @Override
    public int compareTo(Person other) {
        // 나이(age)를 기준으로 비교하여 정렬 음수일 경우 현재 객체가 비교대상보다 더 높은 우선순위 
        return this.age - other.age;
    }

    @Override
    public String toString() {
        return name + " (" + age + " years old)";
    }
}

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Person> priorityQueue = new PriorityQueue<>();
        priorityQueue.add(new Person("Alice", 30));
        priorityQueue.add(new Person("Bob", 25));
        priorityQueue.add(new Person("Charlie", 35));

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

Comparator 객체 사용:

• 저장하려는 객체가 Comparable 인터페이스를 구현하지 않거나, 기존 정렬 방식과 다른 우선순위를 적용하고 싶을 때, Comparator 객체를 사용합니다.
• Comparator는 compare() 메서드를 구현해야 하며, 해당 메서드에서 객체의 우선순위를 기준으로 비교 및 정렬 로직을 구현합니다.
• 우선순위 큐를 생성할 때, Comparator 객체를 인자로 넘겨서 우선순위를 변경할 수 있습니다.

import java.util.PriorityQueue;
import java.util.Comparator;

class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return name + " (" + age + " years old)";
    }
}

public class Main {
    public static void main(String[] args) {
        // Comparator를 사용하여 나이(age)를 기준으로 우선순위 변경
        PriorityQueue<Person> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(p -> p.age));
        priorityQueue.add(new Person("Alice", 30));
        priorityQueue.add(new Person("Bob", 25));
        priorityQueue.add(new Person("Charlie", 35));

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