队列

什么是队列？

队列（Queue）是一种先进先出（FIFO - First In First Out）的数据结构。想象你在餐厅排队取餐——第一个排队的人第一个拿到食物。队列就是这样一种"先来先服务"的数据结构。

队列示意图:
    
    入队 (enqueue)                    出队 (dequeue)
        ↓                               ↓
    ┌───┬───┬───┬───┬───┐
    │ A │ B │ C │ D │   │   →  队首元素先出
    └───┴───┴───┴───┴───┘
     ↑                   ↑
    队首                队尾
    (front)             (rear)

Queue接口的方法分类

Queue接口的方法分为三类，每类都有两种形式——一种在操作失败时抛出异常，另一种返回特殊值（false或null）：

Queue的实现类

LinkedList实现Queue

import java.util.LinkedList;
import java.util.Queue;

public class QueueDemo {
    public static void main(String[] args) {
        // 创建队列
        Queue queue = new LinkedList<>();

        // 入队操作
        queue.offer("第一位客户");
        queue.offer("第二位客户");
        queue.offer("第三位客户");
        System.out.println("入队后: " + queue);

        // 查看队首（不移除）
        System.out.println("队首元素: " + queue.peek());

        // 出队操作
        String first = queue.poll();
        System.out.println("出队: " + first);
        System.out.println("出队后: " + queue);

        // 继续出队
        queue.poll();
        queue.poll();
        System.out.println("全部出队后: " + queue);

        // 尝试对空队列操作
        System.out.println("空队列peek: " + queue.peek());  // null
        System.out.println("空队列poll: " + queue.poll()); // null
    }
}

ArrayDeque双端队列

Deque（Double Ended Queue）是Queue的子接口，支持在两端进行插入和删除操作。ArrayDeque是Deque的高效实现。

双端队列示意图:
    
    ←←← 两端都可以进出 →→→
    
    ┌───┬───┬───┬───┬───┐
    │ A │ B │ C │ D │ E │
    └───┴───┴───┴───┴───┘
     ↑                   ↑
    首                  尾
    可addFirst/removeFirst  可addLast/removeLast

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeDemo {
    public static void main(String[] args) {
        Deque deque = new ArrayDeque<>();

        // 从队尾添加（普通队列操作）
        deque.offerLast("A");
        deque.offerLast("B");
        deque.offerLast("C");

        // 从队首添加
        deque.offerFirst("Start");

        System.out.println("deque: " + deque);  // [Start, A, B, C]

        // 查看
        System.out.println("队首: " + deque.peekFirst());  // Start
        System.out.println("队尾: " + deque.peekLast());   // C

        // 从不同端移除
        deque.removeFirst();
        deque.removeLast();
        System.out.println("移除首尾后: " + deque);  // [A, B]
    }
}

PriorityQueue优先级队列

PriorityQueue是一种特殊的队列，它的出队顺序不是按照入队先后，而是按照元素的优先级。默认情况下，优先级由元素的自然顺序决定（最小元素先出队）。

import java.util.PriorityQueue;
import java.util.Collections;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        // 默认是最小堆（最小元素先出）
        PriorityQueue minHeap = new PriorityQueue<>();
        minHeap.add(30);
        minHeap.add(10);
        minHeap.add(50);
        minHeap.add(20);

        System.out.println("PriorityQueue: " + minHeap);
        System.out.println("peek (最小): " + minHeap.peek());
        System.out.println("poll: " + minHeap.poll());  // 10
        System.out.println("poll: " + minHeap.poll());  // 20

        System.out.println("\n===== 最大堆 =====");
        // 创建最大堆（最大元素先出）
        PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.addAll(java.util.Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6));

        System.out.println("peek (最大): " + maxHeap.peek());
        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " ");
        }
    }
}

PriorityQueue自定义优先级

import java.util.PriorityQueue;

class Task {
    private String name;
    private int priority;  // 数字越小优先级越高

    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    public int getPriority() { return priority; }
    public String getName() { return name; }

    @Override
    public String toString() {
        return name + "(优先级:" + priority + ")";
    }
}

public class CustomPriorityQueue {
    public static void main(String[] args) {
        // 使用自定义比较器：优先级数字越小越先出
        PriorityQueue taskQueue = new PriorityQueue<>(
            (t1, t2) -> t1.getPriority() - t2.getPriority()
        );

        taskQueue.offer(new Task("紧急Bug修复", 1));
        taskQueue.offer(new Task("优化数据库", 3));
        taskQueue.offer(new Task("写文档", 5));
        taskQueue.offer(new Task("回复邮件", 2));

        System.out.println("任务执行顺序:");
        while (!taskQueue.isEmpty()) {
            Task task = taskQueue.poll();
            System.out.println("执行: " + task);
        }
    }
}

队列的使用场景

// 模拟打印机任务队列
Queue printQueue = new LinkedList<>();
printQueue.offer(new PrintJob("文档1"));
printQueue.offer(new PrintJob("文档2"));
// 打印机按顺序处理

Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
    Node node = queue.poll();
    // 处理node
    queue.offer(node.left);
    queue.offer(node.right);
}

Queue<消息> channel = new LinkedList<>();
// 生产者: channel.offer(message);
// 消费者: channel.poll();

三种队列实现对比

常见错误和注意事项

小结