이번에는 Priority Queue에 대해서 공부를 해보았습니다.

Priority Queue

일반적으로 Queue라는 자료구조는 선입선출(First-In-First-Out)의 대기열 규칙을 갖고 있습니다. 즉, 큐에 삽입될 때의 시간이 큐에서의 순서를 결정하게 됩니다.
그러나 우선순위 큐는 입력 시간이 아닌 다른 조건으로 큐내에서의 순서를 결정할 수 있는데, 이 때 List에서 배운 Comparator 인터페이스가 큐 내에서의 순서를 결정하는 역할을 하게 됩니다.

사용법

import.java.util.PriorityQueue를 import하여 사용합니다.

사용법은 Queue와 동일한 메소드를 사용합니다.

1
2
3
4
5
// 기본 생성자. 객체의 기본 비교 CompareTo를 사용한다. 
PriorityQueue<Integer> pa = new PriorityQueue<Integer>();

// 기본 배열크기, 비교함수를 인자로 받는 생성자.
PriorityQueue<Integer> pa = new PriorityQueue<Integer>();

메소드

삽입 - offer,add

큐에 새로운 데이터를 삽입하는 작업을 의미하며, 이는 리스트의 끝 부분을 가리키는 rear에서 발생하며 데이터가 삽입될 때 하나 증가시킨 후 새로운 데이터를 삽입합니다.

제거 - poll,remove

큐에서 데이터를 제거하는 작업을 의미하며 이는 항상 front에서 발생합니다. front값이 rear를 추월하게 되면 더이상 제거할 데이터가 없는 상태 즉, 자료가 하나도 없는 빈 큐를 의미합니다.

poll은 큐가 비어있다면 null을 반환
remove는 큐가 비어있다면 예외 발생

읽기 - peek,element

큐에서 front가 가리키는 데이터를 읽는 작업을 peek이라 합니다. 데이터를 제거하지 않고 읽는 작업만 수행하므로 front값을 변경시키지 않습니다.
peek은 큐가 비어있다면 null을 반환
element은 큐가 비어있다면 예외 발생

사용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

PriorityQueue<Prisoner> pq = new PriorityQueue<Prisoner>();
		
Prisoner ps1 = new Prisoner("박보검",20);
Prisoner ps2 = new Prisoner("하정우",3);
Prisoner ps3 = new Prisoner("이준기",50);
Prisoner ps4 = new Prisoner("강하늘",10);
Prisoner ps5 = new Prisoner("박서준",2);
		
pq.offer(ps1);
pq.offer(ps2);
pq.offer(ps3);
pq.offer(ps4);
pq.offer(ps5);

System.out.println("사이즈:"+pq.size());
		
	while(!pq.isEmpty()){
		Prisoner prisoner = pq.poll();
		System.out.println(prisoner.name);
	}
		
		
System.out.println("----------Reverse");
		
PriorityQueue<Prisoner> reversedPriorityQueue = new PriorityQueue<Prisoner>(pq.size(), Collections.reverseOrder());
reversedPriorityQueue.addAll(pq);
		
	while(!reversedPriorityQueue.isEmpty()){
		Prisoner prisoner2 = reversedPriorityQueue.poll();
		System.out.println(prisoner2.name);
	}

	}
}

class Prisoner implements Comparable<Prisoner>{
	String name;
	int weight;
	
	public Prisoner(String name, int weight){
		this.name = name;
		this.weight = weight;
	}

	@Override
	public int compareTo(Prisoner ps) {
		if(this.weight>ps.weight){
			return 1;
		}else if(this.weight<ps.weight){
			return -1;
		}
		return 0;
	}
	// 이 상태는 오름차순인데, 
	// Comparable을 구현하고, compareTo 메소드를 사용해서 내림차순을 구현하려면
	// return 하는 값을 바꾸면 된다. 1 대신에 -1을 -1 대신에 1을!!
}

우선순위 큐에서 값을 poll()이라는 함수를 통해서 꺼내게 되면 가장 작은 값부터 꺼낼 수 있게 됩니다.
그 이유는 우선순위 큐는 내부적으로 Natural Ordering에 따라서 정렬하는 큐이기 때문입니다.

1
2
3
4
5
6
7
8
PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>();
        
for (int i =10; i>0; i--)
{
      pQueue.add(i);
}

System. out .println(pQueue.peek());

실제로 위의 예를 실행해보면 peek() 메소드를 통해서 head 에 있는 값을 가져오는데, 10이 아니라 1을 가져오는 것을 확인할 수 있습니다. 그것은 Priority Queue가 natural Ordering에 따라서 정렬하기 때문에 가장 작은 값이 head 부분에 위치하는 것을 알 수 있습니다.
그리고 Priority Queue는 Null을 허용하지 않습니다. Natural Ordering에 기초하고 있기 때문에 정렬할 수 없는 Null은 허용하지 않습니다.