Queue

데이터를 선입선출(FIFO, First In First Out) 순서로 삽입·삭제하는 선형 자료구조입니다.

핵심 개념

enqueue(1) → enqueue(2) → enqueue(3)

front → │ 1 │ 2 │ 3 │ ← rear

dequeue() → 1 반환 (가장 먼저 들어온 것이 먼저 나감)

front → │ 2 │ 3 │ ← rear

주요 연산

큐의 종류

Java 구현

1. Java 내장 클래스

// Queue 인터페이스 — LinkedList로 구현
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);     // enqueue
queue.offer(2);
queue.offer(3);
queue.poll();       // dequeue → 1
queue.peek();       // 2 (제거 안 함)
queue.isEmpty();    // false
queue.size();       // 2

// ArrayDeque 사용 (더 빠름, 권장)
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
queue.poll();       // 1

2. 배열 기반 원형 큐 구현

public class CircularQueue<E> {
    private Object[] arr;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.arr = new Object[capacity];
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }

    public void enqueue(E item) {
        if (size == capacity) throw new IllegalStateException("큐가 가득 참");
        rear = (rear + 1) % capacity;  // 원형으로 순환
        arr[rear] = item;
        size++;
    }

    @SuppressWarnings("unchecked")
    public E dequeue() {
        if (size == 0) throw new NoSuchElementException("큐가 비어 있음");
        E item = (E) arr[front];
        arr[front] = null;
        front = (front + 1) % capacity;  // 원형으로 순환
        size--;
        return item;
    }

    @SuppressWarnings("unchecked")
    public E peek() {
        if (size == 0) throw new NoSuchElementException();
        return (E) arr[front];
    }

    public boolean isEmpty() { return size == 0; }
    public int size() { return size; }
}

3. 연결 리스트 기반 구현

public class LinkedQueue<E> {
    private static class Node<E> {
        E data;
        Node<E> next;
        Node(E data) { this.data = data; }
    }

    private Node<E> front;
    private Node<E> rear;
    private int size;

    public void enqueue(E item) {
        Node<E> newNode = new Node<>(item);
        if (rear != null) rear.next = newNode;
        rear = newNode;
        if (front == null) front = rear;
        size++;
    }

    public E dequeue() {
        if (front == null) throw new NoSuchElementException();
        E item = front.data;
        front = front.next;
        if (front == null) rear = null;
        size--;
        return item;
    }

    public E peek() {
        if (front == null) throw new NoSuchElementException();
        return front.data;
    }

    public boolean isEmpty() { return front == null; }
    public int size() { return size; }
}

선형 큐 vs 원형 큐

[선형 큐의 문제]
enqueue(1), enqueue(2), enqueue(3)
│ 1 │ 2 │ 3 │   │   │
  ↑ front       ↑ rear

dequeue() → 1 제거, dequeue() → 2 제거
│   │   │ 3 │   │   │
          ↑ front  ↑ rear

→ 앞의 빈 공간을 재활용할 수 없음 (낭비)

[원형 큐로 해결]
rear가 배열 끝에 도달하면 인덱스 0으로 순환

  인덱스: 0   1   2   3   4
        │   │   │ 3 │   │   │
                  ↑ front

  enqueue(4) → rear = (4+1) % 5 = 0
        │ 4 │   │ 3 │   │   │
          ↑ rear  ↑ front

→ 앞의 빈 공간 재활용 가능!

원형 큐 시각화:

        [0]
      ↗     ↘
   [4]       [1]
     ↖     ↙
   [3] ← [2]

front과 rear가 원형으로 순환

덱 (Deque — Double Ended Queue)

양쪽 끝에서 삽입과 삭제가 모두 가능한 큐입니다.

       앞(front)              뒤(rear)
삽입 ←──│ 1 │ 2 │ 3 │──→ 삽입
삭제 ←──│   │   │   │──→ 삭제

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

// 앞에서 삽입/삭제
deque.offerFirst(1);   // front에 삽입
deque.pollFirst();     // front에서 제거

// 뒤에서 삽입/삭제
deque.offerLast(2);    // rear에 삽입
deque.pollLast();      // rear에서 제거

// 스택처럼 사용
deque.push(1);         // = offerFirst
deque.pop();           // = pollFirst

// 큐처럼 사용
deque.offer(1);        // = offerLast
deque.poll();          // = pollFirst

우선순위 큐 (Priority Queue)

FIFO가 아니라 우선순위가 높은 원소가 먼저 나갑니다. 자세한 내용은 PriorityQueue 참고.

// 기본: 오름차순 (작은 값이 높은 우선순위)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);
pq.poll();   // 10 (가장 작은 값)
pq.poll();   // 20
pq.poll();   // 30

// 내림차순 (큰 값이 높은 우선순위)
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
maxPq.offer(30);
maxPq.offer(10);
maxPq.offer(20);
maxPq.poll();   // 30 (가장 큰 값)

큐의 활용 사례

BFS 예시

public void bfs(int[][] graph, int start) {
    boolean[] visited = new boolean[graph.length];
    Queue<Integer> queue = new ArrayDeque<>();

    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();       // front에서 꺼냄
        System.out.print(node + " ");

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor); // rear에 추가
            }
        }
    }
}

스택 vs 큐 비교