从一道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 frontclass 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 641Java 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) { DequeInteger 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表现更好。这种通过实践获得的理解远比单纯阅读文档要深刻得多。