ArrayDeque 是 Java 里基于动态循环数组实现的双端队列，一般用作栈或普通队列，性能比 LinkedList、Stack 更好，日常开发优先用它。

1.核心特点

• 底层：可变长循环数组，头尾指针，支持自动扩容。
• 不允许 null；非线程安全；两端增删均为 O(1)。
• 实现：Deque → Queue → Collection → Iterable。

2.常用方法

1. 添加（头部 / 尾部）

• addFirst(e) / offerFirst(e)：头插
• addLast(e) / offerLast(e)：尾插
• push(e)：等价 addFirst(e)（栈）

2. 删除（头部 / 尾部）

• removeFirst() / pollFirst()：删头
• removeLast() / pollLast()：删尾
• pop()：等价 removeFirst()（栈）

3. 查看（不删）

• getFirst() / peekFirst()：看头
• getLast() / peekLast()：看尾
• peek()：等价 peekFirst()

区别：add/get/remove 为空抛异常；offer/poll/peek 为空返回 null。

3.经典用法

1. 当作栈（LIFO，推荐替代 Stack）

ArrayDeque<String> stack = new ArrayDeque<>();
stack.push("A"); // 入栈（头插）
stack.push("B");
stack.push("C");

while (!stack.isEmpty()) {
    System.out.println(stack.pop()); // C → B → A
}

2. 当作队列（FIFO，推荐替代 LinkedList）

ArrayDeque<String> queue = new ArrayDeque<>();
queue.offer("A"); // 入队（尾插）
queue.offer("B");
queue.offer("C");

while (!queue.isEmpty()) {
    System.out.println(queue.poll()); // A → B → C
}

3. 双端操作

ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1); // 头
deque.addLast(2);  // 尾
deque.addFirst(0);

System.out.println(deque); // [0, 1, 2]
System.out.println(deque.removeFirst()); // 0
System.out.println(deque.removeLast());  // 2

4.与 LinkedList / Stack 对比

特性	ArrayDeque	LinkedList	Stack
实现	循环数组	双向链表	数组（线程安全）
增删（两端）	O(1)	O(1)	O(1)
随机访问	❌	❌	✅
内存开销	低（数组连续）	高（节点 + 指针）	中
线程安全	❌	❌	✅（但慢）
栈性能	最快	较快	慢
队列性能	最快	较快	—

结论：无并发时，栈 / 队列优先用 ArrayDeque。

5.源码

1.继承实现

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable

实现了 Deque 双端队列接口，具备队列、栈、双端队列全部能力。

2.核心三大成员

// 底层存储：循环数组，长度永远是 2 的幂次方
transient Object[] elements;

// 头指针：指向队列第一个元素位置
transient int head;

// 尾指针：指向**下一个要插入元素的空位**
transient int tail;

// 默认最小容量
private static final int MIN_INITIAL_CAPACITY = 8;

• elements 数组长度必须是 2 的整数次幂（8、16、32、64...），为了取模运算优化；
• head：队首元素下标；
• tail：不是最后一个元素，是下一个待插入的空位置；
• 不允许存储 null。

3.构造方法

无参构造

public ArrayDeque() {
    elements = new Object[16]; // 默认容量16，2的幂
}

指定初始容量构造

public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

allocateElements 作用：算出大于传入值的最小 2 的幂

比如：

• 传 5 → 实际容量 8
• 传 10 → 实际容量 16
• 传 16 → 还是 16

底层通过位运算快速向上取整为 2 的幂

6.注意事项

• 禁止 null：插 null 直接空指针。
• 非线程安全：多线程需手动同步或用 Collections.synchronizedDeque。
• 容量：无界，自动扩容；默认初始 16，可指定初始容量 new ArrayDeque<>(32)。

7.常见应用场景

• 栈 / 队列（高频）
• 滑动窗口最大值（LeetCode 239）
• BFS/DFS 搜索
• 浏览器前进后退历史记录