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 锁或原子操作来保证线程安全，而是通过纯数组 + 索引运算实现原子性操作。其高效性来自：
- 连续内存布局：数组在内存中连续，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），但不保证反映最新状态
不复杂但容易忽略。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
