[자료구조] 비선형 자료구조 : 우선순위 큐

우선순위 큐(Priority Queue)

일반적인 큐(Queue) : FIFO(First In, First Out)의 형식, 먼저 들어온 것이 먼저 나가는 형식의 자료구조

우선순위 큐(Priority Queue) : 우선순위가 존재하며, 우선순위가 높은 것 부터 나가고, 동일한 우선순위에서는 FIFO의 형식의 자료구조

 

우선순위 큐 구현에 자주 사용: 배열, 연결리스트, 힙(Heap)

우선순위 큐의 복잡도

복잡도 측면에서 힙(Heap)을 자주 사용함

 

 

Queue에서의 함수

- enqueue() : 데이터를 입력하는 함수

- dequeue() : 데이터를 출력하는 함수

큐에서의 enqueue와 dequeue의 구조

 

 

 

java에서 우선순위 큐를 구현

// 비선형 자료구조 - 우선순위 큐
// 연결 리스트를 이용한 우선순위 큐
// 자바 기본 PriorityQueue

import java.util.*;

public class Main {
	// enqueue 구현
    public static void enqueue(LinkedList<Integer> list, int data) {
        int idx = list.size(); // data의 인덱스
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) > data) { // 우선순위가 높은지 확인
                idx = i;
                break;
            }
        }
        list.add(idx, data);
    }
	
    // dequeue 구현
    public static Integer dequeue(LinkedList<Integer> list) {
        if (list.size() == 0){
            return null;
        }
        int data = list.get(0); // 인덱스가 0인 것부터 출력하기
        list.remove(0);
        return data;
    }
}

 

 

 

연습문제1. 나이 순으로 오츰차순 또는 내림차순 출력하기(with 이름)

방법1. compareTo() 메소드 구현, compareTo()를 이용하여 age에 대한 비교를 실시한 후에 우선순위 큐를 출력하기(Priority Queue에 poll())

 

compareTo() : 두 개의 값을 비교하여 int 값으로 반환해주는 함수

- int compareTo(NumberSubClass referenceName)

- int compareTo(String anotherString)

- 주로 숫자와 문자열 비교에 사용

숫자의 비교 : 1(크다), 0(같다), -1(작다) 반환

문자열의 비교: 0(같다), 그 외 양수/음수 (문자열 길이의 차이 출력 or 아스키 코드 상의 차이 출력)

 

poll() : 큐의 첫번째 요소를 삭제(및 반환)해주는 함수, 만약 큐가 비어있으면 null 반환

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 o) {
        // 1: 변경 안 함
        // -1: 변경 함

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

        // 내림차순의 코드
        return this.age >= o.age ? -1: 1;
    }
}

public class Practice1 {
    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])); // queue의 offer : 데이터를 넣어주는 것임
        }

        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);
        
	}
}

 

 

방법2.

import java.util.PriorityQueue;

class Person { // 우선 사람에 대한 정보를 담은 Person class를 구현
    String name;
    int age;

    public Person(String name, int age) { // 생성자 생성
        this.name = name;
        this.age = age;
    }
}

public class Practice1 {
    public static void main(String[] args) {
        String[] name = {"A", "B", "C", "D", "E"}; // 사람들의 이름
        int[] age = {30, 20, 45, 62, 35}; // 각각의 사람들에 대한 이름

        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);
        }
    }
}

 

 

실행 결과 

 

연습문제2. 문자열 사전식 오름차순 (이름의 문자 기준으로)

방법. 

 

// Practice 2
// 문자열 사전식 오름차순

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

class Person2 {
    String name;
    int age;

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

public class Practice2 {
    public static void solution(String[] name, int[] age) {
        PriorityQueue<Person2> pq = new PriorityQueue<Person2>(
                (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) {
        PriorityQueue<Person2> pq = new PriorityQueue<>((Person2 p1, Person2 p2) -> p1.name.compareTo(p2.name));

        String[] name = {"A", "B", "C", "D", "E"};
        int[] age = {30, 20, 45, 62, 35};

        solution(name, age);
    }
}

 

실행 결과