Java中 ArrayDeque 如何通过循环数组实现双端队列与无锁高效栈

ArrayDeque是基于循环数组实现的双端队列，通过head/tail双指针与位运算实现头尾O(1)操作，内存连续、缓存友好，支持高效栈/队列模式，非线程安全且不支持null。

ArrayDeque 是 Java 中基于循环数组实现的双端队列（Deque），它同时支持高效地在头尾两端添加/删除元素，也常被用作高性能栈（LIFO）。它的核心优势在于无锁（lock-free）设计、内存局部性好、扩容策略合理，且所有操作平均时间复杂度为 O(1)。

循环数组如何支撑双端操作

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 锁或原子操作来保证线程安全，而是通过纯数组 + 索引运算实现原子性操作。其高效性来自：

立即学习“Java免费学习笔记（深入）”；

• 连续内存布局：数组在内存中连续，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），但不保证反映最新状态

不复杂但容易忽略。