第17课：集合框架 - Queue

🎯 学习目标

• 理解 Queue/Deque/BlockingQueue 三者的区别与使用场景
• 掌握 PriorityQueue（堆）的原理与自定义排序
• 掌握 ArrayDeque 作为队列/栈的使用（优于 Stack/LinkedList）
• 理解 BlockingQueue 在生产者-消费者中的作用
• 识别陷阱（PriorityQueue 不是线程安全、ArrayDeque 不允许 null）

---

📖 一、概念讲解：队列家族

Java 的队列体系庞大，先理清三组概念：

1. Queue vs Deque

• Queue：单端队列，一端入（offer）、另一端出（poll），FIFO。
• Deque（Double Ended Queue）：双端队列，两端都能入/出，既能当队列也能当栈。

2. 两套操作方法的语义（关键！）

操作	抛异常	返回特殊值
入队	add / addFirst/addLast	offer / offerFirst/offerLast
出队	remove / removeFirst/removeLast	poll / pollFirst/pollLast
查看	element / getFirst/getLast	peek / peekFirst/peekLast

规律：抛异常版用于"应该成功"的场景（失败说明出错）；返回特殊值版（null/false）用于"可能失败"的场景（如容量受限队列）。日常优先用 offer/poll/peek（不抛异常，更安全）。

---

📖 二、Queue 基本用法

Queue<Integer> queue = new LinkedList<>();
queue.offer(1); queue.offer(2); queue.offer(3);   // 入队尾
System.out.println(queue.peek());    // 1（查看队头，不删）
System.out.println(queue.poll());    // 1（出队头）
System.out.println(queue.size());    // 2

Queue 的常见实现：LinkedList、ArrayDeque、PriorityQueue。日常用 ArrayDeque 优于 LinkedList（更快更省内存）。

---

📖 三、PriorityQueue（优先队列 / 堆）

PriorityQueue 不保证 FIFO，而是按优先级出队——每次 poll 取出"最小"（默认）的元素。

// 最小堆（默认）
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(2); pq.offer(8); pq.offer(1);
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");   // 1 2 5 8

// 最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5); maxHeap.offer(2); maxHeap.offer(8);
System.out.println(maxHeap.poll());   // 8

// 自定义对象按字段排序
PriorityQueue<Task> taskPq = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority));

原理：底层是二叉堆（数组实现的完全二叉树）。默认是最小堆：根节点最小，poll 取根。入队/出队 O(log n)，peek O(1)。

应用：Top-K 问题（如"找第 K 大"用大小为 K 的最小堆）、任务调度（按优先级处理）、合并 K 个有序链表。

---

📖 四、Deque 与 ArrayDeque

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

// 当队列（FIFO）
deque.offerLast(1); deque.offerLast(2);   // 尾入
deque.pollFirst();                          // 头出 → 1

// 当栈（LIFO）
deque.push(1); deque.push(2);              // 头入（等价 addFirst）
deque.pop();                                // 头出 → 2

// 双端操作
deque.offerFirst(0); deque.offerLast(3);
deque.peekFirst(); deque.peekLast();

为什么用 ArrayDeque 代替 Stack？

• Stack 继承 Vector，方法都 synchronized，单线程下同步是纯开销。
• ArrayDeque 基于数组（循环数组），无同步，栈/队列操作均 O(1)，更快更省。
• Effective Java 明确建议：栈用 ArrayDeque，不要用 Stack。

为什么用 ArrayDeque 代替 LinkedList 做队列？

• ArrayDeque 是数组，内存连续，缓存友好，省去节点指针开销。
• LinkedList 是链表，每元素多 prev/next 指针，内存碎片化。

---

📖 五、BlockingQueue（阻塞队列）

BlockingQueue 是线程安全的队列，队空时 take 阻塞、队满时 put 阻塞——天生用于生产者-消费者。

BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(10);   // 容量10

// 生产者：队列满时 put 阻塞
new Thread(() -> {
    try { for (int i = 0; i < 20; i++) queue.put(i); }
    catch (InterruptedException e) { Thread.currentThread().interrupt(); }
}).start();

// 消费者：队列空时 take 阻塞
new Thread(() -> {
    try { while (true) { Integer item = queue.take(); /* 处理 */ } }
    catch (InterruptedException e) { Thread.currentThread().interrupt(); }
}).start();

常见实现：

• LinkedBlockingQueue：链表实现，可选有界。
• ArrayBlockingQueue：数组实现，必须指定容量。
• SynchronousQueue：容量0，put 必须等 take（直接交接）。
• PriorityBlockingQueue：带优先级的无界阻塞队列。

与普通 Queue 区别：BlockingQueue 线程安全、操作可阻塞；普通 Queue（ArrayDeque/PriorityQueue）非线程安全。

---

⚠️ 六、常见陷阱

陷阱1：PriorityQueue 的 iterator 不保证排序

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3); pq.offer(1); pq.offer(2);
System.out.println(pq);   // 不是 [1,2,3]！堆结构，遍历顺序不定
// 正确遍历：用 poll 逐个取出
while (!pq.isEmpty()) System.out.println(pq.poll());   // 1 2 3

原因：堆只保证"堆顶最小"，不保证整体有序。要有序输出必须逐个 poll。

陷阱2：PriorityQueue / ArrayDeque 非线程安全

多线程用 PriorityBlockingQueue 或加锁，或用并发包的队列。

陷阱3：ArrayDeque 不允许 null

ArrayDeque<Integer> d = new ArrayDeque<>();
d.offer(null);   // NPE！

ArrayDeque 用 null 判断空槽位，故禁止 null。LinkedList 允许 null（但建议避免，null 易引发歧义）。

陷阱4：混淆 offer/poll 与 add/remove

容量受限时 add/remove 抛异常，offer/poll 返回 false/null。生产代码优先后者。

陷阱5：用 Stack 而非 ArrayDeque

Stack 已过时（继承 Vector，同步开销大），栈场景一律用 ArrayDeque。

---

🆚 七、Java vs C 对比

特性	C 语言	Java
队列	手写链表/数组	Queue/Deque 接口体系
优先队列	手写堆	PriorityQueue 内置堆
阻塞队列	自己用 mutex/condition	BlockingQueue 内置阻塞
线程安全	手动加锁	并发包提供线程安全队列

对 C 程序员：Java 把 C 里手写的堆、阻塞队列、生产者-消费者都封装好了。重点理解 PriorityQueue 的堆特性（iterator 无序）和 BlockingQueue 的阻塞语义。

---

💡 八、最佳实践

1. 栈用 ArrayDeque，不要用 Stack。
2. 队列用 ArrayDeque（实现 Deque/Queue），优于 LinkedList。
3. 优先级场景用 PriorityQueue，Top-K 问题尤其好用。
4. 生产者-消费者用 BlockingQueue，避免手写 wait/notify。
5. 优先 offer/poll/peek，不用抛异常的 add/remove/element。
6. 多线程用并发包队列，不用 ArrayDeque/PriorityQueue。

---

📝 练习预告

完成 练习/Ex17_Queue.java 中的 6 道题：

1. Queue 基本操作（offer/poll/peek）
2. PriorityQueue 最小堆/最大堆
3. Deque 当队列与栈
4. ArrayDeque vs Stack 性能对比
5. 用 PriorityQueue 找第 K 大元素（Top-K）
6. 综合：BlockingQueue 实现生产者-消费者

完成后对比 答案/Sol17.java，查看逐行讲解与多解法。

---

📖 九、Queue 方法族详解

Queue 的方法故意设计成两套，是为了适配不同失败语义。

入队：

add：失败抛异常。
offer：失败返回 false。
put：阻塞直到可放入，BlockingQueue 专属。
offer(e, timeout, unit)：等待一段时间，BlockingQueue 专属。

出队：

remove：队空抛异常。
poll：队空返回 null。
take：队空阻塞，BlockingQueue 专属。
poll(timeout, unit)：等待一段时间，BlockingQueue 专属。

查看队头：

element：队空抛异常。
peek：队空返回 null。

实践建议：

普通队列优先 offer/poll/peek。
阻塞队列优先 put/take 或带 timeout 的 offer/poll。
业务上队空是异常时，才用 remove/element。

---

📖 十、PriorityQueue 的堆模型

PriorityQueue 底层是数组表示的二叉堆。

数组和树的关系：

父节点索引 i。
左子节点 2*i + 1。
右子节点 2*i + 2。
父节点 (i - 1) / 2。

最小堆性质：

每个父节点 <= 子节点。
堆顶是最小元素。
其他位置不保证整体有序。

入队过程：

新元素放到数组末尾。
与父节点比较。
如果比父节点小，向上交换。
直到满足堆性质。

出队过程：

取出堆顶。
把末尾元素放到堆顶。
向下与较小子节点交换。
直到满足堆性质。

这就是为什么 peek 是 O(1)，offer/poll 是 O(log n)。

---

🧪 十一、实战案例：Top-K

需求：从大量分数中找最高的 K 个。

思路：维护一个大小为 K 的最小堆。

public static List<Integer> topK(List<Integer> scores, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (Integer score : scores) {
        if (heap.size() < k) {
            heap.offer(score);
        } else if (score > heap.peek()) {
            heap.poll();
            heap.offer(score);
        }
    }
    List<Integer> result = new ArrayList<>(heap);
    result.sort(Comparator.reverseOrder());
    return result;
}

为什么不是把所有数据排序？

全量排序：O(n log n)。
Top-K 小堆：O(n log k)。
当 k 远小于 n 时，小堆明显更省。

常见场景：

排行榜。
热门商品。
日志中耗时最高的请求。
搜索结果前 N 个。

---

📖 十二、BlockingQueue 与背压

阻塞队列不仅是线程安全容器，也是“背压”工具。

没有容量限制的队列风险：

生产速度大于消费速度。
队列持续增长。
内存上涨。
最终 OOM。

有界队列能让生产者在队满时阻塞：

BlockingQueue<Task> queue = new ArrayBlockingQueue<>(1000);

这迫使系统承认处理能力有限，而不是无限堆积任务。

线程池里也有类似问题：

无界队列可能隐藏流量压力。
有界队列 + 拒绝策略更容易保护系统。

选择建议：

需要固定容量和稳定内存：ArrayBlockingQueue。
需要较高吞吐且容量可配置：LinkedBlockingQueue。
需要直接移交任务：SynchronousQueue。
需要优先级：PriorityBlockingQueue，但注意它默认无界。

---

🧪 十三、生产者-消费者停止策略

消费者不能永远 while(true) 而没有退出机制。

方式一：中断线程。

while (!Thread.currentThread().isInterrupted()) {
    try {
        Task task = queue.take();
        handle(task);
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}

方式二：毒丸对象。

static final Task POISON = new Task("STOP");

// 生产者结束时放入
queue.put(POISON);

// 消费者
Task task = queue.take();
if (task == POISON) {
    break;
}

如果有多个消费者，需要放入多个毒丸，或使用广播式停止机制。

---

🛠 十四、Queue 排查清单

队列相关问题常见于并发和调度场景。

队列是否有界。
生产速度是否大于消费速度。
消费者线程是否异常退出。
是否正确处理中断。
PriorityQueue 是否被多线程并发访问。
是否误以为 PriorityQueue 遍历有序。
是否把 null 放进 ArrayDeque。
是否使用 Stack 而不是 ArrayDeque。
BlockingQueue 的 put/take 是否导致线程永久等待。

监控指标：

队列长度。
入队速率。
出队速率。
任务等待时间。
消费者活跃线程数。
拒绝任务数量。

---

✅ 十五、掌握标准

学完本课后，应能做到：

能区分 Queue、Deque、BlockingQueue。
能说明 offer/poll 与 add/remove 的差异。
能用 ArrayDeque 实现队列和栈。
能解释 PriorityQueue 的堆结构和无序遍历。
能用 PriorityQueue 解决 Top-K。
能用 BlockingQueue 实现生产者-消费者。
能设计有界队列避免无限积压。
能正确处理中断和消费者停止。

Queue 的核心是“顺序和等待语义”。选择队列实现时，必须同时考虑排序、容量、线程安全和阻塞行为。

---

🎓 下一步

• 第18课：泛型 — 泛型类/方法、类型擦除、通配符、PECS