Computer >> 컴퓨터 >  >> 프로그래밍 >> Java

자바 PriorityQueue 완벽 가이드: 기본 개념부터 주요 메서드 활용법까지

자바에서 PriorityQueue란?

프로그래밍에서 우선순위 큐(Priority Queue)는 우선순위가 가장 높은 데이터를 가장 먼저 처리하도록 설계된 자료구조입니다. 일반적인 큐가 단순히 들어온 순서대로 데이터를 처리한다면, 우선순위 큐는 각 요소가 가진 '우선순위'를 기준으로 처리 순서를 결정합니다.

자바로 개발하다 보면 우선순위 큐를 구현해야 하는 상황을 자주 만나게 됩니다. 이때 떠올릴 수 있는 것이 자바의 Queue 인터페이스인데, Queue는 인터페이스이기 때문에 코드에서 직접 인스턴스화할 수 없습니다. 힙(heap) 자료구조를 기반으로 하는 우선순위 큐를 만들고 싶다면 PriorityQueue 클래스를 사용해야 합니다.

이 글에서는 자바 PriorityQueue의 기본 개념부터 큐 생성 방법, 그리고 큐의 요소를 조회하고 조작할 때 사용하는 핵심 메서드까지 예제 코드와 함께 자세히 살펴보겠습니다.

큐(Queue)와 우선순위 큐(PriorityQueue)의 차이

큐는 스택과 마찬가지로 연산이 수행되는 순서가 정해져 있는 자료구조입니다. 일반적인 큐는 선입선출(FIFO, First-In First-Out) 방식으로 동작합니다. 즉, 가장 먼저 삽입된 요소가 항상 가장 먼저 꺼내집니다.

식당을 예로 들어 보겠습니다. 손님이 주문한 순서대로 음식을 서빙하는 것이 가장 공정합니다. 따라서 Jack보다 늦게 주문한 손님이라면 Jack 다음 순서에 서빙받아야 하겠죠. 이것이 바로 큐의 동작 방식입니다.

반면 PriorityQueue는 요소들이 우선순위를 기준으로 정렬되는 큐입니다. 기본 설정(오름차순, 최소 힙)에서는 값이 작을수록 우선순위가 높습니다. 예를 들어 5와 10이 들어 있는 큐에서는 10이 나중에 추가되더라도 5가 항상 먼저 처리됩니다. 만약 값이 큰 요소를 먼저 처리하고 싶다면 Comparator를 지정하여 정렬 기준을 변경할 수 있습니다.

우선순위 큐 생성하기

자바에서 우선순위 큐를 사용하려면 먼저 java.util.PriorityQueue 패키지를 임포트해야 합니다. 이 패키지에는 큐를 생성할 수 있는 PriorityQueue 클래스가 포함되어 있습니다.

import java.util.PriorityQueue;

패키지를 임포트했다면 아래 문법으로 우선순위 큐를 생성할 수 있습니다.

PriorityQueue<데이터타입> 큐이름 = new PriorityQueue<>();

각 구성 요소를 살펴보겠습니다.

  • PriorityQueue: 우선순위 큐를 생성하겠다고 프로그램에 알려주는 부분입니다.
  • 데이터타입(DataType): 큐에 저장할 데이터의 타입입니다.
  • 큐이름(queue_name): 생성된 큐를 할당받을 변수의 이름입니다.
  • new PriorityQueue();: 우선순위 큐를 초기화합니다.

예를 들어 식당 손님들의 주문을 저장하는 큐를 만들고, 각 손님의 테이블 번호를 저장하고 싶다면 다음과 같이 작성할 수 있습니다.

PriorityQueue<Integer> orders = new PriorityQueue<>();

이 코드는 정수 값을 저장하는 orders라는 이름의 PriorityQueue 인스턴스를 생성합니다.

PriorityQueue에 요소 추가하기

자바에서 큐에 담긴 각 요소를 아이템(item)이라고 부릅니다. 큐에 아이템을 추가할 때는 add() 메서드를 사용합니다. 이 메서드는 추가할 값을 매개변수로 하나 받으며, 큐가 가득 찬 경우 예외(exception)를 발생시킵니다.

또한 offer() 메서드로도 아이템을 추가할 수 있습니다. 두 메서드의 차이점은 큐가 가득 찼을 때 나타납니다. offer()는 false를 반환하는 반면, add()는 예외를 던집니다.

22번 테이블과 17번 테이블이 점심 주문을 했다고 가정하고, 두 주문을 순서대로 큐에 추가해 보겠습니다.

import java.util.PriorityQueue;

class AddCustomer {
    public static void main(String[] args) {
        PriorityQueue<Integer> orders = new PriorityQueue<>();

        orders.add(22);
        System.out.println("주문 목록: " + orders);

        orders.offer(17);
        System.out.println("업데이트된 주문 목록: " + orders);
    }
}

실행 결과는 다음과 같습니다.

주문 목록: [22]
업데이트된 주문 목록: [17, 22]

코드를 단계별로 살펴보겠습니다.

  1. new PriorityQueue<>();로 orders라는 이름의 우선순위 큐를 생성합니다.
  2. add() 메서드로 22번 테이블 주문을 큐에 추가합니다.
  3. "주문 목록"이라는 문구와 함께 큐의 현재 내용을 콘솔에 출력합니다.
  4. offer() 메서드로 17번 테이블 주문을 큐에 추가합니다.
  5. "업데이트된 주문 목록"이라는 문구와 함께 변경된 큐의 내용을 콘솔에 출력합니다.

출력 결과에서 볼 수 있듯이, 17이 추가된 후 큐는 우선순위(값의 크기)에 따라 자동으로 재정렬되어 17이 맨 앞에 위치하게 됩니다. 우선순위 큐는 요소가 추가되거나 제거될 때마다 내부적으로 힙 구조를 유지하며 스스로 정렬된다는 점이 핵심입니다.

PriorityQueue에서 요소 제거하기

우선순위 큐에서 요소를 제거할 때 사용할 수 있는 메서드는 두 가지입니다.

  • remove(Object o): 큐에서 지정한 요소 하나를 제거합니다. 성공 여부를 boolean 값으로 반환합니다.
  • poll(): 큐의 맨 앞 요소(우선순위가 가장 높은 요소)를 제거하고, 제거된 요소를 반환합니다.

부주방장이 17번 주문을 처리해서 큐에서 제거하고, 이후 셰프가 22번 주문을 처리해서 제거하는 상황을 가정해 보겠습니다.

import java.util.PriorityQueue;

class RemoveOrders {
    public static void main(String[] args) {
        PriorityQueue<Integer> orders = new PriorityQueue<>();

        orders.add(22);
        orders.add(17);

        boolean removed = orders.remove(17);
        System.out.println("17번 주문이 제거되었나요? " + removed);

        int secondRemoved = orders.poll();
        System.out.println("주문 #" + secondRemoved + "이(가) 큐에서 제거되었습니다.");
    }
}

실행 결과는 다음과 같습니다.

17번 주문이 제거되었나요? true
주문 #22이(가) 큐에서 제거되었습니다.

코드의 흐름을 살펴보겠습니다. 먼저 remove(17)을 호출해 큐에서 값 17을 제거했습니다. 제거에 성공했기 때문에 메서드는 true를 반환하고, 이 결과가 콘솔에 출력됩니다.

다음으로 poll() 메서드를 호출해 큐의 맨 앞 요소를 제거했습니다. 남아 있던 유일한 주문은 22번이었으므로, poll()은 22를 반환하며 해당 요소를 큐에서 제거합니다. 참고로 큐가 비어 있을 때 poll()을 호출하면 예외 대신 null을 반환합니다.

큐의 맨 앞 요소 조회하기

peek() 메서드는 큐의 헤드(head), 즉 우선순위가 가장 높은 첫 번째 요소를 조회할 때 사용합니다. 요소를 실제로 제거하지 않고 값만 확인할 수 있다는 점이 특징입니다.

부주방장이 새로운 주문을 받을 준비가 되어, 다음으로 처리해야 할 주문이 무엇인지 확인하고 싶다고 가정해 보겠습니다.

import java.util.PriorityQueue;

class RetrieveOrder {
    public static void main(String[] args) {
        PriorityQueue<Integer> orders = new PriorityQueue<>();

        orders.add(22);
        orders.add(17);

        int nextOrder = orders.peek();
        System.out.println("다음으로 처리할 주문은 " + nextOrder + "번 테이블입니다.");
    }
}

실행 결과는 다음과 같습니다.

다음으로 처리할 주문은 17번 테이블입니다.

현재 큐에서 우선순위가 가장 높은 값은 17이므로, peek() 메서드는 17을 반환합니다. 큐가 비어 있을 경우 peek()은 null을 반환하므로, 빈 큐를 안전하게 처리할 수 있습니다.

우선순위 큐 순회하기

큐를 다루다 보면 우선순위 큐의 모든 요소를 한 번씩 확인하기 위해 반복자(iterator)를 생성해야 하는 경우가 많습니다.

이때 java.util.Iterator 패키지에 포함된 iterator() 메서드를 사용할 수 있습니다. 먼저 아래 코드로 Iterator 패키지를 임포트합니다.

import java.util.Iterator;

식당 주문 큐에 담긴 모든 아이템을 콘솔에 출력해 보겠습니다.

import java.util.PriorityQueue;
import java.util.Iterator;

class PrintOrders {
    public static void main(String[] args) {
        PriorityQueue<Integer> orders = new PriorityQueue<>();

        orders.add(22);
        orders.add(17);
        orders.add(14);
        orders.add(19);

        Iterator<Integer> iterate = orders.iterator();
        while (iterate.hasNext()) {
            System.out.println(iterate.next());
        }
    }
}

실행 결과는 다음과 같습니다.

14
19
17
22

코드를 살펴보면, 먼저 네 개의 값을 큐에 추가한 뒤 iterator() 메서드로 반복자를 생성합니다. 이어서 while 루프와 hasNext(), next() 메서드를 사용해 큐의 모든 요소를 하나씩 순회하며 출력합니다.

주의할 점은 Iterator의 순회 순서가 우선순위 순서를 보장하지 않는다는 것입니다. 위 출력 결과처럼 내부 힙 배열의 저장 순서대로 반환될 수 있습니다. 요소를 우선순위 순서대로 처리하려면 poll()을 반복 호출하거나, toArray()로 변환한 뒤 정렬하는 방법을 사용하는 것이 좋습니다.

그 외 자주 사용되는 PriorityQueue 메서드

PriorityQueue 클래스와 함께 자주 사용되는 메서드는 다음과 같습니다.

메서드 이름설명
size()큐에 저장된 요소의 개수를 반환합니다.
toArray()큐를 배열로 변환합니다.
contains(elementName)큐에 특정 요소가 존재하는지 검색합니다.

마무리

자바의 PriorityQueue 클래스는 Queue 인터페이스를 구현한 대표적인 클래스로, 요소들을 우선순위를 기준으로 자동 정렬하며 관리해 줍니다. 일반 큐가 선입선출(FIFO) 방식으로 동작하는 것과 달리, 우선순위 큐는 우선순위가 가장 높은 요소가 항상 먼저 처리됩니다.

이 글에서는 큐와 우선순위 큐의 기본 개념을 살펴보고, 큐를 생성하는 방법과 add(), offer(), remove(), poll(), peek(), iterator() 등 핵심 메서드를 활용해 큐의 요소를 추가, 제거, 조회, 순회하는 방법까지 알아보았습니다.

이제 여러분도 자바 PriorityQueue 클래스를 능숙하게 활용할 준비가 되었습니다!