비선형 자료구조 - Priority Queue

우선순위 큐 (Priority Queue)

우선 순위가 높은 데이터가 먼저 나옴 (≠ FIFO)

• 모든 데이터에 우선순위가 있음
• Deque시, 우선순위가 높은 순으로 나감
• 우선 순위가 같은 경우는 FIFO

enqueue, dequeue

최소 힙 및 최대 힙의 삽입 삭제와 같음

구현

배열, 연결 리스트, 힙

연결리스트를 이용한 우선순위 큐 구현

public static void enqueue(LinkedList<Integer> list, int data) {
    int idx = list.size();
    for (int i = 0; i <  list.size(); i++) {
        if (list.get(i) > data){
            idx = i;
            break;
        }
    }
    list.add(idx, data);
}

public static Integer dequeue(LinkedList<Integer> list) {
    if (list.size() == 0){
        return null;
    }
    int data = list.get(0);
    list.remove(0);

    return data;
}

Java제공 라이브러리 이용

나이 순으로 오름차순 또는 내림차순 정렬

객체 생성

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

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

Override

@Override
public int compareTo(Person o) {
    //1 : 변경 x
    // -1 : 변경 O

    //새롭게 추가하는 데이터가 더 적을 때 변경 ( 적은값이 위로 올가가고 오름차순 정렬)
    return this.age >= o.age ? 1 : -1;

    //새롭게 추가하는 데이터가 더 클 떄 (큰값이 위로 올라가고 내림차순 정렬)
    return this.age >= o.age ? -1 : 1;

}

값 추가

	public static void solution(String[] name, int[] age) {
        PriorityQueue<Person> pq = new PriorityQueue<>();

        for (int i = 0; i < name.length; i++) {
            pq.offer(new Person(name[i], age[i]));
        }
        System.out.println("== 실체 출력 순서 ==");
        while (!pq.isEmpty()){
            Person p = pq.poll();
            System.out.println(p.name + " " + p.age);
        }

    }
    
     public static void main(String[] args) {
        String[] name = {"A", "B", "C", "D", "E"};
        int[] age = {30, 20, 45, 62, 35};

        solution(name, age);
	}

Override X

PriorityQueue<Person> pq2 = new PriorityQueue<>(
       (Person p1, Person p2) -> p1.age >= p2.age ? 1 : -1);

        for (int i = 0; i < name.length; i++) {
            pq2.offer(new Person(name[i], age[i]));
        }

        while (!pq2.isEmpty()){
            Person p = pq2.poll();
            System.out.println(p.name + " " + p.age);
        }

문자열 오름차순 출력

public static void solution(String[] name, int[] age) {
        //오름차순
        PriorityQueue<Person2> pq = new PriorityQueue<>((Person2 p1, Person2 p2) -> p1.name.compareTo(p2.name));
        //내림차순
        PriorityQueue<Person2> pq = new PriorityQueue<>((Person2 p1, Person2 p2) -> p2.name.compareTo(p1.name));

        for (int i = 0; i < name.length; i++) {
            pq.offer(new Person2(name[i], age[i]));
        }
        while (!pq.isEmpty()){
            Person2 p = pq.poll();
            System.out.println(p.name + " " + p.age);
        }
    }

    public static void main(String[] args) {
        String[] name = {"A", "B", "C", "D", "E"};
        int[] age = {30, 20, 45, 62, 35};

        solution(name, age);
    }