---
title: "00-Queue和Deque总览"
created: 2025-12-02
tags:
  - Java
---
# Queue 和 Deque

> [!note] 定位说明
> 本篇是 Queue 系列总览：Queue（FIFO）/ Deque（双端）两接口 + 三实现速览。深读动线：[[01-ArrayDeque|ArrayDeque]]（栈与双端首选）→ [[02-PriorityQueue|PriorityQueue]]（堆与 Top K）。LinkedList 的队列角色见 List 系列篇内"扩展用法"。

Java 中的 `Queue` 和 `Deque` 是处理队列、双端队列和栈操作的重要接口。`Queue` 如 `PriorityQueue` 提供基于优先级的出队操作，底层是最小堆；而 `Deque` 支持从两端插入和删除，`ArrayDeque` 是其高性能实现，适用于栈和双端队列场景。`LinkedList` 同时实现了 `List` 和 `Deque` 接口，但性能不如专用实现。它们都不是线程安全的，适用于单线程或通过同步手段控制并发。

## Queue 接口的两套方法（高频面试点）

同一个动作，`Queue` 都提供两种风格：**失败抛异常** vs **失败返回特殊值**——面试和源码里来回出现，必须分清：

| 动作 | 抛异常版 | 返回特殊值版 | 失败时的表现 |
| --- | --- | --- | --- |
| 入队 | `add(e)` | `offer(e)` | 容量受限队列满时：抛 `IllegalStateException` / 返回 `false` |
| 出队 | `remove()` | `poll()` | 队空时：抛 `NoSuchElementException` / 返回 `null` |
| 看队头（不出队） | `element()` | `peek()` | 队空时：抛 `NoSuchElementException` / 返回 `null` |

记忆法：**e 开头三兄弟（add/remove/element）脾气硬会抛异常**；o/p 开头三兄弟（offer/poll/peek）温和返回 null/false。**日常写代码推荐 offer/poll/peek**——用返回值判空比捕获异常自然得多。`Deque` 把这套矩阵在头尾各复制一份（`addFirst/offerFirst`、`removeLast/pollLast`……），规则相同。

### [[01-ArrayDeque|ArrayDeque]] —— 高性能双端队列

- **底层结构**：循环数组（动态扩容）
- **支持操作**：头尾插入、删除、队列 & 栈行为
- **优势**：
  - 比 `LinkedList` 更高效
  - 不允许存 null 元素（避免歧义）
  - 不线程安全（多线程环境需加锁）
- **适合场景**：栈、队列、双端队列、缓存队列等

示例用法：

```java
Deque<String> deque = new ArrayDeque<>();
deque.offerFirst("A"); // 头部插入
deque.offerLast("B");  // 尾部插入
deque.pollFirst();     // 头部弹出
deque.pollLast();      // 尾部弹出
```

> 类比 C++：`std::deque`（双端队列）

### [[02-PriorityQueue|PriorityQueue]] —— 优先级队列（最小堆）

- **底层结构**：基于 **最小堆** 的数组实现
- **排序规则**：默认按元素的自然顺序（或传入 Comparator）
- **元素特点**：允许重复，**不允许 null**
- **应用场景**：定时任务调度、最短路径、Top K 问题等

示例用法：

```java
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(2);
pq.offer(8);
System.out.println(pq.poll()); // 输出 2（最小值）
```

> 类比 C++：`std::priority_queue`（但 Java 默认是最小堆，C++ 是最大堆）

### [[02-LinkedList|LinkedList]] —— 多面手（同时是 List + Queue + Deque）

- 既实现了 `List` 接口，又实现了 `Deque` 接口
- 适合需要频繁头尾插入删除的双端队列
- 但性能略逊于 `ArrayDeque`，主要用于兼容性和老代码场景

| 特性 | Queue | Deque |
| --- | --- | --- |
| 接口定义 | FIFO 队列 | 双端队列（可模拟栈） |
| 代表实现类 | LinkedList, PriorityQueue | LinkedList, ArrayDeque |
| 支持方向 | 只能尾进头出 | 头尾都可进出（更灵活） |
| 推荐使用 | 消息队列、调度器 | 栈、缓存、滑动窗口等 |
| 是否线程安全 | ❌（需加锁） | ❌（需加锁） |

> [!warning] 用栈时用 `Deque`，别用 `Stack` 类
> Java 自带的 `java.util.Stack` 继承自 `Vector`（见 List 系列 03 篇），继承了方法级 synchronized 的粗粒度锁，且官方 Javadoc 自己都建议不再使用。新代码写栈统一用 `Deque<Integer> stack = new ArrayDeque<>();` 配 `push()`/`pop()`/`peek()`——方法名一样，性能好得多。与阻塞队列（`BlockingQueue` 家族）相关的并发话题，等 03-Java并发分区再展开。
---
⬅️ [[04-TreeSet源码分析|TreeSet源码分析]] 🏠 [[00-Java|00-Java]] ➡️ [[01-ArrayDeque|ArrayDeque]]