如果你看过 Java 集合源码多半绕不开ArrayDeque。这个号称既能当栈又能当队列的双端队列无论是在 LeetCode 题解里还是在面试问答题里出场率都相当高。但很多人对它的印象停留在“底层是循环数组”这一句话上真要问head和tail怎么转、扩容怎么搬数据、为什么容量永远得是 2 的幂就支支吾吾了。所以这次我想换一种方式讲ArrayDeque不贴大段源码干讲而是把它当成一个有血有肉的数据结构把数组下标、头尾指针、扩容瞬间全都“画”出来。我会先用最简单的命令行输出展示每一步状态再给出用前端小工具做动画的思路。不管你是准备面试还是要写自己的队列工具这篇文章都能帮你真正看懂ArrayDeque的底层原理。1. 从双端操作看 ArrayDeque 的设计价值1.1 双端操作到底解决了什么问题先看最基础的问题为什么需要双端队列普通队列Queue只能在队尾加、队头出如果我想在队头加元素、或者从队尾取元素就得换别的结构。比如浏览器后退前进的页面栈既要在顶部压入新页面又要在回退时从顶部弹出比如滑动窗口类算法经常需要从窗口左侧移除过期值、从右侧加入新值。这类场景天然要求“两端都能操作”ArrayDeque就是干这个的。ArrayDeque实现了Deque接口addFirst/removeFirst/addLast/removeLast四个核心方法把两端操作都覆盖了。它既能当成栈来用也能当成队列来用。官方甚至直接建议用ArrayDeque代替Stack类因为Stack继承自Vector方法用synchronized锁了一整套在单线程场景下只会白白牺牲性能。那为什么不直接用LinkedList当双端队列LinkedList也实现了Deque接口而且增删头尾都是 O(1)。但它的问题是每个元素都是一个Node节点里面有前驱指针、后继指针和item内存开销大节点在堆里散落分布遍历时 CPU 缓存不友好。ArrayDeque用一块连续的Object[]存储元素没有节点对象内存紧凑遍历效率高。代价就是扩容时要搬一次数组但这个成本摊到大量操作后是完全划算的。1.2 循环数组为什么不是“每次移动都搬数据”普通数组队列最尴尬的是什么队头出队之后下标 0 的位置空出来了但后续入队只能往 tail 后面加前面空着也用不上。等 tail 走到数组末尾明明数组前方还有空位却不得不做一次数据搬移甚至直接扩容。这个“假溢出”问题在队列场景里特别烦人。ArrayDeque的解法是循环数组。逻辑上把数组的首尾连成一个环head指向队列头部元素tail指向下一个空位。当指针走到数组尾部时通过位运算自动绕回开头数组里就不会有“明明有空位却用不上”的情况。我常用一个比方普通数组队列像一条单行道车开到终点只能掉头循环数组像环形跑道跑完一圈接着跑下一圈不需要掉头。head和tail根据操作方向往前或往后移动谁都不需要搬移数据只有数组真正满了才扩容。2. 关键字段与底层魔法的代码级拆解2.1 elements、head、tail 三个字段的关系ArrayDeque的核心字段非常少在 JDK 源码里就是三个transient Object[] elements; transient int head; transient int tail;elements是真正存数据的数组。head指向队列头部元素所在的物理下标。tail指向下一次addLast时元素应该放入的位置。这里有第一个大坑tail不是最后一个元素的下标而是最后一个元素的下一个空位下标。比如队列逻辑顺序是[A, B, C]数组物理排列可能是[A, B, C, null]此时head0、tail3最后一个元素 C 的下标是 2不是 3。当队列为空时head和tail相等都指向某个位置。当队列满时head和tail也会相等因为尾指针追上了头指针。这就引出一个问题既然空和满都可能head tail怎么区分答案藏在扩容逻辑里。ArrayDeque的设计是一旦在插入元素后检测到tail撞上了head立刻触发扩容把数组长度翻倍让head和tail重新拉开距离。所以从外部观察head tail绝大多数情况下代表空队列而“满队列且指针重合”只是一个极短的中间状态扩容后立刻消失。2.2 索引移动中的位运算技巧循环数组里指针移动不是简单地head或tail而是要用位运算来实现环形回绕。看两个核心操作head (head - 1) (elements.length - 1); tail (tail 1) (elements.length - 1);假设数组长度是 8二进制是1000长度减 1 是0111。任何整数和0111做按位与都等价于对 8 取模而且负数也能正确处理。比如head当前是 0执行head - 1得到 -1-1 7的结果是 7这样头指针就绕到了数组末尾。tail同理当tail是 7 时(7 1) 7 0尾指针绕回开头。为什么用位运算而不是取模一方面按位与比取模运算更快老版本 JVM 里尤其明显另一方面(tail 1) (length - 1)这种写法在 C/C 风格的算法里也很常见能保证结果永远落在[0, length-1]区间内。前提是数组长度必须是 2 的幂。如果长度是 6减 1 得到 5二进制101tail 1与 5 运算后并不等价于对 6 取模循环回绕就乱了。这就是ArrayDeque强制长度必须是 2 的幂的根本原因。2.3 扩容机制doubleCapacity 是怎么做到一次搬迁的ArrayDeque扩容方法叫doubleCapacity名字很直白容量翻倍。源码大致是这样的逻辑private void doubleCapacity() { int p head; int n elements.length; int r n - p; Object[] a new Object[n 1]; System.arraycopy(elements, p, a, 0, r); System.arraycopy(elements, 0, a, r, p); elements a; head 0; tail n; }这里最关键的是“分两段复制”。因为旧数组的存储顺序是循环的逻辑顺序从head开始先走到数组末尾再绕回数组头部最后停在tail前的空位。扩容时要把这一段连续的逻辑顺序搬到新数组的头部就得先复制head到数组尾部这一段再复制数组头部到tail那一段。举个例子数组长度 8head5tail4那么逻辑顺序是下标 5、6、7、0、1、2、3 上的元素。第一段复制下标 5、6、7长度r 8 - 5 3第二段复制下标 0、1、2、3长度正好是p 5。两段在新数组里拼成连续的 0 到 7。复制完成后head重置为 0tail设为旧容量 8新数组前 8 个位置全部是有效元素后面 8 个位置待用。这样设计的好处除了保持逻辑顺序连续之外还让后续遍历非常顺畅。新数组里元素都挨在一起CPU 缓存命中率高迭代器也不需要再额外判断环绕。3. 让底层原理可视化三种实操方案3.1 方案一命令行 ASCII 可视化最直接的方式就是自己写一个简易版ArrayDequeVisualizer在每次操作后把数组物理结构、head、tail、逻辑顺序全部打印出来。这个方法不需要额外依赖一个.java文件就能跑也是最容易理解核心原理的方式。我先写一个简化版实现主要模拟四个核心方法import java.util.Arrays; public class ArrayDequeVisualizer { private Object[] elements; private int head; private int tail; private int size; public ArrayDequeVisualizer(int capacity) { elements new Object[capacity]; head tail size 0; } private void doubleCapacity() { int p head; int n elements.length; int r n - p; Object[] a new Object[n 1]; System.arraycopy(elements, p, a, 0, r); System.arraycopy(elements, 0, a, r, p); System.out.println( 触发扩容: n - (n 1)); elements a; head 0; tail n; } public void addLast(Object e) { elements[tail] e; tail (tail 1) (elements.length - 1); if (tail head) { doubleCapacity(); } size; printState(addLast( e )); } public void addFirst(Object e) { head (head - 1) (elements.length - 1); elements[head] e; if (head tail) { doubleCapacity(); } size; printState(addFirst( e )); } public void removeFirst() { Object r elements[head]; elements[head] null; head (head 1) (elements.length - 1); size--; printState(removeFirst - r); } public void removeLast() { tail (tail - 1) (elements.length - 1); Object r elements[tail]; elements[tail] null; size--; printState(removeLast - r); } private void printState(String op) { System.out.println(操作: op); System.out.println(物理数组: Arrays.toString(elements)); System.out.println(head head , tail tail , size size); System.out.print(逻辑顺序: ); if (size 0) { System.out.println(空); } else { for (int i 0; i size; i) { int idx (head i) (elements.length - 1); System.out.print(elements[idx]); if (i size - 1) System.out.print( - ); } System.out.println(); } System.out.println(); } public static void main(String[] args) { ArrayDequeVisualizer queue new ArrayDequeVisualizer(4); queue.addLast(A); queue.addLast(B); queue.addLast(C); queue.addLast(D); queue.addFirst(E); queue.removeLast(); } }这段代码里printState是核心。它打印三个信息物理数组是什么样、head和tail分别在哪、逻辑顺序如何。运行后你会看到类似这样的输出操作: addLast(A) 物理数组: [A, null, null, null] head0, tail1, size1 逻辑顺序: A 操作: addLast(B) 物理数组: [A, B, null, null] head0, tail2, size2 逻辑顺序: A - B这种输出比单纯看源码直观得多。特别是数组扩容时打印出来的“ 触发扩容”能让调试者一眼看出扩容发生的时机。3.2 方案二用调试器直接观察内存如果你不想额外写代码也可以直接在 IDEA 或 Eclipse 里打断点调试。在addFirst、addLast、removeFirst等方法的内部打断点然后通过 Debug 面板观察elements数组、head、tail三个变量的变化。我比较推荐的做法是在elements数组那行右键选择“View as - Array”IDEA 会展开数组内容。配合表达式求值功能选中Arrays.toString(elements)可以快速看到数组当前内容。这里有一个坑IDEA 的展开视图默认只显示数组物理下标head和tail对应的位置不会自动标识你得手动对着数组下标算。所以我更常做的是在调试器底部调用printState这样的方法直接把逻辑顺序打出来省得自己在脑子里绕圈子。如果是观察扩容可以在doubleCapacity方法里打条件断点或者在调试器里用“Method Breakpoint”监控doubleCapacity被调用。这样当容量翻倍时你能在调用栈里清楚看到是哪一个 add 操作触发的扩容旧数组和新数组的内容变化也会一目了然。3.3 方案三HTML/JS 动画可视化如果你想做一个更生动的可视化工具或者拿去讲课分享可以用前端三件套做一个交互式演示页。核心思路很简单把数组渲染成一行格子每个格子显示元素内容head位置用绿色高亮tail位置用蓝色高亮左侧放四个按钮点击后调用对应的 JS 方法操作完成后重新渲染页面。一个最简渲染函数大概是这样的function render() { const container document.getElementById(array); container.innerHTML ; for (let i 0; i elements.length; i) { const cell document.createElement(div); cell.className cell; cell.textContent elements[i] null ? : elements[i]; if (i head) cell.classList.add(head-marker); if (i tail) cell.classList.add(tail-marker); container.appendChild(cell); } document.getElementById(state).textContent head head , tail tail , size size; }然后addFirst、addLast、removeFirst、removeLast四个 JS 方法里要么直接模拟 JDK 逻辑要么用fetch调一个 Java 后端的接口返回状态。后者适合做教学演示前者适合纯前端自娱自乐。如果你会用 CSStransition还可以给格子里的元素加上移动动画看起来就像元素在环形跑道上跑步一样。4. 实操过程一步一步画出队列的状态4.1 从空队列开始addLast 压入元素我们用容量为 4 的数组做演示模拟连续四次addLast。这是最基础、也最容易理解的操作序列。初始状态物理数组: [null, null, null, null] head0, tail0, size0 逻辑顺序: 空第一次addLast(A)A 放在下标 0tail移动到 1。操作: addLast(A) 物理数组: [A, null, null, null] head0, tail1, size1 逻辑顺序: A第二次addLast(B)B 放在下标 1tail移动到 2。操作: addLast(B) 物理数组: [A, B, null, null] head0, tail2, size2 逻辑顺序: A - B第三次addLast(C)C 放在下标 2tail移动到 3。操作: addLast(C) 物理数组: [A, B, C, null] head0, tail3, size3 逻辑顺序: A - B - C第四次addLast(D)这是关键一步。D 先放在下标 3然后tail变成(3 1) 3 0和head相等触发扩容。扩容后数组长度为 8新的物理数组变为[A, B, C, D, null, null, null, null]head0tail4。输出像这样操作: addLast(D) 触发扩容: 4 - 8 物理数组: [A, B, C, D, null, null, null, null] head0, tail4, size4 逻辑顺序: A - B - C - D注意这里扩容发生在addLast方法完成之前。也就是说调用addLast(D)返回后容量已经不是 4 而是 8。这个细节不画出来真的很难注意。4.2 addFirst 与环绕游标从尾部绕到头部addLast是从tail方向填充比较简单。addFirst就要考验你对循环数组的理解了。我们再开一个容量为 4 的队列连续执行addFirst。初始状态head0, tail0。第一次addFirst(A)操作: addFirst(A) head (0 - 1) 3 3 物理数组: [null, null, null, A] head3, tail0, size1 逻辑顺序: A注意A 没有放在数组开头而是放在数组末尾的下标 3。因为addFirst要求新元素插入到逻辑头部而头部前面的位置在循环数组里是下标 3。继续addFirst(B)操作: addFirst(B) head (3 - 1) 3 2 物理数组: [null, null, B, A] head2, tail0, size2 逻辑顺序: B - A继续addFirst(C)操作: addFirst(C) head (2 - 1) 3 1 物理数组: [null, C, B, A] head1, tail0, size3 逻辑顺序: C - B - A继续addFirst(D)操作: addFirst(D) head (1 - 1) 3 0 物理数组: [D, C, B, A] head0, tail0, size4 触发扩容: 4 - 8 物理数组: [D, C, B, A, null, null, null, null] head0, tail4, size4 逻辑顺序: D - C - B - A这个例子里的扩容时机也很关键插入 D 后head变成了 0和tail相等说明数组已经满到“头尾相接”于是扩容把整个数组搬到长度 8 的新数组里。head回到 0tail变成旧容量 4。4.3 扩容瞬间从长度 4 扩容到 8 的状态迁移上面的例子扩容时head恰好是 0所以只复制了一段。如果head不在 0 呢比如旧数组长度 8经过一系列双端操作后head5tail4数组物理内容大致是下标: 0:A 1:B 2:C 3:D 4:null 5:Z 6:Y 7:X head5, tail4逻辑顺序从head开始Z - Y - X - A - B - C - D。此时再执行一次addFirst(W)head变成(5 - 1) 7 4W 放在下标 4然后head和tail都变成 4触发扩容。扩容时p head 4r 8 - 4 4。第一段把下标 4 到 7 复制到新数组头部也就是W, Z, Y, X第二段把下标 0 到 3 复制到新数组下标 4 到 7也就是A, B, C, D。最终新数组长度 16结构如下下标: 0:W 1:Z 2:Y 3:X 4:A 5:B 6:C 7:D 8~15:null head0, tail8看到没有新数组的前 8 个元素完全按照旧数组的逻辑顺序排列而不是简单地把旧数组物理顺序复制一遍。这就是doubleCapacity分两段复制的意义。5. 常见误区与排查技巧实录5.1 为什么 ArrayDeque 里不能放 nullArrayDeque的addFirst和addLast开头都有一句if (e null) throw new NullPointerException()。很多人不理解为什么LinkedList能放 nullArrayDeque不行因为循环数组的实现依赖elements[i] null来判断某个槽位是否为空。如果允许用户传入 null整个数组里就会出现“真正的空位”和“null 元素”无法区分的情况。removeFirst读取元素时拿到 null 到底是该返回这个 null 元素还是该认为这里没有元素这就造成了语义混乱。所以ArrayDeque干脆禁止 null换来了实现上的清晰。这在可视化里也能看到我用null表示空位所以数组里的 null 永远代表“没有元素”。5.2 容量为什么永远得是 2 的幂如果你用new ArrayDeque(5)指定容量为 5它实际分配的数组长度并不是 5而是 8指定 33会得到 64。就是因为必须保证容量是 2 的幂否则(head - 1) (length - 1)这种位运算不能正确实现循环取模。有人可能会问如果容量不是 2 的幂我用真正的取模%不行吗理论上可以但ArrayDeque为了性能选择了位运算。更重要的是这个约束让很多判断变得更简单。比如扩容时直接把旧容量左移一位新容量必然是 2 的幂tail的计算也不会出现负数或越界。如果你自己写类似的循环队列我建议也保持这个约束不然各种边界条件会让你怀疑人生。5.3 可视化时最容易被绕晕的三个问题我见过不少人在画ArrayDeque状态图时越画越乱主要就是这三个原因第一把tail当成最后一个元素的下标。如果你在逻辑顺序展示里从head开始一直打印到tail - 1当tail是 0 时会变成负数或者打印出一个不应该出现的元素。正确做法是记录size然后从head开始连续打印size个元素。第二扩容后还盯着旧的下标看。扩容会创建全新的数组旧数组被整体丢弃head归零tail变成旧容量。如果拿扩容前的下标去框新数组会觉得数据“乱序”了其实只是参照系变了。我在可视化工具里会特别打印“ 触发扩容”提醒自己此刻所有下标都要重新理解。第三认为物理顺序必须等于逻辑顺序。物理顺序是从数组下标 0 开始看到的排列逻辑顺序是从head开始沿循环方向走一圈的顺序。在addFirst操作较多时两者往往不一致。比如容量 4 连续四次addFirst之后物理数组是[D, C, B, A]逻辑顺序却是D - C - B - A两者恰好一致但如果混用addFirst和addLast就会经常出现物理上“首尾分离”的情况。5.4 从可视化中发现的性能启示把状态画出来之后很多关于性能的结论就变得直观了。比如老话说ArrayDeque比LinkedList快快在哪儿从可视化能看到ArrayDeque操作元素时只改一个数组下标不需要创建节点遍历时从head到tail连续访问数组CPU 缓存友好。而LinkedList每次遍历都要沿着指针跳转节点散落内存中缓存命中率差。再比如扩容的成本。从可视化中可以看到ArrayDeque采用“倍增”策略容量从 4 扩到 8再到 16、32扩容次数是指数级收敛的。假设最终队列里有 1000 个元素最多也就扩容十几次而且每次扩容只搬一次数组均摊到每次 add 操作上成本极低。这也是为什么大量入队操作下ArrayDeque依然能保持很高的整体性能。6. 把可视化思路延伸到更多集合类6.1 可视化小工具还能怎么玩这个可视化方法不只适用于ArrayDeque。我后来用同一套思路画过LinkedList、HashMap和PriorityQueue每个都能得到意想不到的收获。原理相同底层结构越抽象就越需要把它“拍平”成具体的内容让数据结构的变化过程肉眼可见。比如HashMap的可视化重点是要同时展示桶数组和链表/红黑树的结构扩容时的resize过程旧数组中的每个节点如何重新计算位置如果不画出来很难真正理解为什么并发环境下老版本的扩容会形成环。再比如PriorityQueue可视化时可以直接把数组下标对应的堆结构画成二叉树上下浮动的过程一目了然。做法上先输出操作后的物理数组内容和关键指针再慢慢叠加更复杂的渲染。命令行打印永远是最省事的起点因为它在任何环境都能跑而且强迫你精确描述每一步的状态。6.2 我的一点实操体会我个人最开始看ArrayDeque源码时总觉得tail指向空位这个设计很别扭直到自己动手写了个打印工具把addFirst的环绕过程和扩容的两次复制都输出出来才算真正理解。后来我给同事分享这套可视化思路时大家都反映“看懂图片比看懂源码快得多”。如果你也在啃 Java 集合源码我建议别只盯着代码可以像我一样写一个几十行的调试工具把每个关键步骤打印出来。一次操作打印一行配上下标和指针很快就能形成直觉。后面再看那些“性能为什么好”“为什么容量必须是 2 的幂”之类的问题就不需要死记硬背了。亲手画过一遍比看十篇文章都管用。