우선순위 큐(Priority Queue)를 공부하면서

Queue는 먼저 선입선출(FIFO)이라는 특징을 가지는 구조이다. (Stack은 후입선출 - LIFO)

 

그럼 우선순위 큐는?

 

우선순위 큐는 말 그대로 우선순위가 높은 데이터를 먼저 뽑아내는 구조를 말한다.

그럼 여기서 의아할 게 어떤 기준을 가지고 우선순위를 정하는 걸까 싶은데, 단순히 요소의 크기를 우선순위를 잡고 오름차순, 내림차순 정렬을 할 수 있고, 우선순위 큐의 타입을 배열로 지정한다면, 특정 요소의 크기순으로 우선순위 기준을 잡을 수도 있다.

 

Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));

 

(pq라는 우선순위 큐에는 int타입의 1차원 배열이 들어가게 되고, 배열의 1번째 인덱스의 값을 기준으로 정렬이 된다)

 

 

Java에서 제공하는 우선순위 큐는 기본적으로 요소의 오름차순으로 값이 정렬된다.

 

 

우선순위 큐를 구현하는 방법은 많다. 배열, 연결리스트, 힙, 이진탐색트리가 있다.

구현 방법은 많지만, 힙(Heap)이 배열이나 연결리스트에 비해 더 나은 성능을 제공하기 때문에, 일반적으로 우선순위 큐의 구현은 힙이 선호된다. - 참고

 

힙이 무엇인지는 다음 영상으로 쉽게 이해가 가능하다. - 영상

 

 

우선순위 큐에 관한 알고리즘 문제를 풀면서 내가 새롭게 알게 된 내용을 정리하자면 다음과 같다.

 

먼저, 스택과 큐의 메서드에 관해 혼동됐던 부분을 정리하자면

 

• 요소 추가
  • Stack - push(), add()
  • Queue - add(), offer()
• 요소 꺼내기(삭제)
  • Stack - pop(), remove()
  • Queue - poll(), remove()
• 요소 꺼내기(삭제 x)
  • peek()

 

여기서, 우선순위 큐를 사용하면서 add()와 offer()의 차이에 대해 궁금해졌었다.

 

일단 두 메서드의 인터페이스 차이가 있다. add()는 Collections, offer()는 Queue 인터페이스에서 사용할 수 있는 메서드이다.

용량이 제한된 큐의 경우, add()는 요소를 추가할 수 없을 때, 항상 true를 반환하고 상황에 따라 5가지 종류의 예외를 던진다. offer()는 요소를 추가할 수 없을 때는 아예 false를 반환해버린다. - 참고1, 참고2

 

Queue에 저장되는 요소의 개수에는 제한이 있지만, 충분히 개수가 많기 때문에 고려하지 않아도 된다. 직접 제한 용량을 설정해서 Queue를 생성하는 방법도 존재한다. - 참고

 

 

그리고, remove()에 대해 처음 알게 되었다. 요소를 꺼내는 건 Queue에서 가장 먼저 추가된 요소를 poll()을 통해 꺼내는 방법 외에는 다른 특정 요소를 꺼내는 건 못하는 줄 알았다.

알아보니, 매개변수를 넣고 remove() 메서드를 이용하면 Queue에서 매개변수와 같은 값을 가지는 특정 요소를 꺼내는 순서에 상관없이 제거가 가능하다. 매개변수를 넣지 않고 사용하면, poll()과 같은 기능을 수행한다.

 

다음과 같은 상황에서는 어떻게 결과가 나올까?

 

Queue<Integer> q = new LinkedList<>();

q.add(10);
q.add(1);
q.add(10);

q.remove(10);

System.out.println(q);

 

매개변수 10을 넣고 remove()를 수행한 결과는 [1, 10] 이다.

즉, 10과 일치하는 모든 요소가 아닌 가장 먼저 추가된 10이 지워지는 것이다.

 

 

이 remove() 메서드는 Stack에도 있지만, Queue와는 조금 다르다. 반환타입과 함께 살펴보자.

 

Stack - 참고

• remove(Object o) - boolean
  Stack에서 매개변수로 넣은 값과 동일한 요소를 제거하고, 제거에 성공하면 true 반환
  String 타입의 Stack에서는 문제 없이 사용할 수 있지만, Integer 타입의 Stack의 경우에는 매개변수로 들어가는 값이 인덱스 값, 즉 아래의 메서드로 작용되는 것 같으니, 주의해서 사용하면 될 것 같다. - 참고
  
  
• remove(int index) - Integer
  Stack에서 해당 인덱스에 있는 요소를 지우고, 지워진 요소를 반환한다.
  
  

Queue - 참고

• remove() - Integer
  Queue에서 가장 먼저 들어간 요소에 대해 지운다. poll()과 같은 기능을 수행하지만, Queue가 비어 있을 경우에는 NoSuchElementException 예외를 던진다. - 참고
  
  
• remove(Object o) - boolean
  Java Docs에는 나와있지 않은 것 같지만, IDE 환경에서 확인해본 결과, 매개 변수와 동일한 특정 요소를 지우고, 성공하면 true를 반환한다.
  Integer 타입의 Stack에서의 remove() 메서드는 인덱스 값을 가지는 메서드가 별도로 존재하기 때문에 신중히 사용해야되는 것과는 다르게, Queue의 remove() 메서드는 Queue가 Integer 타입이든 String 타입이든 문제 없이 사용하면 된다.

 

 

기본적으로 Java에서 제공하는 우선순위 큐는 오름차순으로 요소들이 정렬된다고 했다.

마지막으로 우선순위 큐 문제를 풀 때, 사용했던 내림차순 정렬도 정리하자면 다음 코드와 같다.

 

// 기본 우선순위 큐(오름차순)
Queue<Integer> AscendingPQ = new PriorityQueue<>();			

// 내림차순 정렬 우선순위 큐
Queue<Integer> DescendingPQ = new PriorityQueue<>((o1, o2) -> o2 - o1);

 

내부적으로 내림차순 정렬이 되는 우선순위 큐를 구현하는 방법은 다양하다. - 참고

• Collections 클래스의 reverseOrder() 메서드 이용
• Comparator 인터페이스의 compareTo() 메서드를 Override하여 사용
• 람다 표현식을 사용

나는 사용했던 대부분의 우선순위 큐 정렬은 람다 표현식을 이용했다.

 

 

 

잘못된 부분은 언제든 댓글 달아주시면 정정하겠습니다.