Java ArrayDeque 循环数组实现双端队列与无锁高效栈

先说说 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），但不保证反映最新状态

这些细节虽然不复杂，但确实容易被忽略。在实际开发中，选对数据结构往往比算法优化更见效。