从一道LeetCode题（641）出发，手把手教你实现自己的ArrayDeque，彻底搞懂双端队列
从LeetCode 641题实战：零基础构建高性能双端队列
第一次在LeetCode上遇到设计循环双端队列的题目时，我盯着那个"641"的编号发呆了十分钟。教科书上那些关于队列的抽象定义突然变成了具体的工程问题——如何让一个固定大小的数组既能从头部删除又能从尾部添加？这个问题就像一把钥匙，意外打开了我理解Java集合框架底层设计的大门。
1. 理解双端队列的核心需求
双端队列（Deque）就像地铁站的双向闸机，既允许乘客从两端进出。在LeetCode 641题中，我们需要实现几个关键操作：
insertFront()：在队首添加元素insertLast()：在队尾添加元素deleteFront()：移除队首元素deleteLast()：移除队尾元素
传统数组的局限性立即显现：如果在数组头部插入元素，需要将所有元素向后移动，时间复杂度高达O(n)。这就是为什么我们需要引入"循环数组"的概念——通过模运算让数组在逻辑上首尾相连。
// 循环数组索引计算示例 int nextFront = (front - 1 + capacity) % capacity; int nextRear = (rear + 1) % capacity;2. 设计循环数组的指针系统
实现循环双端队列最精妙的部分在于头尾指针的舞蹈。与普通队列不同，双端队列的两个指针都可能向任意方向移动。在初始状态，我习惯将front和rear都初始化为0，但这会导致判空和判满条件冲突——队列空和队列满时都是front == rear。
解决方案是引入一个size变量，或者牺牲一个数组空间。我更喜欢后者，因为：
- 不需要额外维护size变量
- 条件判断更直观：队满时
(rear + 1) % capacity == front
class MyCircularDeque { private int[] data; private int front, rear; private int capacity; public MyCircularDeque(int k) { capacity = k + 1; // 多分配一个空间用于区分空满 data = new int[capacity]; front = rear = 0; } }3. 边界条件处理的实战技巧
在实际编码中，边界条件总是最容易被忽视的部分。经过多次调试，我总结出这些经验：
- 插入操作前必须检查队列是否已满
- 删除操作前必须检查队列是否为空
- 指针移动要配合模运算防止越界
public boolean insertFront(int value) { if (isFull()) return false; front = (front - 1 + capacity) % capacity; data[front] = value; return true; } public boolean deleteLast() { if (isEmpty()) return false; rear = (rear - 1 + capacity) % capacity; return true; }注意：Java的%运算符对负数取模会得到负数结果，所以需要加上capacity再取模
4. 从LeetCode题到生产级实现
LeetCode的题目通常做了简化，真实的ArrayDeque实现要考虑更多工程细节：
| 特性 | LeetCode 641 | Java ArrayDeque |
|---|---|---|
| 容量 | 固定 | 动态扩容 |
| 并发 | 单线程 | 非线程安全 |
| 空值 | 不支持 | 允许null元素 |
| 迭代 | 不需要 | 实现Iterator |
动态扩容策略是生产级实现的关键。当数组空间不足时，ArrayDeque会按照当前容量的2倍扩容，并将元素重新排列：
private void doubleCapacity() { int newCapacity = data.length << 1; // 容量翻倍 Object[] newData = new Object[newCapacity]; // 将元素从front开始拷贝到新数组头部 System.arraycopy(data, front, newData, 0, data.length - front); System.arraycopy(data, 0, newData, data.length - front, rear); data = newData; front = 0; rear = data.length >>> 1; // 新rear位置是原容量 }5. 性能优化与陷阱规避
在真实项目中使用双端队列时，有几个性能陷阱需要注意：
- 初始容量选择：如果能预估最大元素数量，构造时指定容量避免多次扩容
- 批量操作：优先使用
addAll等方法减少边界检查次数 - 内存占用：长期闲置的队列考虑调用
trimToSize释放多余空间
// 性能优化示例：批量插入 public void addAllFront(Collection<? extends E> c) { for (E e : c) { addFirst(e); // 实际实现会有更优化的方式 } }6. 双端队列的变体与应用场景
理解了基本实现后，我们可以根据需求创造各种变体：
- 固定时间窗口统计：用循环双端队列实现滑动窗口
- 撤销操作历史：用双端队列保存有限步操作记录
- 工作窃取算法：每个线程维护自己的双端任务队列
// 滑动窗口最大值示例 public int[] maxSlidingWindow(int[] nums, int k) { Deque<Integer> deque = new ArrayDeque<>(); int[] result = new int[nums.length - k + 1]; for (int i = 0; i < nums.length; i++) { // 移除超出窗口范围的索引 while (!deque.isEmpty() && deque.peekFirst() <= i - k) { deque.pollFirst(); } // 移除比当前元素小的索引 while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) { deque.pollLast(); } deque.offerLast(i); if (i >= k - 1) { result[i - k + 1] = nums[deque.peekFirst()]; } } return result; }7. 测试驱动开发实践
好实现离不开全面测试。我习惯为双端队列编写这些测试用例：
边界测试：
- 创建容量为1的队列
- 连续插入删除直到边界
异常流程：
- 空队列时尝试删除
- 满队列时尝试插入
循环特性验证：
- 插入front直到绕回数组起点
- 从尾部删除直到绕回数组末尾
@Test public void testCircularBehavior() { MyCircularDeque deque = new MyCircularDeque(3); assertTrue(deque.insertLast(1)); assertTrue(deque.insertLast(2)); assertTrue(deque.insertFront(3)); // 队列: [3,1,2] assertFalse(deque.insertFront(4)); // 已满 assertEquals(3, deque.getFront()); assertEquals(2, deque.getRear()); assertTrue(deque.deleteLast()); // 移除2 assertTrue(deque.insertFront(4)); // 队列: [4,3,1] }从LeetCode题目到完整实现的过程中，最让我惊讶的是Java标准库中ArrayDeque的源码竟然如此简洁优雅。通过自己动手实现，那些原本晦涩的文档描述突然变得清晰起来——比如为什么建议用ArrayDeque代替Stack，以及它如何在大多数情况下比LinkedList表现更好。这种通过实践获得的理解，远比单纯阅读文档要深刻得多。