一、核心概念與繼承體系

二、Queue 核心方法與實現

1. 核心操作：

2. 常用實現類：

• LinkedList：基於鏈表，支持null元素
• PriorityQueue：基於堆的優先級隊列（自然序/Comparator）
• ArrayBlockingQueue：固定大小的阻塞隊列（線程安全）
• LinkedBlockingQueue：可選有界阻塞隊列（線程安全）

三、Deque 雙端隊列擴展

1. 核心操作增強：

// 頭部操作
offerFirst(e)  // 頭部插入
pollFirst()    // 頭部移除
peekFirst()    // 查看頭部

// 尾部操作
offerLast(e)   // 尾部插入（等價於offer）
pollLast()     // 尾部移除
peekLast()     // 查看尾部

// 棧操作
push(e)        // = offerFirst(e)
pop()          // = removeFirst()

2. 作為隊列使用（FIFO）的API：

// 隊列操作（FIFO：先進先出）
offerLast(e) 或 offer(e)  // 入隊（尾部添加）
pollFirst() 或 poll()     // 出隊（頭部移除）
peekFirst() 或 peek()     // 查看隊頭

3. 作為棧使用（LIFO）的API：

// 棧操作（LIFO：後進先出）
push(e)         // 入棧 = addFirst(e)
pop()           // 出棧 = removeFirst()
peekFirst()     // 查看棧頂

4. API使用對照表：

5. 代碼示例：

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

// 作為隊列使用（FIFO）
deque.offerLast("A"); // 隊尾添加
deque.offerLast("B");
System.out.println(deque.pollFirst()); // A（隊頭移除）

// 作為棧使用（LIFO）
deque.push("C");      // 入棧
deque.push("D");
System.out.println(deque.pop());      // D（出棧）

// 混合操作（不推薦但可能）
deque.offerLast("E"); // 隊尾添加（隊列操作）
deque.push("F");      // 棧頂添加（棧操作）
System.out.println(deque.pollFirst()); // F（混合操作結果）

6. 常用實現類：

• ArrayDeque：基於循環數組（默認容量16，性能最優）
• LinkedList：基於雙向鏈表（支持索引訪問）
• LinkedBlockingDeque：線程安全阻塞雙端隊列

四、與其他集合類對比

五、使用場景與最佳實踐

1. 隊列場景：

• 任務調度：ThreadPoolExecutor 使用 BlockingQueue
• 消息傳遞：生產者-消費者模式
• 廣度優先搜索（BFS）

2. 雙端隊列場景：

• 撤銷操作棧：ArrayDeque 替代 Stack
• 滑動窗口算法
• 工作竊取算法（Work Stealing）

3. 選擇指南：

六、常見問題

Q1：Queue和Deque的主要區別是什麼？

A：

1. 功能定位：

• Queue 是標準FIFO隊列（尾部添加，頭部移除）
• Deque 是雙端隊列，擴展了Queue，支持兩端操作

2. 操作能力：

• Queue 只有隊頭出隊(poll)、隊尾入隊(offer)
• Deque 增加offerFirst/pollFirst等雙端操作方法

3. 棧功能：

• Deque 可直接作為棧使用（push/pop方法）
• Queue 沒有原生棧操作支持

Q2：ArrayDeque和LinkedList如何選擇？

A：

• ArrayDeque：

• 基於循環數組，內存連續
• 兩端操作時間複雜度O(1)
• 隨機訪問更快，CPU緩存友好
• 推薦場景：大多數隊列/棧需求（默認選擇）

• LinkedList：

• 基於雙向鏈表，內存分散
• 支持List接口的索引訪問
• 插入刪除中間元素更高效
• 推薦場景：

• 需要同時使用隊列和列表功能
• 需要頻繁在中間位置插入/刪除

Q3：阻塞隊列是什麼？常用實現有哪些？

A：

• 阻塞隊列：當隊列滿時阻塞生產者，隊列空時阻塞消費者（BlockingQueue接口）
• 常用實現：

• ArrayBlockingQueue：數組實現的有界隊列
• LinkedBlockingQueue：鏈表實現的可選有界隊列
• PriorityBlockingQueue：帶優先級的無界阻塞隊列
• SynchronousQueue：不存儲元素的直接傳遞隊列

Q4：Deque如何替代Stack？

A：

1. Java官方推薦用Deque替代Stack類
2. 轉換方式：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);          // 入棧 = addFirst()
int top = stack.peek(); // 查看棧頂 = peekFirst()
int pop = stack.pop();  // 出棧 = removeFirst()

1. 優勢：

• 避免Stack的同步開銷（Vector實現）
• 更統一的集合API
• 更好的性能（特別是ArrayDeque）

Q5：PriorityQueue的排序原理？

A：

• 基於堆數據結構（默認最小堆）
• 排序規則：

• 自然排序：元素實現Comparable
• 定製排序：構造時傳入Comparator

• 特點：

• 隊頭總是當前最值元素
• 入隊/出隊時間複雜度O(log n)
• 不支持null元素

Q6：如何使用Deque同時作為隊列和棧？

A：
Deque可以同時支持隊列和棧操作，但必須避免混用API：

1. 隊列模式（FIFO）：固定使用尾部添加+頭部移除組合
// 推薦API組合
deque.offer(e);      // 入隊（尾部）
String item = deque.poll(); // 出隊（頭部）
1. 棧模式（LIFO）：固定使用頭部添加+頭部移除組合
// 推薦API組合
deque.push(e);       // 入棧（頭部）
String top = deque.pop();  // 出棧（頭部）
1. 危險操作：混用API會導致數據順序混亂
// 錯誤示例（導致數據順序不可預測）
deque.push("A");  // 棧操作（頭部插入）
deque.offer("B"); // 隊列操作（尾部插入）
// 此時隊列：A<-B，但棧頂是A

Q7：為什麼Java推薦用Deque代替Stack類？

A：
除了之前提到的性能優勢，API設計也更合理：

1. Stack的缺陷API：

// 老式Stack API（繼承自Vector）
stack.addElement(e);  // 非標準方法名
stack.insertElementAt(e, 0); // 危險的低效操作
1. Deque的標準棧API：
deque.push(e);  // 標準棧操作
deque.pop();    // 直觀的LIFO語義
deque.peek();   // 查看棧頂
1. 額外優勢：Deque的棧操作時間複雜度均為O(1)，而Stack的insertElementAt(0)是O(n)

七、高頻面試進階問題

1. poll()和remove()有什麼區別？

• 行為相同：移除並返回隊頭元素
• 空隊列時：poll()返回null，remove()拋異常

2. ArrayDeque初始容量是多少？如何擴容？

• 默認初始容量16
• 擴容規則：加倍容量（16→32→64...）
• 重要特性：容量總是2的冪（位運算優化）

3. 阻塞隊列的put()和offer()區別？

// 阻塞方法（無限等待）
void put(E e) throws InterruptedException;

// 非阻塞方法
boolean offer(E e, long timeout, TimeUnit unit); // 限時等待
boolean offer(E e);                              // 立即返回

1. 為什麼LinkedList實現了List和Deque？

• 設計上支持多種訪問方式：

• 列表功能：索引訪問/中間插入
• 隊列功能：FIFO操作
• 雙端功能：兩端高效操作

• 體現了接口隔離原則