ArrayDeque

ℹ️定位说明

Queue 系列第 1 篇详篇。官方推荐的栈/队列实现：循环数组，头尾操作均摊 O(1)，比 LinkedList 快（无节点分配、内存连续）。本篇含循环数组的扩容与下标回绕机制。

ArrayDeque：高性能双端队列

一、基本概念

ArrayDeque 是 Java 提供的一种基于动态数组实现的双端队列（Deque），支持高效的栈（LIFO）与队列（FIFO）操作，是 Deque 接口的一个重要实现类。

public class ArrayDeque<E> extends AbstractCollection<E>

        implements Deque<E>, Cloneable, Serializable

它具备以下特点：

特性	说明
底层结构	循环数组（动态扩容）
支持双端操作	支持从头尾插入和删除
非线程安全	多线程下需手动同步
不允许 null 元素	防止和空返回值歧义
相比 LinkedList 更高效	访问局部性更好，GC 压力更小，操作更快

二、底层结构与数据模型

ArrayDeque 使用一个循环数组 elements[] 来存储数据，并用两个指针标记头尾：

head: 指向队首元素位置
tail: 指向下一个插入队尾的位置

数组逻辑结构示意：

    tail

     ↓

[ _ _ B C D _ _ A ]

         ↑

       head

插入或删除时通过环形偏移计算位置，从而实现 O(1) 的效率。

三、添加元素 —— offerFirst / offerLast

public void addFirst(E e) {

    if (e == null) throw new NullPointerException();

    elements[head = (head - 1) & (elements.length - 1)] = e;

    if (head == tail) resize();

}

public void addLast(E e) {

    if (e == null) throw new NullPointerException();

    elements[tail] = e;

    tail = (tail + 1) & (elements.length - 1);

    if (tail == head) resize();

}

说明：

采用位运算 (index ± 1) & (length - 1) 代替取模 %，更高效（前提是数组长度为 2 的幂）
判断队满：插入后 head == tail，说明已满，触发扩容
插入前不允许为 null，防止与 poll() 返回 null 混淆

四、删除元素 —— pollFirst / pollLast

public E pollFirst() {

    int h = head;

    E result = elements[h];

    if (result == null) return null;

    elements[h] = null; // 清除引用，便于 GC

    head = (h + 1) & (elements.length - 1);

    return result;

}

public E pollLast() {

    int t = (tail - 1) & (elements.length - 1);

    E result = elements[t];

    if (result == null) return null;

    elements[t] = null;

    tail = t;

    return result;

}

说明：

删除后指针推进，释放数组槽位，避免内存泄漏
仍采用环形偏移保证索引安全

五、扩容机制 —— resize()

扩容触发时，ArrayDeque 会将旧数据从 head 开始顺序复制到新数组中：

private void resize() {

    int oldCapacity = elements.length;

    int newCapacity = oldCapacity << 1; // 扩容为原来的2倍

    Object[] newArray = new Object[newCapacity];

    int r = oldCapacity - head; // 从head到数组末尾的元素个数

    System.arraycopy(elements, head, newArray, 0, r);

    System.arraycopy(elements, 0, newArray, r, head);

    elements = newArray;

    head = 0;

    tail = oldCapacity;

}

核心要点：

扩容为原数组的 2 倍（比 ArrayList 的 1.5 倍更保守）
采用双段拷贝的方式解决循环结构问题
拷贝代价较大，建议合理初始化容量

六、典型应用场景

场景	示例
栈（LIFO）	`push()` / `pop()`
队列（FIFO）	`offerLast()` / `pollFirst()`
双端队列	支持头尾任意插入删除
缓存/滑动窗口	固定容量 + 头部淘汰策略实现

七、和 LinkedList 的对比

维度	ArrayDeque	LinkedList
底层结构	循环数组	双向链表
头尾插入删除效率	O(1)	O(1)
中间插入删除	不支持	O(n)
内存占用	紧凑（数组）	高（每个节点有两个引用）
是否支持 null	❌（抛出异常）	✅
线程安全	❌	❌

推荐：一般建议使用 ArrayDeque 替代 LinkedList 作为栈或队列的实现。

八、示例代码

Deque<String> deque = new ArrayDeque<>();

// 队列用法

deque.offerLast("a");

deque.offerLast("b");

System.out.println(deque.pollFirst()); // 输出 a

// 栈用法

deque.push("x");

deque.push("y");

System.out.println(deque.pop()); // 输出 y

九、注意事项总结

不允许存储 null 元素
非线程安全，需外部加锁或使用并发容器（如 ConcurrentLinkedDeque）
不支持元素随机访问（无索引）
插入删除性能优越，推荐作为双端队列使用

⬅️ 00-Queue和Deque总览 🏠 00-Java ➡️ PriorityQueue

01-ArrayDeque