一、核心概念與繼承體系

二、Queue 核心方法與實現(xiàn)

1. 核心操作：

2. 常用實現(xiàn)類：

• LinkedList：基于鏈表，支持null元素

• PriorityQueue：基于堆的優(yōu)先級隊列（自然序/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（混合操作結(jié)果）

6. 常用實現(xiàn)類：

• ArrayDeque：基于循環(huán)數(shù)組（默認容量16，性能最優(yōu)）

• LinkedList：基于雙向鏈表（支持索引訪問）

• LinkedBlockingDeque：線程安全阻塞雙端隊列

四、與其他集合類對比

五、使用場景與最佳實踐

1. 隊列場景：

• 任務(wù)調(diào)度：ThreadPoolExecutor 使用 BlockingQueue

• 消息傳遞：生產(chǎn)者-消費者模式

• 廣度優(yōu)先搜索（BFS）

2. 雙端隊列場景：

• 撤銷操作棧：ArrayDeque 替代 Stack

• 滑動窗口算法

• 工作竊取算法（Work Stealing）

3. 選擇指南：

六、常見問題

Q1：Queue和Deque的主要區(qū)別是什么？

A：

1. 功能定位：

   • Queue 是標準FIFO隊列（尾部添加，頭部移除）

   • Deque 是雙端隊列，擴展了Queue，支持兩端操作

2. 操作能力：

   • Queue 只有隊頭出隊(poll)、隊尾入隊(offer)

   • Deque 增加offerFirst/pollFirst等雙端操作方法

3. 棧功能：

   • Deque 可直接作為棧使用（push/pop方法）

   • Queue 沒有原生棧操作支持

Q2：ArrayDeque和LinkedList如何選擇？

A：

• ArrayDeque：

  • 基于循環(huán)數(shù)組，內(nèi)存連續(xù)

  • 兩端操作時間復(fù)雜度O(1)

  • 隨機訪問更快，CPU緩存友好

  • 推薦場景：大多數(shù)隊列/棧需求（默認選擇）

• LinkedList：

  • 基于雙向鏈表，內(nèi)存分散

  • 支持List接口的索引訪問

  • 插入刪除中間元素更高效

  • 推薦場景：

    • 需要同時使用隊列和列表功能

    • 需要頻繁在中間位置插入/刪除

Q3：阻塞隊列是什么？常用實現(xiàn)有哪些？

A：

• 阻塞隊列：當隊列滿時阻塞生產(chǎn)者，隊列空時阻塞消費者（BlockingQueue接口）

• 常用實現(xiàn)：

  • ArrayBlockingQueue：數(shù)組實現(xiàn)的有界隊列

  • LinkedBlockingQueue：鏈表實現(xiàn)的可選有界隊列

  • PriorityBlockingQueue：帶優(yōu)先級的無界阻塞隊列

  • SynchronousQueue：不存儲元素的直接傳遞隊列

Q4：Deque如何替代Stack？

A：

1. Java官方推薦用Deque替代Stack類

2. 轉(zhuǎn)換方式：

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

3. 優(yōu)勢：

   • 避免Stack的同步開銷（Vector實現(xiàn)）

   • 更統(tǒng)一的集合API

   • 更好的性能（特別是ArrayDeque）

Q5：PriorityQueue的排序原理？

A：

• 基于堆數(shù)據(jù)結(jié)構(gòu)（默認最小堆）

• 排序規(guī)則：

  • 自然排序：元素實現(xiàn)Comparable

  • 定制排序：構(gòu)造時傳入Comparator

• 特點：

  • 隊頭總是當前最值元素

  • 入隊/出隊時間復(fù)雜度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會導(dǎo)致數(shù)據(jù)順序混亂

// 錯誤示例（導(dǎo)致數(shù)據(jù)順序不可預(yù)測）
deque.push("A");  // 棧操作（頭部插入）
deque.offer("B"); // 隊列操作（尾部插入）
// 此時隊列：A<-B，但棧頂是A

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

A：
除了之前提到的性能優(yōu)勢，API設(shè)計也更合理：

1. Stack的缺陷API：

   // 老式Stack API（繼承自Vector）
   stack.addElement(e);  // 非標準方法名
   stack.insertElementAt(e, 0); // 危險的低效操作

2. Deque的標準棧API：

   deque.push(e);  // 標準棧操作
   deque.pop();    // 直觀的LIFO語義
   deque.peek();   // 查看棧頂

3. 額外優(yōu)勢：Deque的棧操作時間復(fù)雜度均為O(1)，而Stack的insertElementAt(0)是O(n)

七、高頻面試進階問題

1. poll()和remove()有什么區(qū)別？

   • 行為相同：移除并返回隊頭元素

   • 空隊列時：poll()返回null，remove()拋異常

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

   • 默認初始容量16

   • 擴容規(guī)則：加倍容量（16→32→64...）

   • 重要特性：容量總是2的冪（位運算優(yōu)化）

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

   // 阻塞方法（無限等待）
   void put(E e) throws InterruptedException;
   
   // 非阻塞方法
   boolean offer(E e, long timeout, TimeUnit unit); // 限時等待
   boolean offer(E e);                              // 立即返回

4. 為什么LinkedList實現(xiàn)了List和Deque？

   • 設(shè)計上支持多種訪問方式：

     • 列表功能：索引訪問/中間插入

     • 隊列功能：FIFO操作

     • 雙端功能：兩端高效操作

   • 體現(xiàn)了接口隔離原則

總結(jié) 

到此這篇關(guān)于Java中Queue以及Deque用法的文章就介紹到這了,更多相關(guān)Java中Queue以及Deque內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！