카테고리 없음

자바 공부#2_03. Queue & Deque

코딩연습중 2025. 4. 5. 16:50

Queue?

Queue는 선입선출(FIFO)의 개념을 구현한 자료구조이다.

Queue특징

  1. 선입선출(FIFO)
  2. 중복 허용 ✅
  3. null 허용 여부는 클래스에 따라 다름

Queue인터페이스를 구현한 대표적인 클래스에는 LinkedList, PriorityQueue, ArrayDeque 등이 있다.

 

Deque?

Deque(Double-Ended Queue)는 양쪽 끝에서 삽입과 삭제가 모두 가능한 선형 자료구조다. 쉽게 말해, 앞에서도 삽입/삭제, 뒤에서도 삽입/삭제가 가능하다는 의미.
그래서 사실상 Queue + Stack의 기능을 모두 가지고 있는 유연한 자료구조다.

 

Deque 인터페이스를 구현한 대표적인 클래스에는 ArrayDeque, LinkedList 등이 있다.

 

1. LinkedList (as Queue)

LinkedList는 List뿐 아니라 Queue 및 Deque 인터페이스도 구현한 다재다능한 클래스이다.
Queue로 사용할 경우, FIFO 방식의 삽입/삭제가 빠르다는 장점이 있다.

특징

  • FIFO(선입선출) 구조
  • offer(), poll(), peek() 메서드 사용
  • 양쪽 삽입/삭제가 가능하여 Deque로도 활용 가능
  • 내부적으로 이중 연결 리스트 구조 사용
  • 삽입/삭제는 빠름, 인덱스 접근은 느림

따라서 단순한 큐 구조를 사용할 때  적합하다.

ex) 일반적인 대기열 처리, 작업 큐, 이벤트 큐

 

2. PriorityQueue

PriorityQueue는 요소가 들어오는 순서와 관계없이 우선순위에 따라 정렬된 순서로 처리되는 큐이다.
내부적으로 힙(Heap) 자료구조를 기반으로 합니다.

특징

  • 우선순위 큐 구조 (기본은 오름차순)
  • 요소는 자동 정렬되어 저장됨
  • offer(), poll(), peek() 메서드 사용
  • null 저장 불가
  • 정렬 기준은 Comparable 구현 or Comparator 전달

따라서 중요도/우선순위가 있는 작업 처리에 적합하다.

ex) 응급 환자 처리, 작업 스케줄링, 게임 순위 처리 등

 

3. ArrayDeque

ArrayDeque는 배열을 사용해 양방향으로 삽입과 삭제가 가능한 큐(Queue) 및 덱(Deque) 구조를 제공.
성능 면에서는 LinkedList보다 빠르고 가볍고, 메모리 효율도 높음

특징

  • 내부적으로 Resizable Array 구조 사용
  • Queue 및 Deque 인터페이스 둘 다 구현
  • 양쪽 삽입/삭제 가능 (addFirst, addLast, pollFirst, pollLast)
  • null 값 저장 ❌ (→ NullPointerException 발생)
  • Thread-safe 아님 (멀티스레드 환경에선 ConcurrentLinkedDeque 사용 필요)
  • LinkedList보다 더 빠른 큐/덱 성능 (포인터 구조 없음 → 메모리 접근 빠름)

따라서 양쪽 끝에서 삽입/삭제가 자주 필요한 경우, 스택이나 큐를 LinkedList 대신 더 빠르고 효율적으로 구현하고 싶을 때  적합하다.

💡 ArrayDeque는 Stack 클래스보다 스택으로 사용할 때도 더 빠르고 효율적이라 스택 대체용으로도 자주 사용

 

 

 

4. LinkedList vs PriorityQueue vs ArrayDeque

 

  LinkedList  PriorityQueue  ArrayDeque
추가 (add) O(1) (끝에 추가) O(log n) O(1)
삭제 (remove/poll) O(1) (앞/뒤 삭제 가능) O(log n) O(1)
탐색 (peek/contains) O(n) O(n) O(n)
정렬 여부 ❌ (입력 순서만 유지) ✅ (우선순위 기반 정렬) ❌
null 허용 여부 ✅ ❌ ❌
순서 보장 여부 ✅ 입력 순서 보장 ❌ (우선순위 기준) ✅ 입력 순서 보장
스레드 안전성 ❌ ❌ ❌
내부 구조 이중 연결 리스트 힙 기반 이진 트리 동적 배열 (순환 큐)
적합한 용도 일반적인 큐/덱, 양방향 처리에 적합 우선순위 작업 큐 (ex. 작업 스케줄링) 빠르고 가벼운 큐/스택 대체용

for문보다 Iterable 기반 반복문 (for-each) 사용이 일반적

 

5. PriorityQueue → Comparable / Comparator

PriorityQueue 사용 시에는 요소 간의 우선순위 기준이 필요.

이 때에 해당 클래스가 Comparable<T>를 구현하거나, Comparator<T>를 생성자에 넘겨줘야 함.

 

// 1. Comparable 구현
class Task implements Comparable<Task> {
    int priority;
    @Override
    public int compareTo(Task o) {
        return Integer.compare(this.priority, o.priority); // 낮은 숫자 우선
    }
}

// 2. 또는 Comparator 전달
PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingInt(t -> t.priority));