PriorityQueue

개념

PriorityQueue는 인터페이스로 Queue를 implements 받으며,

Queue처럼 FIFO(First In First Out)의 구조를 갖긴 하지만,

내부적으로 우선순위를 정하여 그 우선 순위가 높은 데이터를 먼저 내보내는 자료구조이다.

 

이러한 우선순위 큐는 Heap을 이용하여 구현하는데,

데이터 삽입 시, 최대값이 우선순위인 큐를 최대힙 , 최소값이 우선순위인 큐를 최소힙이라고 한다.

 

때문에 우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야한다는 특징이 있다.

 

 

 

 

우선 순위 큐의 선언

queue interface를 상속받고 있지만, 구현체인 PriorityQueue 내부적으로 더많은 기능을 제공하므로

PriorityQueue를 선언하는 것이 일반적이다.

// 우선순위가 낮은 int형 priorityQueue 선언
PriorityQueue<Integer> pqLow = new PriorityQueue<>();

// 우선순위가 높은 int형 priorityQueue 선언
PriorityQueue<Integer> pqHigh = new PriorityQueue<>(Collections.reverseOrder());

 

CRUD

Create : add(), offer()

pqLow.add(1);
pqLow.add(3);
pqLow.add(5);
pqLow.offer(4);
pqLow.add(2);

 

 

Read: peek(), element()

우선순위 큐의 우선순위에 따라 다르게 동작한다.

 

pqLow.add(1);
pqLow.add(3);
pqLow.add(5);
pqLow.offer(4);
pqLow.add(2);
System.out.println("pqLow = " + pqLow);
System.out.println("pqLow.peek() = " + pqLow.peek());
System.out.println("pqLow.element() = " + pqLow.element());

pqHigh.add(1);
pqHigh.add(3);
pqHigh.add(5);
pqHigh.add(4);
pqHigh.add(2);
System.out.println("pqLow = " + pqHigh);
System.out.println("pqHigh.peek() = " + pqHigh.peek());
System.out.println("pqHigh.element() = " + pqHigh.element());

결과
> pqLow.peek() = 1
> pqLow.element() = 1
> pqHigh.peek() = 5
> pqHigh.element() = 5

peek() : 값을 반환, 값을 제거하지 않는다. 큐가 비어있으면, null 리턴!

element() : 값을 반환, 값을 제거하지 않는다. 큐가 비어있으면, 예외발생!

 

 

 

Update → X

 

Delete: remove(), poll(), clear()

remove(), poll() 은 우선순위대로 제거를 하면서 해당요소를 반환하지만, 

remove()는 queue에 값이 비어있다면, 예외를 발생시키고,

poll()은 null을 리턴시킨다는 점이 다르다.

또한 clear()의 경우, 모든 요소의 값을 지운다.