[Java] PriorityQueue(우선순위 큐) 사용법과 예제

안녕하세요 골드입니다.

 

 

1. PriorityQueue(우선순위 큐)란?

 흔히 아는 Queue는 FIFO(First In First Out) 형식으로 먼저 들어온 데이터를 먼저 방출하는 방식입니다. PriorityQueue는 Queue인터페이스 중의 하나로, 저장 순서에 상관없이 우선순위(Priority)가 높은 것부터 선출하는 것이 특징입니다. 저장공간으로 배열을 사용하고, 각 요소를 힙(heap)이라는 자료구조 형태로 저장합니다. 힙은 이진트리의 한 형태로 가장 큰 값과 가장 작은 값을 빠르게 찾을 수 있다는 장점이 있습니다. 기본적으로 PriorityQueue는 요소에 대한 비교 기준이 존재해야 하고, 비교 기준에 따라 그 우선순위를 결정하게 됩니다.

 

2. PriorityQueue 선언

 PriorityQueue를 생성하고 데이터를 저장한 후 출력하였습니다. 단순히 참조 변수를 출력하게 되면 내부 배열의 순서가 출력되는데 이는 힙 자료구조의 형태가 출력되는 것입니다. 한마디로 단순히 참조 변수를 출력한다면 원하는 결과를 얻지 못할 수도 있습니다. 그렇기 때문에 pq.poll()이라는 메서드를 사용하여 저장된 데이터들을 순서대로 출력하였습니다. int값을 저장하면 컴파일러가 Integer로 문제없게 만들어 줍니다. 또한 Integer는 Number의 자손이기 때문에 비교 기준을 정하지 않아도 자동적으로 오름차순으로 저장되었습니다. 

 이미 선언되어 있는 인터페이스를 사용하여 내림차순으로 쉽게 만들 수 있습니다. Collections.reverseOrder()를 사용하면 값을 출력할 때 반대로 출력됩니다. 혹은 Integer뿐만 아니라 String형식도 저장할 수 있습니다. 저장하는 데이터 형식만 다를 뿐입니다. 

 

3. PriorityQueue 메서드의 종류

 PriorityQueue는 Queue 메서드들과 이름이 95% 같습니다. 

 3-1 추가

 PriorityQueue에 값을 추가하는 방법은 대표적으로 두 가지가 있습니다. add()와 offer()입니다.

 

 add()를 사용하여 추가하는 것은 내부적으로 offer()로 추가됩니다. 결국 둘은 이름만 다르고 같은 메서드입니다. 값을 저장할 때 null을 저장하면 NullPointerException이 발생하기 때문에 null은 저장할 수 없습니다. PriorityQueue를 생성하면 기본 사이즈로 생성되고 만약 사이즈보다 더 많은 값을 저장한다면 자동으로 늘어나게 됩니다.

 

 3- 2 삭제

 삭제와 관련된 메서드 세 가지입니다. poll()은 가장 앞에 있는 데이터를 꺼내서 확인한다고 생각하면 됩니다. remove()는 데이터를 확인하지 않고 그냥 꺼내 버립니다. clear()는 모든 데이터를 초기화합니다. 

 poll()은 데이터를 꺼낸 후 확인하기 때문에 while문이 무한 루프에 빠지지 않고 println()에 값까지 출력되는 것입니다. 모든 데이터가 poll()되면 PriorityQueue에 데이터가 존재하지 않기 때문에 isEmpty()가 true가 되어 while문을 빠져 나옵니다.

 

 3-3 그 외 

 만약 가장 앞에 있는 값을 확인만 하고 싶다면 peek()을 사용할 수 있습니다. peek()은 저장된 데이터 주머니를 살짝 열어서 가장 앞에 있는 값을 확인만 합니다.

 println()으로 1이 출력될 것입니다. peek()은 가장 앞에 있는 값을 확인하는 메서드입니다. 배열의 get()과 같이 사용할 수 없습니다. 

 

 혹은 Iterator 인터페이스를 사용하여 구현할 수도 있습니다.

 

 

---

 알고리즘 문제를 풀다가 PriorityQueue를 구현하였습니다. 예를 들면 문제에서 다양한 문자열에 중복을 허용하여 저장된 배열이 있고 그중 중복이 적은 문자열부터 나열하여 저장된 배열을 구하시오 같은 문제였습니다. [a, b, b, c, c, c,]와 같이 저장되어 있었고 결괏값으로 [a, b, c]를 return 하면 되는 것인데 이 과정에서 PriorityQueue를 사용하면 문제를 좀 더 쉽게 해결할 수 있었습니다.

 

 

여기까지 골드였습니다.

감사합니다.

 

참고자료 : Java의 정석(3rd Edition) 남궁성 지음 도우 출판