双端队列的核心特点在于 在队列的两端进行插入和删除操作，在队列的 前端Front 和 后端Rear 高效地进行插入和删除操作。它融合了 普通队列（先进先出 - FIFO）和 栈（后进先出 - LIFO）的特性

public interface Deque<E> extends Queue<E> {}

Deque 方法简介

比起基本队列Deque 为每种操作（插入、移除、检查）在队列的两端（头部和尾部）都提供了两组方法。一组在操作失败时抛出异常，另一组则返回特殊值（通常是 null 或 false）。

操作	头部 (Front/First)	尾部 (Rear/Last)
插入	addFirst(e) / offerFirst(e)	addLast(e) / offerLast(e)
	失败抛异常 / 失败返回 false	失败抛异常 / 失败返回 false
移除	removeFirst() / pollFirst()	removeLast() / pollLast()
	空队列抛异常 / 空队列返回 null	空队列抛异常 / 空队列返回 null
检查	getFirst() / peekFirst()	getLast() / peekLast()
查看不删除	空队列抛异常 / 空队列返回 null	空队列抛异常 / 空队列返回 null
栈操作	push(e) (等价于 addFirst(e))
	pop() (等价于 removeFirst())
	peek() (等价于 peekFirst())
队列操作	remove() (等价于 removeFirst())	add(e) (等价于 addLast(e))
(继承自Queue)	poll() (等价于 pollFirst())	offer(e) (等价于 offerLast(e))
	element() (等价于 getFirst())
	peek() (等价于 peekFirst())
其他	removeFirstOccurrence(Object o)	removeLastOccurrence(Object o)
	从前往后移除第一个匹配元素，成功返回true	从后往前移除第一个匹配元素，成功返回true
	contains(Object o)	size()
	iterator()	descendingIterator() (从尾到头遍历)

Deque 核心特点

1.双端操作
这是Deque的核心。你可以在队列的头部和尾部执行插入、删除和检查操作

2.替代角色

• 作为队列 (FIFO)： 使用 addLast(e) / offerLast(e) 添加元素到尾部，使用 removeFirst() / pollFirst() 从头部移除元素
• 作为栈 (LIFO)： 使用 push(e) / addFirst(e) 添加元素到头部（压栈），使用 pop() / removeFirst() 从头部移除元素（弹栈），使用 peek() / peekFirst() 查看栈顶元素而不移除，使用push(e), pop(), peek()时，明确表示你在将Deque当作栈使，Deque 是官方推荐替代遗留 Stack 类的方案

3.容量限制
某些 Deque 实现（如 ArrayDeque）可能有固定容量限制。尝试在满队列中添加元素可能会导致异常或返回特殊值（取决于具体方法）

4.Null元素
Deque 的实现类可以允许或不允许null元素。ArrayDeque不允许null元素，而LinkedList允许。使用 null 元素时要特别小心，因为某些方法（如 removeFirstOccurrence(null)）可能会产生歧义

5.非线程安全
Deque的标准实现类（ArrayDeque, LinkedList）不是线程安全的。线程安全方式使用外部同步机制（如 Collections.synchronizedDeque()）或使用并发包下的实现（如 LinkedBlockingDeque）

Deque实现类 ArrayDeque

ArrayDeque实现了Deque接口，基于动态数组的数据提供了双端队列的功能

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

ArrayDeque 构造方法

1.无参构造默认容量 16

// 创建一个初始容量为16的空队列
Deque<String> names = new ArrayDeque<>(); 

2.创建一个具有指定初始容量的空双端队列

//预分配足够空间存放大约1000个读数
Deque<Integer> sensorReadings = new ArrayDeque<>(1000); // 但注意的是 自动调整为2的幂
ArrayDeque<Integer> deque2 = new ArrayDeque<>(100); // 实际容量128

3.创建一个包含指定集合 c 中所有元素的双端队列
元素的顺序由集合的迭代器返回顺序决定

List<String> list = Arrays.asList("Apple", "Banana", "Orange");
// 创建包含["Apple", "Banana", "Orange"]的队列
Deque<String> fruitDeque = new ArrayDeque<>(list); 重要提示：
如果传入的集合 c 是 null，会抛出 NullPointerException。
如果传入的集合 c 中包含 null 元素，在添加过程中（调用 c.iterator().next() 时）
会抛出 NullPointerException，因为 ArrayDeque 不允许 null 元素

ArrayDeque 的数据结构及实现原理

数据结构

// 关键字段
transient Object[] elements; // 存储元素的数组
transient int head;          // 头部指针（指向当前首元素）
transient int tail;          // 尾部指针（指向下一个插入位置）

动态循环数组示意图
动态数组:数组的大小可随着数据量进行扩容
循环数组:数组的任何一点都可以被看作是起点或者终点

添加节点流程图

假设初始容量为 4（实际最小容量为 8，但为简化演示使用 4）初始状态
数组：[null, null, null, null]
head = 0, tail = 0（空队列）
索引:  0     1     2     3[null, null, null, null]↑head/tail步骤 1: 尾部添加 A (addLast("A"))
在tail位置插入A，tail后移：tail = (0 + 1) & 3 = 1
索引:  0     1     2     3["A", null, null, null]↑head ↑tail步骤 2: 尾部添加 B (addLast("B"))
在 tail 位置插入 B，tail 后移：tail = (1 + 1) & 3 = 2
索引:  0     1     2     3["A", "B", null, null]↑head       ↑tail步骤 3: 头部添加 C (addFirst("C"))
head 前移：head = (0 - 1) & 3 = 3（循环到末尾） 在 head 位置插入 C
索引:  0     1     2     3["A", "B", null, "C"]↑tail ↑head步骤 4: 尾部添加 D (addLast("D"))
在 tail 位置插入 Dtail 后移：tail = (2 + 1) & 3 = 3
此时 head == tail，触发扩容！
索引:  0     1     2     3["A", "B", "D", "C"]↑head/tail? (实际 head=3, tail=3)步骤 5: 扩容（关键步骤）
计算新容量：原容量 4 → 新容量 8（翻倍）
创建新数组：[null, null, null, null, null, null, null, null]
复制元素（按逻辑顺序重排）1.从原head开始：复制索引3的 "C" → 新数组索引 02.继续循环：复制索引0的 "A" → 新数组索引 13.复制索引1的 "B" → 新数组索引 24.复制索引2的 "D" → 新数组索引 3
重置指针：
head = 0（新数组头部）
tail = 4（新数组尾部下一个空位）
新数组索引: 0    1    2    3    4    5    6    7["C", "A", "B", "D", null, null, null, null]↑head                ↑tail再新增节点
头部添加 E (addFirst("E"))
head 前移：head = (0 - 1) & 7 = 7（循环到末尾），在 head 位置插入 E
索引:  0    1    2    3    4      5     6    7["C", "A", "B", "D", null, null, null, "E"]↑tail             ↑head尾部添加 F (addLast("F"))
在 tail 位置插入 F，tail 后移：tail = (4 + 1) & 7 = 5
索引: 0    1    2    3    4     5     6     7["C", "A", "B", "D", "F", null, null, "E"]↑tail        ↑head直到两种会师 那就再次扩容 2倍扩容

删除节点流程图

头部移除 (removeFirst())
取出 head 位置元素 "E"，置空 head 位置
head 后移：head = (7 + 1) & 7 = 0
索引:  0    1    2    3    4    5     6     7["C", "A", "B", "D", "F", null, null, null]↑head                    ↑tail尾部移除 (removeLast())
tail 前移：tail = (5 - 1) & 7 = 4
取出 tail 位置元素 "F" 置空 tail 位置
索引:   0    1    2    3    4    5     6     7["C", "A", "B", "D", null, null, null, null]↑head     		  ↑tai

ArrayDeque 方法介绍

操作	方法	时间复杂度	说明
头部插入	addFirst(E), push(E)	O(1)	插入失败抛出异常
	offerFirst(E)	O(1)	插入失败返回 false
头部移除	removeFirst(), pop()	O(1)	空队列抛出异常
	pollFirst()	O(1)	空队列返回 null
头部查看	getFirst(), peek()	O(1)	空队列抛出异常
	peekFirst()	O(1)	空队列返回 null
尾部插入	addLast(E), add(E)	O(1)	插入失败抛出异常
	offerLast(E), offer(E)	O(1)	插入失败返回 false
尾部移除	removeLast()	O(1)	空队列抛出异常
	pollLast()	O(1)	空队列返回 null
尾部查看	getLast()	O(1)	空队列抛出异常
	peekLast()	O(1)	空队列返回 null
大小检查	size()	O(1)	通过 head 和 tail 计算
包含检查	contains(Object)	O(n)	线性搜索
清空	clear()	O(n)	遍历数组置 null

ArrayDeque 核心特性

1. 基于循环数组实现：
   • 底层使用动态数组（Object[]）存储元素。
   • 通过两个指针（head 和 tail）实现循环数组，head 指向队列的第一个元素，tail 指向队列末尾的下一个空位。
   • 当数组满时会自动扩容（通常翻倍），并将元素复制到新数组。
2. 高效的头尾操作：
   • 队列两端（头部和尾部）添加或移除元素的时间复杂度为 O(1)（摊销时间，因涉及扩容操作
   • 具体方法包括：
     • 头部操作：addFirst(), offerFirst(), removeFirst(), pollFirst(), getFirst(), peekFirst()
     • 尾部操作：addLast(), offerLast(), removeLast(), pollLast(), getLast(), peekLast()
3. 不允许 null 元素：
   • 试图添加 null 元素会抛出 NullPointerException。
4. 非线程安全：
   • 不是线程安全的类，如果需要在多线程环境下使用，必须通过外部同步机制（如 Collections.synchronizedDeque）来保证线程安全。
5. 迭代快速失败（Fail-Fast）：
   • 迭代器是快速失败的，如果在迭代过程中队列被修改（除了通过迭代器自身的 remove 方法），会抛出 ConcurrentModificationException。
6. 用作栈和队列：
   • 作为栈使用时（后进先出，LIFO），推荐使用 push（等同于 addFirst）和 pop（等同于 removeFirst）方法。
   • 作为队列使用时（先进先出，FIFO），推荐使用 add（等同于 addLast）和 remove（等同于 removeFirst）或 offer 和 poll 方法。
7. 性能优势：
   • 相比 LinkedList，ArrayDeque 在大多数场景下有更好的性能（尤其作为队列或栈），因为基于数组实现，内存局部性更好，减少了指针操作的开销。
8. 初始容量：
   • 默认初始容量为 16，也可以指定初始容量（必须是 2 的幂，如果不是，会自动调整为最接近的 2 的幂）。
   • 扩容策略：当数组满时，容量翻倍（变为原来的 2 倍）。
9. 元素顺序：
   • 迭代顺序是从头部（head）到尾部（tail），即队列中元素的顺序

ArrayDeque 总结

使用场景

场景	推荐操作
FIFO 队列	offerLast(e) ， pollFirst()
LIFO 栈	push(e) (=addFirst(e)) ， pop() (=removeFirst())
滑动窗口	头尾快速插入/删除（如 LeetCode 239）
任务调度	高效管理待执行任务队列
历史记录	固定容量实现 LRU（需配合移除逻辑）

注意事项

场景	原因
需要存储 null	设计禁止 null 元素
高频随机访问	按索引访问中间元素需遍历（改用 ArrayList）
多线程无锁环境	非线程安全（改用 ConcurrentLinkedDeque 或 LinkedBlockingDeque）
精确控制容量增长	扩容策略固定为翻倍（若需定制策略需自行实现）

ArrayDeque 使用样例代码

// 1. 作为栈使用（LIFO）
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);      // addFirst(1)
stack.push(2);
int top = stack.pop(); // removeFirst() → 2// 2. 作为队列使用（FIFO）
Deque<String> queue = new ArrayDeque<>(1000); // 预分配容量
queue.offer("A");   // addLast("A")
queue.offer("B");
String first = queue.poll(); // removeFirst() → "A"// 3. 双端操作
ArrayDeque<Character> deque = new ArrayDeque<>();
deque.addFirst('X'); // [X]
deque.addLast('Y');  // [X, Y]
deque.removeFirst(); // [Y]
deque.removeLast();  // []

Deque实现类 LinkedList

LinkedList是整个集合框架中最灵活的类之一，因为它同时实现了List Qeque Deque 三个数据结构
LinkedList详情介绍链接

Deque实现类 ConcurrentLinkedDeque (非阻塞线程安全)

ConcurrentLinkedDeque是线程安全的无界双端队列，采用无锁算法CAS实现，支持在队列两端进行高效并发操作。它是ConcurrentLinkedQueue的双端队列版本

public class ConcurrentLinkedDeque<E>extends AbstractCollection<E>implements Deque<E>, java.io.Serializable {}

与 基本队列的非阻塞线程安全ConcurrentLinkedQueue 对比

特性	ConcurrentLinkedDeque	ConcurrentLinkedQueue
操作端	双端（头尾操作）	单端（尾部入队，头部出队）
特殊方法	addFirst(), removeLast()	无
数据结构	双向链表	单向链表
内存开销	更高（每个节点两个指针）	较低
使用场景	更广泛	标准队列场景

ConcurrentLinkedDeque 核心特性

1.线程安全：基于无锁算法（CAS）实现
2.双端操作：支持队列头部和尾部的插入/移除
3.无界队列：理论上可无限扩展（受内存限制）
4.非阻塞：操作不会导致线程阻塞
5.FIFO/LIFO 混合：可作为队列或栈使用
6.不允许 null 元素：插入 null 会抛出 NullPointerException

阻塞和非阻塞的主要区别在于是否等待对方响应
阻塞调用是指调用结果返回之前，当前线程会被挂起，一直处于等待消息通知，不能执行其他业务
非阻塞调用指在不能立刻得到结果之前，该调用不会阻塞当前线程

ConcurrentLinkedDeque 是非阻塞线程的特性区别对比 阻塞线程的类

特性	阻塞队列 (如 ArrayBlockingQueue)	非阻塞队列 (ConcurrentLinkedDeque)
线程挂起	竞争失败时挂起等待	失败时自旋重试，无挂起
开销	上下文切换开销大	无上下文切换，仅 CPU 自旋
吞吐量	高竞争下下降显著	高并发场景下更优

简单来说：阻塞的竞争失败挂起等待，非阻塞的不挂起不断重试直到成功，所以性能开销更大点

ConcurrentLinkedDeque 方法

头部操作

• void addFirst(E e) / boolean offerFirst(E e)：头部插入元素
• E removeFirst() / E pollFirst()：移除并返回头部元素
• E getFirst() / E peekFirst()：查看但不移除头部元素

尾部操作

• void addLast(E e) / boolean offerLast(E e)：尾部插入元素
• E removeLast() / E pollLast()：移除并返回尾部元素
• E getLast() / E peekLast()：查看但不移除尾部元素

通用操作

• boolean add(E e)：尾部添加（等价于 addLast）
• E remove()：头部移除（等价于 removeFirst）
• E element() / E peek()：查看头部元素

ConcurrentLinkedDeque 数据结构和实现原理

数据结构：双向链表节点
双向链表节点结构

private static final class Node<E> {volatile Node<E> prev;  // 前驱指针volatile E item;        // 存储元素volatile Node<E> next;  // 后继指针// CAS 操作方法boolean casItem(E cmp, E val) { /*...*/ }void lazySetNext(Node<E> val) { /*...*/ }boolean casNext(Node<E> cmp, Node<E> val) { /*...*/ }// ... 类似的前驱指针操作方法
}

队列头尾指针分离

   private transient volatile Node<E> head;private transient volatile Node<E> tail;

实现原理
核心点
1.数据结构：双向链表节点（Node）
2.无锁算法：使用CAS操作更新指针
3.头尾指针：volatile修饰的头节点（head）和尾节点（tail）
4.协作式删除机制：逻辑删除（标记item为null）和物理删除（解除链接）
5.一致性：弱一致性迭代器和视图
6.惰性更新策略：头尾指针不总是精确指向端点
7.最终一致性：通过后续操作逐步修正位置

已元素删除算法（以 pollFirst 为例）

public E pollFirst() {restartFromHead:for (;;) {// 步骤1：定位头节点Node<E> h = head, p = h;// 步骤2：查找首个有效节点while (p.item == null) {Node<E> next = p.next;if (next == null) return null;  // 队列为空p = next;}// 步骤3：逻辑删除 (标记item为null)if (!p.casItem(p.item, null)) continue;// 步骤4：物理解除链接Node<E> next = p.next;if (next != null && next.prev == p) {next.casPrev(p, p.prev);  // 更新后继的前驱}Node<E> prev = p.prev;if (prev != null && prev.next == p) {prev.casNext(p, p.next);  // 更新前驱的后继}// 步骤5：更新头指针if (p != h) {updateHead();  // 惰性更新head}return p.item;}
}

协作式删除节点
在步骤3：逻辑删除 (标记item为null)

// 在指针中嵌入状态信息（实际通过节点状态实现）
if (node.item == null) {// 节点已被删除，需要特殊处理helpUnlink(node);  // 协助解除链接continue;         // 重试操作
}

当线程A尝试删除节点X时：先将 X.item 置为 null（逻辑删除）
线程B若发现 X.item == null：主动调用 helpUnlink(x) 协助物理解除链接，更新相邻节点的指针
减少不必要的CAS操作

迭代器实现原理：弱一致性迭代器

public Iterator<E> iterator() {return new Itr();
}private class Itr implements Iterator<E> {private Node<E> nextNode;private E nextItem;Itr() {advance();  // 初始化时获取首个有效节点}void advance() {// 从当前节点开始查找下一个有效节点do {nextNode = (nextNode == null) ? first() : nextNode.next;} while (nextNode != null && nextNode.item == null);nextItem = (nextNode != null) ? nextNode.item : null;}
}

特点：
快照隔离：迭代开始时获取当前头指针
跳过已删除节点：自动过滤 item == null 的节点
弱一致性：可能反映迭代开始后的部分修改

惰性更新策略

//前向指针修正：
void fixPrev(Node<E> p) {for (;;) {Node<E> q = p.prev;Node<E> next = p.next;if (q != null && q.next != p) {q.casNext(q.next, p);  // 修复前驱的后继}if (next != null && next.prev != p) {next.casPrev(next.prev, p);  // 修复后继的前驱}// 检查是否修复完成if ((q == null || q.next == p) && (next == null || next.prev == p)) {break;}}
}

修复后，最终一致性

设计亮点
1.无锁并发：基于 Michael-Scott 算法的双端扩展，使用 CAS 实现线程安全
2.惰性更新策略：不立即更新反向指针（允许暂时不一致）， 后续操作会修复不一致状态
3.删除标记技术：协作删除：线程A的物理删除 和 后续线程B的物理删除
4.自我修复机制：线程遇到不一致状态时主动修复链表，保证最终一致性

ConcurrentLinkedDeque 总结

性能总结

操作	时间复杂度	并发性能
addFirst()	O(1)	极高
pollLast()	O(1)	高
size()	O(n)	低
contains()	O(n)	中

注意事项

1.弱一致性方法：

• size() 需要遍历整个链表，结果可能过时
• contains() 可能返回瞬时状态
• 迭代器是弱一致性的

2.内存消耗：

• 每个元素需要额外两个指针（prev/next）
• 比单向链表多 50% 内存开销

3.精确性要求：

   // 不要依赖size()进行关键决策if (deque.size() > threshold) {// 这个判断可能不可靠！}

适用场景

1.工作窃取算法：

   // 工作者线程从自己队列头部获取任务Runnable task = localDeque.pollFirst();// 当本地队列为空时，从其他队列尾部窃取if (task == null) {task = otherDeque.pollLast();}

2.多生产者-多消费者系统：

• 生产者可自由选择头部/尾部添加任务
• 消费者可选择从头部/尾部获取任务

3.实时事件处理系统：

• 新事件添加到头部（高优先级）
• 旧事件从尾部处理（低优先级）

4.并发缓存实现：

• 最近使用添加到头部
• 淘汰策略从尾部移除

最佳实践

1.首选特定端方法：

   // 明确意图deque.offerFirst(item); // 比 push() 更清晰

2.空队列处理：

   // 使用poll而不是remove避免异常E item = deque.pollFirst();if (item != null) {// 处理元素}

3.批量处理优化：

   // 批量提取多个元素List<E> batch = new ArrayList<>(BATCH_SIZE);while (batch.size() < BATCH_SIZE) {E item = deque.pollFirst();if (item == null) break;batch.add(item);}

和Deque其余子类 性能对比

操作	ConcurrentLinkedDeque	LinkedBlockingDeque	ArrayDeque (非线程安全)
头部插入 (100线程)	12 ms	45 ms	N/A
尾部插入 (100线程)	13 ms	48 ms	N/A
头部删除 (100线程)	11 ms	42 ms	N/A
内存开销 (100万元素)	~48 MB	~32 MB	~24 MB

ConcurrentLinkedDeque 是 Java 并发编程中的高级工具：

• ✅ 优势：高并发性能、双端操作、无界容量
• ⚠️ 局限：内存开销大、弱一致性方法
• 💡 适用：工作窃取、多端生产者-消费者系统、需要双端操作的并发场景

在需要高并发双端操作的场景下，ConcurrentLinkedDeque 提供了最优秀的并发性能，是构建高性能并发系统的理想选择

ConcurrentLinkedDeque 代码使用示例

1.作为并发栈（LIFO）

ConcurrentLinkedDeque<String> stack = new ConcurrentLinkedDeque<>();// 压栈
stack.push("Task1"); // addFirst
stack.push("Task2");// 弹栈
String task = stack.pop(); // removeFirst

2.作为双端队列

ConcurrentLinkedDeque<Integer> deque = new ConcurrentLinkedDeque<>();// 生产者A - 尾部添加
new Thread(() -> {for (int i = 0; i < 100; i++) {deque.addLast(i); // 尾部添加}
}).start();// 生产者B - 头部添加
new Thread(() -> {for (int i = -1; i > -100; i--) {deque.addFirst(i); // 头部添加}
}).start();// 消费者 - 头部处理
new Thread(() -> {while (true) {Integer num = deque.pollFirst(); // 头部取出if (num != null) {System.out.println("Processed: " + num);}}
}).start();

ArrayDeque 与 LinkedList 对比

特性	ArrayDeque	LinkedList
数据结构	动态循环数组	双向链表
内存占用	更紧凑（无节点开销）	每个元素额外24字节
随机访问	O(n)	O(n)（实际更慢）
迭代性能	更高（缓存友好）	较低
插入/删除（头尾）	O(1) 分摊时间	O(1)
插入/删除（中间）	O(n)	O(1)（已知位置）
null 支持	❌ 禁止	✅ 允许
多线程安全	❌ 需要外部同步	❌ 需要外部同步
扩容成本	较高（复制数组）	无

Deque总结

Deque 是一个功能强大且灵活的接口，统一了队列和栈的抽象。它提供了丰富的双端操作方法（包括异常抛出型和特殊值返回型）。ArrayDeque 通常是需要高效双端操作且不需要 List 功能或 null 元素时的最佳选择。LinkedList 在需要同时使用 Deque 和 List 功能或需要 null 元素时是唯一选择。理解不同方法的区别以及两种主要实现的特性，对于正确有效地使用 Deque 至关重要。