arraydeque是基于循环数组实现的双端队列，不支持null、非线程安全；通过head/tail索引与位运算（容量为2的幂）实现高效首尾操作，扩容时翻倍并重排元素。
ArrayDeque 是 Java 中基于循环数组实现的双端队列（Deque），它不支持 null 元素，且线程不安全，但性能优于 LinkedList（尤其在头尾操作上）。它的核心在于用一个普通数组 + 两个索引（head 和 tail）模拟“首尾均可增删”的逻辑，而**不真正移动元素**，靠索引绕回实现空间复用。
循环数组的关键设计：head 和 tail 的含义
ArrayDeque 内部维护一个数组 elements[] 和两个 int 字段：
-
head：指向队列**第一个元素**的位置（即elements[head]是队首）；初始为 0。 -
tail：指向队列**下一个可插入位置**（即新元素将放在elements[tail]）；初始为 0。
注意：tail 不是最后一个元素下标，而是“待插入位”，所以队列长度 = (tail - head) & (elements.length - 1)（前提是容量为 2 的幂）。
为什么容量必须是 2 的幂？
ArrayDeque 在扩容时总是将容量设为大于等于所需大小的最小 2 的幂（如 1→2→4→8…）。这样做的根本目的是用位运算替代取模，高效实现循环索引：
- 获取第 i 个元素：
elements[(head + i) & (elements.length - 1)] - 前进 head（出队首）：
head = (head + 1) & (elements.length - 1) - 前进 tail（入队尾）：
tail = (tail + 1) & (elements.length - 1)
因为当 length = 2ⁿ 时，length - 1 的二进制是 n 个 1（如 8−1=7 → 0b111），& 运算等价于对 length 取模，且无分支、无溢出风险，比 % 快得多。
头尾插入/删除如何避免数据搬移？
所有操作都只更新 head/tail 索引，数组内容不动：
-
addFirst(e)：先让
head = (head - 1) & (len-1)，再赋值elements[head] = e。 -
addLast(e)：先赋值
elements[tail] = e，再让tail = (tail + 1) & (len-1)。 -
removeFirst()：读
elements[head]，再head = (head + 1) & (len-1)。 -
removeLast()：先
tail = (tail - 1) & (len-1)，再读elements[tail]。
例如初始空 deque（len=8, head=0, tail=0）：
→ addFirst(1)：head 变为 7，elements[7]=1；
→ addLast(2)：elements[0]=2，tail 变为 1；
此时队列为 [1,2]，实际存储为 elements[7]=1, elements[0]=2 —— 物理不连续，逻辑首尾分明。
扩容机制：如何保持循环性？
当 tail == head 且有新元素要加入时（即数组满），触发扩容。新数组长度翻倍（仍为 2 的幂），然后将旧数组中从 head 到 tail−1 的元素（跨边界时分两段拷贝）按顺序复制到新数组开头，重置 head=0，tail=旧 size。
例如旧数组 len=4, head=3, tail=3（满），元素分布在 elements[3], [0], [1], [2]；扩容后新数组 len=8，这 4 个元素被依次拷贝到新数组的索引 0~3，head=0, tail=4 —— 循环结构被“拉直”重建，后续操作继续高效循环。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
