雙端隊列的核心特點在于 在隊列的兩端進行插入和刪除操作，在隊列的 前端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 至關重要。