77. Queue 与 Deque

Queue 就是排队

Queue 模拟现实里的排队：先来的人先办业务，也就是先进先出（FIFO）。

Queue<String> queue = new ArrayDeque<>();
queue.offer("甲"); // 入队
queue.offer("乙");
queue.offer("丙");
System.out.println(queue.poll()); // 甲，出队，先来的先走
```java

Queue 的方法分两套，语义不同，初学者要分清：

- `add` / `remove` / `element`：队列满了/空了会**抛异常**。
- `offer` / `poll` / `peek`：满了/空了返回 `false` / `null`，**更温和**。

日常写队列推荐用 `offer`/`poll`/`peek` 这一套，不容易因为边界情况崩。

```java
Queue<String> q = new ArrayDeque<>();
q.offer("任务1");
String head = q.peek();   // 看一眼队首，不删除
String done = q.poll();   // 取走队首并删除

Deque 是两头都能进出的队列

Deque 全称 double-ended queue（双端队列）。它既能当普通队列，又能在头部和尾部同时操作，所以既能 FIFO 也能 LIFO（栈）。

Deque<String> dq = new ArrayDeque<>();
dq.offerLast("尾");   // 尾部入队
dq.offerFirst("头");  // 头部入队
System.out.println(dq.pollFirst()); // 头，出队
System.out.println(dq.pollLast());  // 尾，出队
```java

当你只需要栈（后进先出）时，`ArrayDeque` 是替代老古董 `Stack` 的现代首选：

```java
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // 压栈，等同 offerFirst
stack.push(2);
System.out.println(stack.pop()); // 2，弹栈，等同 pollFirst

PriorityQueue 不按顺序出队

PriorityQueue 也是 Queue 的实现，但它不保证先进先出，而是按「优先级」出队：每次 poll 出来的都是当前最小的（或按你指定的比较规则最小的）。

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);
System.out.println(pq.poll()); // 10，最小的最先出
System.out.println(pq.poll()); // 20
```bash

它底层是堆（一种树结构），适合「每次取最值」的场景，比如任务调度里先处理优先级最高的。注意它迭代遍历时并不是有序的，只有 `poll` 才保证取出当前最小。

> [!WARNING]
> 别把 PriorityQueue 当普通排队用。你 `offer` 的顺序和 `poll` 出来的顺序没关系，它只认大小不认先后。要看一眼堆顶用 `peek()`，同样取最小的元素。

## 三种队列怎么选

- `ArrayDeque`：普通队列、双端队列、栈——几乎全能，默认首选。
- `PriorityQueue`：需要按优先级/大小出队时用，不保 FIFO。
- `LinkedList`：也能当队列/双端队列，但性能不如 ArrayDeque，除非你同时要它的 List 能力。

## 遍历队列要注意

遍历队列用增强 for 即可，但要注意：遍历**不会**删除元素，只有 `poll` 才出队。

```java
Queue<String> q = new ArrayDeque<>(List.of("a", "b", "c"));
for (String s : q) {
    System.out.println(s); // 只是看，队列里还在
}
System.out.println(q.size()); // 3，没少

队列不能放 null

ArrayDeque 和 PriorityQueue 都不允许放入 null，一放就抛 NullPointerException。这和 ArrayList、HashSet 不一样（后两者允许一个 null）。

Queue<String> q = new ArrayDeque<>();
// q.offer(null); // 抛 NullPointerException
```bash

> [!WARNING]
> 别往 ArrayDeque / PriorityQueue 里塞 `null`。如果业务上确实需要表达「空」，用 `Optional` 或自定义一个哨兵对象，而不是用 `null` 占位。

## ArrayDeque 的容量秘密

ArrayDeque 没有容量上限，需要时会自动成倍扩容，所以你基本不用担心满。它底层是个循环数组，头尾操作都很快，这也是它比 LinkedList 当队列更快的原因——数组的缓存局部性比链表好得多，CPU 读起来更顺。

Queue 和 Stack 别混用接口。当你要的是栈，就声明成 `Deque` 然后用 `push`/`pop`；要的是队列，就用 `offer`/`poll`。虽然 ArrayDeque 两个都能干，但接口选对了，代码读起来意图更清晰，别人一看就知道你这容器是用来排队还是用来压栈的。

面试常考：为什么推荐 ArrayDeque 而不是 LinkedList 当队列？答案就是上面反复提的——ArrayDeque 基于数组，首尾操作时间和 LinkedList 一样是常量，但实际运行更快、内存更省，还没有 LinkedList 每个节点都要额外对象头的开销。能用 ArrayDeque 就别用 LinkedList 当队列。

## PriorityQueue 的典型用途

PriorityQueue 看着像队列，其实更像「会自动排序的待办清单」。典型场景是任务调度：把一堆任务按优先级入队，每次 `poll` 都拿到当前最重要的那个先执行。它不保证先来后到，只保证你拿到的永远是当前最值，这点一定要记牢，否则业务逻辑会错得莫名其妙。

还有个细节：PriorityQueue 默认是最小堆（小的先出），要大的先出就传一个反过来比较的 Comparator，或者排序时取负（推荐用 `Comparator.reverseOrder()`，别手写取负，容易溢出）。它同样不允许放 null，遍历时顺序也不是排好的，只有 `poll` 才保证顺序。

## 一句话收尾

队列记住 offer/poll/peek 三件套，栈用 ArrayDeque 的 push/pop，按优先级出队才用 PriorityQueue。ArrayDeque 是无脑首选，LinkedList 当队列基本被它碾压。另外队列里别放 null，否则 poll 返回 null 时你分不清是「空了」还是「真取到了 null」，逻辑会埋雷。队列这种结构在真实项目里多用于解耦生产者和消费者，等你学到多线程和线程池，会频繁和它打交道，现在先把出入队语义练熟最要紧。

## 小结

Queue 是先进先出的排队结构，方法分「抛异常」和「返回空」两套，推荐用 `offer`/`poll`/`peek`；Deque 两头都能操作，`ArrayDeque` 是当代首选、可替代 Stack；PriorityQueue 按优先级而非顺序出队。下一章进入键值配对的 Map 家族。