Java 큐 인터페이스와 주요 구현체 분석

Queue 인터페이스의 기본 개념

Queue는 FIFO(First In, First Out) 원칙을 따르는 자료구조로, Collection 인터페이스를 확장하여 요소의 순차적 처리가 필요한 상황에서 사용된다. 대표적인 활용 예로는 작업 스케줄링, 버퍼 관리, 이벤트 처리 등이 있다.

public interface Queue<E> extends Collection<E> {}

FIFO 동작 방식

가장 먼저 추가된 요소가 가장 먼저 제거된다.

Queue<String> queue = new LinkedList<>();
queue.offer("X");
queue.offer("Y");
queue.offer("Z");

System.out.println(queue); // [X, Y, Z]
queue.poll();
System.out.println(queue); // [Y, Z]

실패 처리 전략

큐 연산은 두 가지 실패 처리 방식을 제공한다:

  • 예외 발생: 조건을 만족하지 않을 때 예외를 던진다.
  • 특수 값 반환: 실패 시 null 또는 false를 반환하며, 실무에서는 이 방식을 권장한다.
Queue<String> queue = new LinkedList<>();

// 예외 기반
try {
    queue.remove(); // 비어 있으면 NoSuchElementException 발생
} catch (NoSuchElementException e) {
    System.out.println("예외 발생: " + e.getClass().getSimpleName());
}

// 특수 값 기반
System.out.println("poll 결과: " + queue.poll()); // null 출력

// 용량 제한 큐에서 삽입 시도
Queue<Integer> bounded = new ArrayBlockingQueue<>(1);
bounded.offer(100);
System.out.println("offer 결과: " + bounded.offer(200)); // false

주요 메서드

연산 예외 기반 비정상 값 기반 (권장)
삽입 add(e) offer(e)
제거 remove() poll()
조회 (제거 없음) element() peek()

최선의 실천법: 항상 offer(), poll(), peek()을 사용하라. 예외 기반 메서드는 예측 불가능한 실행 흐름을 유발할 수 있다.

AbstractQueue 추상 클래스

큐 구현을 위한 기본 골격을 제공하며, 다음과 같이 선언된다.

public abstract class AbstractQueue<E> 
    extends AbstractCollection<E> 
    implements Queue<E>

핵심 설계 원리

  • AbstractCollection을 상속해 addAll() 등의 기본 메서드를 제공한다.
  • 큐 핵심 연산인 offer(), poll(), peek()은 추상 메서드로 남겨두고, 하위 클래스에서 구현하도록 강제한다.

기본 메서드 동작

  • add(e): 내부적으로 offer(e) 호출. 실패 시 IllegalStateException 발생.
  • remove(): poll() 호출 후 결과가 null이면 예외 발생.
  • element(): peek() 호출 후 null이면 예외 발생.
  • clear(): poll()을 반복 호출해 모든 요소 제거.
  • addAll(): 원자적이지 않으며, 일부만 성공할 수 있음.

중요 사항

  • 직접 인스턴스화할 수 없다.
  • 스레드 안전하지 않으며, 동시성 보장은 하위 클래스 책임이다.
  • offer(), poll(), peek()의 정확한 구현에 전체 동작이 의존한다.
  • 블로킹 큐는 이 클래스를 상속하고 put()/take() 메서드로 블로킹 동작을 추가한다.

PriorityQueue: 우선순위 기반 큐

힙(최소 힙 또는 최대 힙) 기반으로 구현되며, FIFO가 아닌 우선순위에 따라 요소를 처리한다.

생성 예시

// 기본 생성자 (자연 정렬)
PriorityQueue<Integer> pq1 = new PriorityQueue<>();

// 초기 용량 지정
PriorityQueue<Integer> pq2 = new PriorityQueue<>(16);

// 커스텀 비교기
PriorityQueue<Integer> pq3 = new PriorityQueue<>((a, b) -> b - a);

// 기존 컬렉션으로 초기화
PriorityQueue<Integer> pq4 = new PriorityQueue<>(Arrays.asList(5, 2, 8));

내부 구조

배열 기반의 이진 힙으로, 인덱스 기반 부모-자식 관계를 유지한다.

// 배열 상태: [2, 4, 10, 8, 7, 15, 20]
//
//     2
//   /   \
//  4     10
// / \   /  \
//8  7  15  20

주요 연산

  • offer(e) / add(e): O(log n), 삽입 후 상향 조정(sift-up).
  • poll(): O(log n), 최상위 요소 제거 후 하향 조정(sift-down).
  • peek(): O(1), 최상위 요소 참조.
  • contains(o): O(n), 전체 탐색 필요.
  • iterator(): 요소의 우선순위 순서를 보장하지 않는다.

중요 제약사항

  • null 요소 허용 안 함 → NullPointerException.
  • 비동기 환경에서는 PriorityBlockingQueue 사용 권장.
  • 대규모 데이터 삽입 시 초기 용량 설정으로 리사이징 비용 감소 가능.
  • 반복자는 실제 처리 순서와 다를 수 있으므로 poll()을 통한 소비를 권장.

사용 예시

record Student(String name, int score) {}

PriorityQueue<Student> students = new PriorityQueue<>(
    Comparator.comparingInt(Student::score).reversed()
);

students.offer(new Student("김유신", 95));
students.offer(new Student("이순신", 87));
students.offer(new Student("강감찬", 91));

while (!students.isEmpty()) {
    System.out.println(students.poll()); // 점수 높은 순
}

ConcurrentLinkedQueue: 무차단 동시성 큐

고성능 멀티스레드 환경을 위해 설계된 무차단, 비동기 큐로, CAS(compare-and-swap) 기반 알고리즘을 사용한다.

내부 노드 구조

private static class Node<E> {
    volatile E item;
    volatile Node<E> next;
    
    boolean casItem(E cmp, E val) { ... }
    boolean casNext(Node<E> cmp, Node<E> val) { ... }
}

핵심 알고리즘

  • Michael & Scott 알고리즘 기반.
  • 헤드(head)와 테일(tail) 포인터 분리.
  • 테일 포인터는 지연 업데이트되어 경합(reduced contention)을 줄임.

삽입 동작 흐름

  1. 새 노드 생성.
  2. 현재 tail부터 실제 마지막 노드 찾기.
  3. CAS로 마지막 노드의 next를 새 노드로 설정.
  4. 성공 시 조건부로 tail 포인터 업데이트.
  5. 실패 시 재시도.

주요 특징

  • 무차단(non-blocking): 스레드가 대기하지 않음.
  • 스레드 안전: CAS로 원자성 보장.
  • 무제한(unbounded): 메모리 한계까지 확장.
  • 약한 일관성: size(), contains(), 반복자는 정확하지 않을 수 있음.
  • null 요소 금지.

성능 특성

메서드 시간 복잡도 비고
offer() O(1) 평균 상수 시간
poll() O(1) 평균 상수 시간
peek() O(1)
size() O(n) 전체 탐색 필요
contains() O(n) 동시 수정 가능성 있음

사용 패턴

ConcurrentLinkedQueue<Task> taskQueue = new ConcurrentLinkedQueue<>();

// 생산자
ExecutorService producer = Executors.newSingleThreadExecutor();
producer.submit(() -> {
    for (int i = 0; i < 1000; i++) {
        taskQueue.offer(new Task(i));
    }
});

// 소비자
ExecutorService consumer = Executors.newSingleThreadExecutor();
consumer.submit(() -> {
    while (!Thread.interrupted()) {
        Task task = taskQueue.poll();
        if (task != null) {
            process(task);
        } else {
            Thread.yield(); // 잠깐 양보
        }
    }
});

주의 사항

  • size() > 0 대신 poll() 결과를 직접 검사하라.
  • 반복자는 약한 일관성을 가지므로, 변경 사항이 반영되지 않을 수 있다.
  • 대량 데이터 처리 시 메모리 누수 주의.

큐 구현체 비교 및 선택 가이드

구현체 삽입/삭제 동시성 경계 용도
ArrayDeque O(1) 비동기 무제한 단일 스레드 고성능 큐
LinkedList O(1) 비동기 무제한 리스트 기능 필요 시
PriorityQueue O(log n) 비동기 무제한 우선순위 기반 처리
ConcurrentLinkedQueue O(1) 무차단 무제한 고병렬 환경
ArrayBlockingQueue O(1) 블로킹 유제한 공정성 요구 시
SynchronousQueue O(1) 블로킹 용량 0 직접 전달형 통신

실무 적용 전략

  • 단일 스레드: ArrayDeque 사용 (가장 빠름).
  • 고병렬 환경: ConcurrentLinkedQueue 또는 적절한 BlockingQueue.
  • 용량 제어 필요: LinkedBlockingQueue 또는 ArrayBlockingQueue.
  • 즉시 전달: SynchronousQueue.
  • 지연 처리: DelayQueue.

잘못된 사용 예

Queue<Integer> q = new LinkedList<>();
q.offer(10);
q.offer(20);

// 잘못된 접근: 큐는 순차적 접근만 허용
// int first = ((LinkedList<Integer>)q).get(0); // 위반!

// 올바른 방법
int head = q.poll(); // 첫 번째 요소 소비

태그: java Queue PriorityQueue ConcurrentLinkedQueue AbstractQueue

7월 28일 02:01에 게시됨

인기 태그

©2026 괴물 클럽