본문으로 건너뛰기
Advertisement

11.4 Queue, Deque, PriorityQueue

리스트(List)가 인덱스로 관리하는 순서 있는 컬렉션이라면, Queue와 Deque는 데이터의 입출력 방향을 제한하는 자료구조입니다. 알고리즘과 실제 시스템 설계에서 핵심적으로 사용됩니다.

1. Queue (큐) - FIFO​

First In, First Out — 먼저 들어온 것이 먼저 나갑니다. 마치 은행 대기열처럼 처음 줄 선 사람이 먼저 처리됩니다.

입력 → [C] [B] [A] → 출력
          ↑입력      ↑출력

Queue 인터페이스 주요 메서드​

메서드동작실패 시
offer(e)요소 추가false 반환
poll()앞에서 제거 후 반환null 반환
peek()앞 요소 조회 (제거 안 함)null 반환
add(e)요소 추가예외 발생
remove()앞에서 제거 후 반환예외 발생
import java.util.LinkedList;
import java.util.Queue;

Queue<String> queue = new LinkedList<>();

// 입력 (뒤에 추가)
queue.offer("첫 번째");
queue.offer("두 번째");
queue.offer("세 번째");

System.out.println(queue.peek());   // "첫 번째" (제거 안 함)
System.out.println(queue.poll());   // "첫 번째" (제거)
System.out.println(queue.poll());   // "두 번째"
System.out.println(queue);          // [세 번째]
System.out.println(queue.poll());   // "세 번째"
System.out.println(queue.poll());   // null (비어 있을 때)

실전 예제: BFS (너비 우선 탐색)​

Queue는 BFS(너비 우선 탐색) 알고리즘의 핵심 자료구조입니다.

import java.util.*;

public class BFSExample {
    // 그래프: 각 노드와 연결된 이웃 노드들
    static Map<Integer, List<Integer>> graph = new HashMap<>();

    static {
        graph.put(1, Arrays.asList(2, 3));
        graph.put(2, Arrays.asList(4, 5));
        graph.put(3, Arrays.asList(6));
        graph.put(4, Collections.emptyList());
        graph.put(5, Collections.emptyList());
        graph.put(6, Collections.emptyList());
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.offer(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        bfs(1); // 출력: 1 2 3 4 5 6
    }
}

2. Deque (덱) - 양방향 큐​

Double Ended Queue — 앞(front)과 뒤(rear) 양쪽에서 모두 추가·제거할 수 있습니다. Stack과 Queue 기능을 모두 포함합니다.

     ↓앞에 추가     ↓뒤에 추가
[A] [B] [C] [D]
↑앞에서 제거       ↑뒤에서 제거
import java.util.ArrayDeque;
import java.util.Deque;

Deque<String> deque = new ArrayDeque<>();

// 뒤에 추가 (Queue처럼)
deque.offerLast("B");
deque.offerLast("C");

// 앞에 추가 (Stack처럼)
deque.offerFirst("A");

System.out.println(deque); // [A, B, C]

System.out.println(deque.pollFirst());  // "A" (앞에서 제거)
System.out.println(deque.pollLast());   // "C" (뒤에서 제거)
System.out.println(deque.peekFirst());  // "B" (앞 확인, 제거 안 함)

Deque를 Stack으로 사용​

자바의 Stack 클래스는 레거시입니다. ArrayDeque를 Stack으로 사용하는 것이 현대 자바의 권장 방식입니다.

Deque<Integer> stack = new ArrayDeque<>();

stack.push(1); // offerFirst와 동일
stack.push(2);
stack.push(3);

System.out.println(stack.pop());  // 3 (LIFO - Last In First Out)
System.out.println(stack.pop());  // 2
System.out.println(stack.peek()); // 1 (제거 안 함)

실전 예제: 괄호 유효성 검사 (Stack 활용)​

public static boolean isValidBracket(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == '}' && top != '{') return false;
            if (c == ']' && top != '[') return false;
        }
    }

    return stack.isEmpty();
}

System.out.println(isValidBracket("({[]})"));  // true
System.out.println(isValidBracket("([)]"));    // false
System.out.println(isValidBracket("{[}"));     // false

3. PriorityQueue (우선순위 큐)​

일반 Queue는 FIFO이지만, PriorityQueue는 우선순위가 높은 요소부터 나옵니다. 내부적으로 힙(Heap) 자료구조로 구현됩니다.

import java.util.PriorityQueue;

// 기본: 숫자의 경우 오름차순 (작은 값이 먼저 나옴)
PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll()); // 10 (가장 작은 값)
System.out.println(pq.poll()); // 20
System.out.println(pq.poll()); // 30

커스텀 우선순위 (Comparator)​

// 내림차순 (큰 값이 먼저)
PriorityQueue<Integer> descPq = new PriorityQueue<>(Comparator.reverseOrder());
descPq.offer(10);
descPq.offer(30);
descPq.offer(20);
System.out.println(descPq.poll()); // 30

// 객체에 커스텀 우선순위
record Task(String name, int priority) {}

PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority) // priority 낮을수록 먼저
);

taskQueue.offer(new Task("일반 작업", 3));
taskQueue.offer(new Task("긴급 작업", 1));
taskQueue.offer(new Task("중요 작업", 2));

while (!taskQueue.isEmpty()) {
    System.out.println(taskQueue.poll().name());
}
// 출력:
// 긴급 작업
// 중요 작업
// 일반 작업
고수 팁

자료구조 선택 가이드:

상황선택
일반 FIFO 큐ArrayDeque (LinkedList보다 빠름)
Stack (LIFO)ArrayDeque (Stack 클래스 사용 금지)
앞뒤 모두 삽입/삭제ArrayDeque
우선순위 기반 처리PriorityQueue

ArrayDeque는 LinkedList보다 일반적으로 더 빠릅니다. 내부 배열 기반이라 캐시 효율이 높고, 노드별 객체 생성 오버헤드가 없습니다. LinkedList를 Queue로 쓰는 오래된 코드가 많지만, 신규 코드에서는 ArrayDeque를 사용하세요.

Advertisement
Advertisement