Java Queue, Deque, PriorityQueue 완벽 가이드

코딩 테스트를 준비하다 보면 Queue 관련 자료구조를 정말 많이 사용하게 됩니다. 특히 BFS 알고리즘이나 우선순위 처리 같은 문제에서 필수적이죠. 저도 처음엔 이 세 가지가 뭐가 다른지 헷갈렸는데, 하나씩 공부하면서 정리해보니 확실히 이해가 되더라고요. 오늘은 제가 공부한 내용을 바탕으로 Queue, Deque, PriorityQueue의 사용 패턴을 같이 살펴보려고 합니다.

Queue 인터페이스 기본 개념

Queue는 FIFO(First-In-First-Out) 방식으로 동작하는 자료구조입니다. 쉽게 말해 먼저 들어간 데이터가 먼저 나오는 구조죠. 은행 창구에서 번호표를 뽑고 기다리는 것과 비슷하다고 생각하면 됩니다.

 

Java에서 Queue는 인터페이스로 제공되기 때문에 직접 인스턴스를 만들 수 없습니다. 대신 LinkedList나 PriorityQueue 같은 구현 클래스를 사용해야 합니다.

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll()); // 1 출력

Queue의 핵심 메서드

Queue 인터페이스는 크게 두 가지 스타일의 메서드를 제공합니다.

• 예외를 던지는 메서드: add(), remove(), element()
• 특수 값을 반환하는 메서드: offer(), poll(), peek()

실무에서는 offer, poll, peek를 더 자주 사용합니다. 예외를 던지는 대신 null이나 false를 반환하기 때문이죠.

Queue<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first
System.out.println(queue.remove()); // second
System.out.println(queue.poll()); // null

LinkedList를 Queue로 사용하기

LinkedList는 Queue 인터페이스를 구현하고 있어서 큐로 사용할 수 있습니다. 하지만 일반적인 큐 용도로는 ArrayDeque가 더 효율적이라고 알려져 있습니다.

Queue<Integer> linkedQueue = new LinkedList<>();
linkedQueue.offer(10);
linkedQueue.offer(20);
linkedQueue.offer(30);
while (!linkedQueue.isEmpty()) {
    System.out.println(linkedQueue.poll());
}

Deque로 더 유연하게 작업하기

Deque는 Double Ended Queue의 약자로, 양쪽 끝에서 데이터를 추가하거나 제거할 수 있는 자료구조입니다. 스택과 큐 두 가지 역할을 모두 수행할 수 있습니다.

Deque의 주요 메서드

• 앞쪽: addFirst(), offerFirst(), removeFirst(), pollFirst(), peekFirst()
• 뒤쪽: addLast(), offerLast(), removeLast(), pollLast(), peekLast()

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("첫번째");
deque.addLast("마지막");
deque.addFirst("새로운 첫번째");
System.out.println(deque.peekFirst());
System.out.println(deque.peekLast());

Deque를 Stack처럼 사용하기

Deque는 Stack 자료구조로도 사용할 수 있습니다. Java에서는 레거시 Stack 클래스 대신 Deque를 권장합니다.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 3

ArrayDeque vs LinkedList 성능 비교

구현체	특징
ArrayDeque	빠른 속도, 메모리 효율 좋음, null 허용하지 않음
LinkedList	메모리 많이 사용, null 허용, 중간 삽입 유리

Deque 활용 예시: 슬라이딩 윈도우 최댓값

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new ArrayDeque<>();
    int[] result = new int[nums.length - k + 1];
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && deque.peekFirst() <= i - k)
            deque.pollFirst();
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
            deque.pollLast();
        deque.offerLast(i);
        if (i >= k - 1)
            result[i - k + 1] = nums[deque.peekFirst()];
    }
    return result;
}

PriorityQueue로 우선순위 처리하기

PriorityQueue는 내부적으로 힙(Heap) 구조를 사용하는 우선순위 큐입니다. 값이 작은 요소부터 우선적으로 반환됩니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(2);
pq.offer(8);
pq.offer(1);
System.out.println(pq.peek()); // 1

커스텀 Comparator 사용하기

class Task {
    String name;
    int priority;
    Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }
}
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    (t1, t2) -> t2.priority - t1.priority
);
taskQueue.offer(new Task("작업1", 3));
taskQueue.offer(new Task("작업2", 1));
while (!taskQueue.isEmpty()) {
    Task task = taskQueue.poll();
    System.out.println(task.name + " : " + task.priority);
}

PriorityQueue 활용 예제: K번째 큰 수

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int n : nums) {
        pq.offer(n);
        if (pq.size() > k) pq.poll();
    }
    return pq.peek();
}

활용 패턴 정리

• Queue: BFS, 순차적 작업처리
• Deque: 스택/큐 혼합 문제, 슬라이딩 윈도우
• PriorityQueue: 다익스트라, 우선순위 작업 처리, K번째 값

Queue, Deque, PriorityQueue는 자바 컬렉션 프레임워크에서 자주 쓰이지만 각각의 특성과 시간복잡도를 이해하면 훨씬 더 효율적으로 사용할 수 있습니다. 이 세 가지를 자유자재로 다룰 수 있게 되면 코딩 테스트 문제 해결력이 확실히 올라갑니다.

 

Java Map 완전 정복: HashMap, LinkedHashMap, TreeMap 비교와 키 설계 핵심 가이드