자바_Priority Queue

1. 우선순위 큐(Priority Queue)란?

: 일반적으로 큐는 앞선 포스팅에서도 볼 수 있듯이, 데이터를 일시적으로 쌓아두기 위한 자료구조로 FIFO(First In First Out)의 구조, 즉 먼저 들어온 데이터가 먼저 나가는 구조를 가진다. 오늘 살펴볼 PriorityQueue는 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 요소가 먼저 나가는 자료구조이다. 

 

2. 사용 방법

자바에서 우선순위 큐 라이브러리를 사용하고 싶다면 java.util.PriorityQueue 를 import 하고 Queue<Element> queue = new Queue<>()와 같은 형식으로 선언하면 된다. 오늘 포스팅에서는 지난 번과 마찬가지로 import가 아닌 직접 구현해 보도록 하겠다. 5개 짜리 배열을 만들고 그 안에 값을 넣는데, 이때 Human 클래스의 compareTo 함수를 기준으로, 즉 키가 큰 순서대로 삽입하는 방식이다.

 

[Human.java]

public class Human implements Comparable<Human>{

	private String name = "";
	private double height = 0.0;
	private double weight = 0.0;
	
	
	public Human(String _name, double _height, double _weight) {
		this.name = _name;
		this.height = _height;
		this.weight = _weight;
	}
	
	public void printAll() {
		System.out.println(
				this.name + ": " + 
				this.height + "cm / " + 
				this.weight + "kg");
	}
	
	public int compareTo(Human _human) {
		// 키가 큰 순서대로 리스트에 집어넣음
		if(this.height < _human.height) return 1;
		else if (this.height > _human.height) return -1;
		else return 0;
	}
}

 

[MyPriorityQueue.java]

public class MyPriorityQueue {
    private Human arr[] = new Human[5];
    
    
    public void add(Human _human) {
    	// 카운트가 배열의 크기보다 같거나 크면 Overflow!! 출력
        if (count() >= arr.length) {
            System.out.println("Overflow!!");
            return;
        }
        
        // 삽입할 자리 찾기
        int insertIdx = 0;
        for (int i = 0; i < arr.length; ++i) {
            if (arr[i] != null) {
                if (arr[i].compareTo(_human) == 1) {
                	insertIdx = i;
                	break; // 여기서 break를 안 걸어주면 삽입할 인덱스를 찾기 위한 검사가
                		   // 배열 끝까지 계속 돌아가기 때문에 정렬이 제대로 안 됨
                }
                else ++insertIdx;
            }
        }
        
        // 삽입할 자리가 비워져 있지 않다면 자리 만들기
        if (arr[insertIdx] != null) {
            for (int i = arr.length - 1; i > insertIdx; --i) {
                arr[i] = arr[i - 1];
            }
        }
        
        // 삽입
        arr[insertIdx] = _human;
    }
    
    public int count() {
        int cnt = 0;
        for (int i = 0; i < arr.length; ++i)
            if (arr[i] != null) ++cnt;
        return cnt;
    }
    
    public void printAll() {
        for (int i = 0; i < arr.length; ++i) {
            if (arr[i] == null)
                System.out.println("arr[" + i + "] is Null");
            else                
                arr[i].printAll();
        }
    }
}

 

[Main.java]

import java.util.PriorityQueue;

public class Main {

	public static void main(String[] args) {
    
        MyPriorityQueue myHumans = new MyPriorityQueue();
            myHumans.add(new Human("kim", 180, 90));
            myHumans.add(new Human("lim", 200, 75));
            myHumans.add(new Human("ma", 150, 68));
            myHumans.add(new Human("lee", 183, 93));
            myHumans.add(new Human("choi", 167, 50));
            myHumans.add(new Human("kang", 203, 101));
            myHumans.printAll();	
	}
}

 

 

출력값은 다음과 같다.