先说说 ArrayDeque 的核心设计思路。它本质上是一个基于循环数组实现的双端队列，在 Java 中属于那种看似普通、实则性能非常出色的数据结构。头尾两端都能高效操作，且所有操作的平均时间复杂度均为 O(1)，这背后依靠的是 head/tail 双指针与位运算的巧妙配合。
很多开发者一提到栈和队列，第一时间想到的就是 Stack 或 LinkedList，但实际上 ArrayDeque 在许多场景下是更优的选择。它的核心优势包括：内存连续带来的缓存友好性、无锁（lock-free）设计，以及合理的扩容策略。这里所说的“无锁”并非指多线程环境下的并发安全，而是指它本身不依赖任何锁或 CAS 原子操作来保证线程安全，完全依靠数组和索引运算完成所有操作。
循环数组如何支撑双端操作
ArrayDeque 内部维护一个可动态扩容的 Object[] 数组（elements），并使用两个索引：head（指向队首元素）和 tail（指向下一个可插入位置）。数组在逻辑上首尾相连，构成环形结构：
- 头插（
addFirst）：先将head减 1（取模数组长度），然后写入；若 head 越界则绕回数组末尾 - 尾插（
addLast）：直接在tail位置写入，再将tail加 1（取模数组长度） - 头删（
removeFirst）：读取head位置元素，再将head加 1（取模长度） - 尾删（
removeLast）：先将tail减 1（取模长度），再读取该位置元素
这种设计避免了传统链表的节点分配开销，也解决了 ArrayList 头部插入性能差的问题。可以说，这是用数组结构的一些代价，换来了双端操作的高效性。
无锁高效的关键机制
ArrayDeque 所有 public 方法都是单线程安全的（非并发安全），但它本身不使用 synchronized 或 CAS，因此被称为“无锁”设计——这里的“无锁”指不依赖 JVM 锁或原子操作来保证线程安全，而是通过纯数组 + 索引运算实现原子性操作。其高效性主要来自：
- 连续内存布局结构：数组在内存中连续，CPU 缓存友好，访问 head/tail 附近元素命中率高
- 索引计算仅使用位运算：当数组容量为 2 的幂时（ArrayDeque 总是扩容为 2^n），
(index - 1) & (elements.length - 1)替代取模，速度极快 - 懒扩容策略，均摊时间复杂度为 O(1)：初始容量为 16，满时翻倍；头插导致 head 绕回碰撞时才扩容，避免频繁搬移
作为栈使用的天然适配性
ArrayDeque 提供了 push/pop/peek 方法，语义与栈操作完全一致，且相比于 Stack（基于 Vector，同步且继承自过时类）和 LinkedList（节点对象多、GC 压力大）具有明显优势：
push(e)→addFirst(e)pop()→removeFirst()peek()→getFirst()
由于栈操作只发生在一端（头端），ArrayDeque 此时退化为“单端增长的数组栈”，无 head/tail 冲突，缓存更集中，性能接近原生数组栈。
注意事项与典型误用
尽管高效，但在使用时仍需注意以下事项：
- 非线程安全容器：多线程环境下需要外部同步（如
Collections.synchronizedDeque）或改用ConcurrentLinkedDeque（但后者是链表，无 ArrayDeque 的缓存优势） - 不允许插入 null 元素：插入 null 会抛
NullPointerException，这一点比 LinkedList 更严格 - 扩容存在一定代价：虽然均摊 O(1)，但单次扩容需复制整个数组，大数据量下可能引发短暂停顿
- 迭代器具有弱一致性：遍历时允许并发修改（不抛 ConcurrentModificationException），但不保证反映最新状态
这些细节虽然不复杂，但确实容易被忽略。在实际开发中，选择合适的数据结构往往比算法优化更为有效。
