一、核心概念與繼承體系

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

1. 核心操作：

2. 常用實(shí)現(xiàn)類(lèi)：

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

• PriorityQueue：基于堆的優(yōu)先級(jí)隊(duì)列（自然序/Comparator）

• ArrayBlockingQueue：固定大小的阻塞隊(duì)列（線(xiàn)程安全）

• LinkedBlockingQueue：可選有界阻塞隊(duì)列（線(xiàn)程安全）

三、Deque 雙端隊(duì)列擴(kuò)展

1. 核心操作增強(qiáng)：

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

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

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

2. 作為隊(duì)列使用（FIFO）的API：

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

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

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

4. API使用對(duì)照表：

5. 代碼示例：

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

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

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

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

6. 常用實(shí)現(xiàn)類(lèi)：

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

• LinkedList：基于雙向鏈表（支持索引訪(fǎng)問(wèn)）

• LinkedBlockingDeque：線(xiàn)程安全阻塞雙端隊(duì)列

四、與其他集合類(lèi)對(duì)比

五、使用場(chǎng)景與最佳實(shí)踐

1. 隊(duì)列場(chǎng)景：

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

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

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

2. 雙端隊(duì)列場(chǎng)景：

• 撤銷(xiāo)操作棧：ArrayDeque 替代 Stack

• 滑動(dòng)窗口算法

• 工作竊取算法（Work Stealing）

3. 選擇指南：

六、常見(jiàn)問(wèn)題

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

A：

1. 功能定位：

   • Queue 是標(biāo)準(zhǔn)FIFO隊(duì)列（尾部添加，頭部移除）

   • Deque 是雙端隊(duì)列，擴(kuò)展了Queue，支持兩端操作

2. 操作能力：

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

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

3. 棧功能：

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

   • Queue 沒(méi)有原生棧操作支持

Q2：ArrayDeque和LinkedList如何選擇？

A：

• ArrayDeque：

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

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

  • 隨機(jī)訪(fǎng)問(wèn)更快，CPU緩存友好

  • 推薦場(chǎng)景：大多數(shù)隊(duì)列/棧需求（默認(rèn)選擇）

• LinkedList：

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

  • 支持List接口的索引訪(fǎng)問(wèn)

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

  • 推薦場(chǎng)景：

    • 需要同時(shí)使用隊(duì)列和列表功能

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

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

A：

• 阻塞隊(duì)列：當(dāng)隊(duì)列滿(mǎn)時(shí)阻塞生產(chǎn)者，隊(duì)列空時(shí)阻塞消費(fèi)者（BlockingQueue接口）

• 常用實(shí)現(xiàn)：

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

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

  • PriorityBlockingQueue：帶優(yōu)先級(jí)的無(wú)界阻塞隊(duì)列

  • SynchronousQueue：不存儲(chǔ)元素的直接傳遞隊(duì)列

Q4：Deque如何替代Stack？

A：

1. Java官方推薦用Deque替代Stack類(lèi)

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)勢(shì)：

   • 避免Stack的同步開(kāi)銷(xiāo)（Vector實(shí)現(xiàn)）

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

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

Q5：PriorityQueue的排序原理？

A：

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

• 排序規(guī)則：

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

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

• 特點(diǎn)：

  • 隊(duì)頭總是當(dāng)前最值元素

  • 入隊(duì)/出隊(duì)時(shí)間復(fù)雜度O(log n)

  • 不支持null元素

Q6：如何使用Deque同時(shí)作為隊(duì)列和棧？

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

1. 隊(duì)列模式（FIFO）：固定使用尾部添加+頭部移除組合

// 推薦API組合
deque.offer(e);      // 入隊(duì)（尾部）
String item = deque.poll(); // 出隊(duì)（頭部）

1. 棧模式（LIFO）：固定使用頭部添加+頭部移除組合

// 推薦API組合
deque.push(e);       // 入棧（頭部）
String top = deque.pop();  // 出棧（頭部）

1. 危險(xiǎn)操作：混用API會(huì)導(dǎo)致數(shù)據(jù)順序混亂

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

Q7：為什么Java推薦用Deque代替Stack類(lèi)？

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

1. Stack的缺陷API：

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

2. Deque的標(biāo)準(zhǔn)棧API：

   deque.push(e);  // 標(biāo)準(zhǔn)棧操作
   deque.pop();    // 直觀的LIFO語(yǔ)義
   deque.peek();   // 查看棧頂

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

七、高頻面試進(jìn)階問(wèn)題

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

   • 行為相同：移除并返回隊(duì)頭元素

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

2. ArrayDeque初始容量是多少？如何擴(kuò)容？

   • 默認(rèn)初始容量16

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

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

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

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

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

   • 設(shè)計(jì)上支持多種訪(fǎng)問(wèn)方式：

     • 列表功能：索引訪(fǎng)問(wèn)/中間插入

     • 隊(duì)列功能：FIFO操作

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

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

總結(jié) 

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

最新評(píng)論