前言

本文基于課堂課件與個人學習體會，將全面(也許吧)講解Java中棧和隊列這兩種經典數據結構的原理、實現和應用。內容如有不足，歡迎指正與交流。

1. 棧(Stack)

1.1 什么是棧

棧是一種特殊的線性表，其特點是僅允許在一端（稱為棧頂）進行插入和刪除操作。不允許操作的另一端稱為棧底。棧遵循**后進先出LIFO（Last In First Out）**原則，就像一摞盤子，只能從頂部拿取或放置。

棧的基本操作包括：

• 壓棧（Push）：將新元素添加到棧頂
• 出棧（Pop）：移除棧頂元素并返回

1.2 棧的常用操作

方法	功能
Stack()	構造一個空的棧
E push (E e)	將e壓棧，并返回e
E pop()	將棧頂元素出棧并返回
E peek()	獲取棧頂元素(不出棧)
int size()	獲取棧中有效元素個數
boolean empty()	檢查棧是否為空

下面是一個使用Java標準庫中Stack類的簡單示例：

public static void main(String[] args) {// 創建整型棧Stack<Integer> s = new Stack<>();// 依次入棧1、2、3、4s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size());  // 輸出: 4System.out.println(s.peek());  // 輸出: 4s.pop();  // 4出棧，棧中剩余1、2、3System.out.println(s.pop());  // 輸出: 3，棧中剩余1、2// 判斷棧是否為空if(s.empty()) {System.out.println("棧空");} else {System.out.println(s.size());  // 輸出: 2}
}

1.3 棧的模擬實現

在Java中，Stack類繼承自Vector類。Vector和ArrayList類似，都是動態順序表，區別在于Vector是線程安全的。

我們自己實現一個棧類，加深對棧操作的理解：

package Stack;import java.util.Arrays;public class MyStack {// 存儲棧中元素的數組private int[] elem;// 當前棧中有效元素個數private int usedSize;// 構造一個默認容量為10的棧public MyStack() {this.elem = new int[10];}// 入棧操作public void push(int val) {// 棧滿則擴容if (isFull()) {this.elem = Arrays.copyOf(elem, 2 * elem.length);}elem[usedSize++] = val;}// 判斷棧是否已滿public boolean isFull() {return usedSize == elem.length;}// 出棧操作public int pop() {if (isEmpty()) {throw new EmptyStackException();}int val = elem[usedSize-1];usedSize--;return val;}// 獲取棧頂元素但不刪除public int peek() {if (isEmpty()) {throw new EmptyStackException();}return elem[usedSize-1];}// 判斷棧是否為空public boolean isEmpty() {return 0 == usedSize;}
}

為了處理空棧操作的異常情況，定義一個異常類：

package Stack;// 自定義空棧異常類
public class EmptyStackException extends RuntimeException {public EmptyStackException() {}public EmptyStackException(String message) {super(message);}
}

我們還可以編寫一個簡單的測試類來驗證我們的棧實現：

package Stack;public class Test {public static void main(String[] args) {// 創建自定義棧MyStack stack = new MyStack();// 測試入棧stack.push(10);stack.push(20);stack.push(30);stack.push(40);// 查看棧頂元素System.out.println("棧頂元素: " + stack.peek());  // 輸出: 40// 測試出棧System.out.println("出棧元素: " + stack.pop());  // 輸出: 40System.out.println("出棧元素: " + stack.pop());  // 輸出: 30// 檢查棧大小System.out.println("棧中元素個數: " + stack.usedSize);  // 輸出: 2// 測試棧是否為空System.out.println("棧是否為空: " + stack.isEmpty());  // 輸出: false// 清空棧stack.pop();  // 出棧20stack.pop();  // 出棧10// 驗證棧空System.out.println("棧是否為空: " + stack.isEmpty());  // 輸出: true// 測試空棧異常try {stack.pop();} catch (EmptyStackException e) {System.out.println("捕獲到空棧異常");}}
}

1.4 棧的應用場景

棧在編程中有很多實用場景，這些例子都能很好地展示棧"后進先出"的特性。下面我們看幾個經典應用，這些也是面試中的常客哦。

1.4.1 元素序列處理

棧的LIFO特性讓它非常適合處理需要"反向"或"回溯"的問題，比如：

1. 字符串反轉 - 正向讀取，反向輸出
2. 括號匹配檢查 - 左括號入棧，右括號檢查匹配
3. 表達式求值 - 處理中綴、后綴表達式
4. 棧序列驗證 - 檢查出棧序列是否有效
5. 最小棧設計 - 追蹤棧中的最小值

1.4.2 字符串反轉

字符串反轉是棧的入門應用，思路很直接：把字符依次壓入棧中，然后彈出來，就自然形成了反序。

public static String reverseString(String str) {Stack<Character> stack = new Stack<>();// 將字符逐個入棧for (int i = 0; i < str.length(); i++) {stack.push(str.charAt(i));}// 出棧組成新字符串StringBuilder result = new StringBuilder();while (!stack.empty()) {result.append(stack.pop());}return result.toString();
}

1.4.3 括號匹配

原題鏈接

題目：給定一個只包含括號的字符串，判斷括號是否有效匹配。

解題思路：

1. 遇到左括號就入棧（存起來等待匹配）

2. 遇到右括號就檢查棧頂的左括號是否匹配

   • 匹配就彈出棧頂元素，繼續處理下一個字符
   • 不匹配或棧為空，直接返回false

3. 最后檢查棧是否為空：

   • 空棧：所有左括號都找到了匹配，返回true
   • 非空：有左括號沒找到匹配，返回false

其實就像給括號"找對象"，每個左括號都要找到自己匹配的右括號才行。

算法流程：

實現代碼：

public boolean isValid(String s) {// 創建字符棧Stack<Character> stack = new Stack<>();for(int i = 0; i < s.length(); i++) {char ch = s.charAt(i);// 左括號入棧if(ch == '(' || ch == '[' || ch == '{') {stack.push(ch);} else {// 右括號但棧為空，無法匹配if (stack.isEmpty()) {return false;}char top = stack.peek();// 檢查匹配if ((ch == ')' && top == '(') || (ch == '}' && top == '{') || (ch == ']' && top == '[')) {stack.pop(); // 匹配成功，彈出左括號} else {return false; // 匹配失敗}}}// 棧空則所有括號都匹配完成return stack.isEmpty();
}

1.4.4 逆波蘭表達式求值

原題鏈接

題目：給定一個后綴表達式(逆波蘭表達式)，求其結果值。

解題思路：

1. 遇到數字？直接入棧保存起來

2. 遇到運算符？從棧中彈出兩個數字進行計算：

   • 先彈出的是第二個操作數
   • 后彈出的是第一個操作數
   • 計算結果再壓回棧中

3. 表達式處理完后，棧中就只剩下最終結果了

比如 ["2","1","+","3","*"] 的計算過程：

• 讀到 2 和 1，分別入棧，棧內：[2,1]
• 讀到 +，彈出 1 和 2，計算 2+1=3，結果入棧，棧內：[3]
• 讀到 3，入棧，棧內：[3,3]
• 讀到 ，彈出 3 和 3，計算 33=9，結果入棧，棧內：[9]
• 結束，最終結果為 9

就像是依次處理計算任務，用棧暫存中間結果。

算法流程：

實現代碼：

public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(String token : tokens) {if(isOperator(token)) {// 是運算符，彈出兩個操作數計算int b = stack.pop();int a = stack.pop();switch(token) {case "+": stack.push(a + b); break;case "-": stack.push(a - b); break;case "*": stack.push(a * b); break;case "/": stack.push(a / b); break;}} else {// 是操作數，轉換為整數并入棧stack.push(Integer.parseInt(token));}}// 最終棧中只有一個元素，即為計算結果return stack.pop();
}private boolean isOperator(String token) {return "+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token);
}

1.4.5 棧的壓入、彈出序列

原題鏈接

題目：給定兩個整數序列，第一個為入棧順序，判斷第二個是否是可能的出棧順序。

解題思路：

1. 準備一個輔助棧，按照給定順序依次"入棧"
2. 每次入棧后，都嘗試"出棧"操作：
   • 如果棧頂元素等于當前期望的出棧元素，就執行出棧
   • 一直出棧，直到棧頂元素不等于期望出棧元素或棧空
3. 繼續入棧下一個元素，重復上述過程
4. 最后檢查棧是否為空：
   • 空棧：說明所有元素都按照期望序列出棧了，返回true
   • 非空：出棧序列不匹配，返回false

打個比方，就像排隊進場又出場，我們看看是否能按照給定的出場順序安排人員進出。

實現代碼：

public boolean validateStackSequences(int[] pushed, int[] popped) {// 參數校驗if (pushed == null || popped == null || pushed.length != popped.length) {return false;}Stack<Integer> stack = new Stack<>();int popIdx = 0;for (int val : pushed) {// 將當前元素壓入棧stack.push(val);// 嘗試出棧操作while (!stack.isEmpty() && stack.peek() == popped[popIdx]) {stack.pop();popIdx++;}}// 如果輔助棧為空，說明所有元素都正確匹配了return stack.isEmpty();
}

1.4.6 最小棧

原題鏈接

題目：設計一個棧，支持常規操作的同時能夠在O(1)時間內獲取棧中的最小值。

解題思路：

這個問題的難點在于：每次出棧后，如何快速知道剩下元素中的最小值？

最直接的思路是用一個輔助棧，專門用來記錄當前棧中的最小值：

1. 主棧：正常保存所有入棧的元素
2. 輔助棧(最小棧)：同步記錄每個狀態下的最小值
   • 當新元素小于或等于當前最小值時，將新元素也壓入輔助棧
   • 當出棧元素等于當前最小值時，輔助棧也要出棧

這樣，輔助棧的棧頂始終是當前主棧中的最小值。

舉個例子：

• 依次入棧：5, 2, 6, 1
• 主棧變化：[5] -> [5,2] -> [5,2,6] -> [5,2,6,1]
• 輔助棧變化：[5] -> [5,2] -> [5,2] -> [5,2,1]
• 每一步，輔助棧的棧頂都是當前所有元素中的最小值

實現代碼：

class MinStack {// 主棧：存儲所有元素private Stack<Integer> stack;// 輔助棧：存儲最小值private Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);// 如果最小棧為空或新元素不大于最小棧棧頂，則將新元素也壓入最小棧if (minStack.empty() || val <= minStack.peek()) {minStack.push(val);}}public void pop() {if(!stack.empty()) {// 如果出棧元素是當前最小值，最小棧也要出棧if(stack.peek().equals(minStack.peek())) {minStack.pop();}stack.pop();}}public int top() {if(stack.empty()) {throw new EmptyStackException();}return stack.peek();}public int getMin() {if(minStack.empty()) {throw new EmptyStackException();}return minStack.peek();}
}

1.4.7 遞歸轉循環

棧的另一個重要應用是將遞歸算法轉為迭代形式。遞歸本質上是利用系統棧來管理函數調用，我們可以用顯式的棧來模擬這個過程，從而避免遞歸可能導致的棧溢出問題。

以逆序打印鏈表為例：

// 遞歸方法 - 簡潔但有棧溢出風險
void printListReversely(Node head) {if(head != null) {printListReversely(head.next);  // 先遞歸處理后續節點System.out.print(head.val + " "); // 再處理當前節點}
}// 用棧模擬的迭代方法 - 更安全
void printListReverselyWithStack(Node head) {Stack<Node> stack = new Stack<>();// 將所有節點入棧Node curr = head;while(curr != null) {stack.push(curr);curr = curr.next;}// 出棧并打印while(!stack.isEmpty()) {System.out.print(stack.pop().val + " ");}
}

這兩種方法的核心思想相同，但迭代版本使用顯式棧管理，可以更好地控制內存使用，避免大數據時可能的棧溢出問題。

1.5 概念區分

在討論棧時，我們經常會遇到幾個相關但不同的概念：數據結構中的棧、JVM中的虛擬機棧以及棧幀。讓我們來理清它們之間的關系。

1.5.1 數據結構中的棧

我們前面討論的棧是一種抽象數據類型，具有后進先出的特性。它的基本操作包括：

• push：將元素添加到棧頂
• pop：從棧頂移除元素
• peek：查看棧頂元素但不移除
• isEmpty：檢查棧是否為空

Java中通過java.util.Stack類提供了這種數據結構的實現。

1.5.2 JVM中的虛擬機棧

Java虛擬機棧(JVM Stack)是Java虛擬機內存模型的一部分，為Java程序的運行提供服務。它具有以下特點：

• 線程私有：每個線程在創建時都會創建一個虛擬機棧
• 生命周期：與線程的生命周期相同
• 作用：存儲方法執行過程的各種數據

JVM棧可能出現的異常：

• StackOverflowError：當請求的棧深度超過虛擬機允許的最大深度時
• OutOfMemoryError：當棧動態擴展時無法申請到足夠的內存時

1.5.3 棧幀

棧幀(Stack Frame)是虛擬機棧中的基本單位，對應一次方法調用所需的內存空間。當方法被調用時，一個新的棧幀被創建并壓入當前線程的虛擬機棧；當方法執行完成后，棧幀被彈出。

棧幀的主要組成部分：

1. 局部變量表：存儲方法參數和局部變量
2. 操作數棧：存儲操作的中間結果
3. 動態鏈接：指向運行時常量池的方法引用
4. 方法返回地址：記錄方法執行完后的返回位置
5. 附加信息：如調試信息

舉個例子：

public static int add(int a, int b) {int result = a + b;return result;
}public static void main(String[] args) {int x = 5;int y = 10;int sum = add(x, y);System.out.println(sum);
}

當執行到add(x, y)時，會創建一個新的棧幀，包含參數a和b以及局部變量result。當add方法返回后，這個棧幀被銷毀，控制權回到main方法的棧幀。

1.5.4 三者關系

1. 數據結構棧與JVM棧：

   • 數據結構棧是一種抽象概念
   • JVM棧是具體的內存區域實現

2. JVM棧與棧幀：

   • JVM棧是容器，包含多個棧幀
   • 棧幀是元素，每個方法調用對應一個棧幀

3. 它們的共同點：

   • 都遵循后進先出(LIFO)原則
   • 都用于管理程序執行的狀態和數據

2. 隊列(Queue)

2.1 隊列簡介

隊列是一種特殊的線性表，它只允許在一端（隊尾）進行插入操作，在另一端（隊頭）進行刪除操作。隊列遵循**先進先出FIFO(First In First Out)**原則，就像排隊買票一樣，先到的人先服務。

隊列的基本操作包括：

• 入隊（Enqueue）：在隊尾添加元素
• 出隊（Dequeue）：從隊頭移除元素

2.2 隊列的使用

在Java中，Queue是一個接口，定義了隊列數據結構的標準操作。LinkedList是實現Queue接口的常用類，它通過鏈表實現了隊列功能。

Queue接口定義的主要方法：

方法	功能
boolean offer(E e)	將元素添加到隊尾
E poll()	移除并返回隊頭元素
E peek()	獲取隊頭元素但不移除
int size()	獲取隊列中元素個數
boolean isEmpty()	檢查隊列是否為空

下面是一個使用Java隊列的示例：

public static void main(String[] args) {// 創建隊列Queue<Integer> queue = new LinkedList<>();// 添加元素到隊列queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);// 查看隊列信息System.out.println("隊列大小: " + queue.size());     // 輸出：5System.out.println("隊頭元素: " + queue.peek());     // 輸出：1// 移除隊頭元素queue.poll();  // 移除元素1System.out.println("出隊后隊頭: " + queue.poll());   // 輸出：2// 檢查隊列狀態if(queue.isEmpty()) {System.out.println("隊列為空");} else {System.out.println("隊列剩余元素: " + queue.size());  // 輸出：3}
}

2.3 自定義隊列實現

隊列可以通過數組或鏈表實現。鏈表實現更為靈活，特別是在需要頻繁調整隊列大小的場景下。下面我們使用雙向鏈表實現一個簡單的隊列：

/*** 基于雙向鏈表的隊列實現*/
public class MyQueue {// 鏈表節點類static class ListNode {int val;           // 節點值ListNode prev;     // 前驅節點ListNode next;     // 后繼節點ListNode(int val) {this.val = val;}}private ListNode first;    // 隊頭指針private ListNode last;     // 隊尾指針private int size;          // 隊列大小// 入隊操作public void offer(int val) {ListNode newNode = new ListNode(val);if (isEmpty()) {// 空隊列，新節點同時是隊頭和隊尾first = last = newNode;} else {// 非空隊列，在尾部添加節點last.next = newNode;newNode.prev = last;last = newNode;}size++;}// 出隊操作public int poll() {if (isEmpty()) {throw new IllegalStateException("隊列為空");}int value = first.val;if (first == last) {// 隊列只有一個元素first = last = null;} else {// 移除隊頭first = first.next;first.prev = null;}size--;return value;}// 查看隊頭元素public int peek() {if (isEmpty()) {throw new IllegalStateException("隊列為空");}return first.val;}// 判斷隊列是否為空public boolean isEmpty() {return first == null;}// 獲取隊列大小public int size() {return size;}
}

2.4 循環隊列

循環隊列是首尾相連的隊列，通常使用數組實現。它能有效解決普通隊列在使用數組實現時可能面臨的"假溢出"問題（數組空間未滿但無法添加新元素）。

2.4.1 循環隊列原理

循環隊列使用兩個指針：front（指向隊頭元素）和rear（指向隊尾元素的下一個位置）。當指針到達數組末尾時，它會"繞回"到數組開頭，形成一個邏輯上的環形結構。

在循環隊列中，下標計算采用取模運算：

• 向后移動：newIndex = (oldIndex + 1) % array.length
• 向前移動：newIndex = (oldIndex + array.length - 1) % array.length

2.4.2 區分隊空與隊滿

在循環隊列實現中，一個核心問題是如何區分隊列空和隊列滿，因為在這兩種情況下front和rear可能指向相同位置。常用的解決方案有：

1. 犧牲一個存儲單元：保留一個空位置作為隊滿標志

   • 隊空條件：front == rear
   • 隊滿條件：(rear + 1) % capacity == front

2. 使用計數器：維護一個size變量記錄元素個數

   • 隊空條件：size == 0
   • 隊滿條件：size == capacity

3. 使用狀態標志：額外使用一個布爾變量標記隊列狀態

2.4.3 循環隊列實現

下面是一個基于數組實現的循環隊列：

/*** 數組實現的循環隊列*/
class MyCircularQueue {private int front;    // 隊頭指針private int rear;     // 隊尾指針private int[] elem;   // 存儲隊列元素的數組public MyCircularQueue(int k) {// 多分配一個空間用于區分隊空和隊滿elem = new int[k + 1];front = rear = 0;}// 入隊操作public boolean enQueue(int value) {if (isFull()) {return false;}elem[rear] = value;rear = (rear + 1) % elem.length;return true;}// 出隊操作public boolean deQueue() {if (isEmpty()) {return false;}front = (front + 1) % elem.length;return true;}// 獲取隊頭元素public int Front() {if (isEmpty()) {return -1;}return elem[front];}// 獲取隊尾元素public int Rear() {if (isEmpty()) {return -1;}// 隊尾元素位于rear-1位置int index = (rear - 1 + elem.length) % elem.length;return elem[index];}// 檢查隊列是否為空public boolean isEmpty() {return front == rear;}// 檢查隊列是否已滿public boolean isFull() {return (rear + 1) % elem.length == front;}
}

循環隊列實現中的關鍵點：

• 實際可用空間為k，而數組長度為k+1（犧牲一個位置區分隊空隊滿）
• 入隊時，先存值再移動rear指針
• 出隊時，只需移動front指針
• 隊滿條件是rear的下一個位置等于front
• 計算隊尾元素位置需要考慮rear為0的情況

3. 雙端隊列(Deque)

3.1 雙端隊列概述

雙端隊列（Deque）是一種允許在兩端進行插入和刪除操作的隊列。名稱"Deque"是"Double-Ended Queue"的縮寫。它結合了棧和隊列的特點，使得數據操作更加靈活。

在Java中，Deque是一個接口，擴展了Queue接口。常用的實現類包括：

• LinkedList：基于鏈表實現
• ArrayDeque：基于數組實現（通常比LinkedList更高效）

3.2 雙端隊列操作

3.2.1 創建雙端隊列

Java提供了兩種常見的雙端隊列實現：

// 基于數組的實現，適用于大多數場景
Deque<Integer> arrayDeque = new ArrayDeque<>();// 基于鏈表的實現，適用于頻繁的插入刪除操作
Deque<Integer> linkedDeque = new LinkedList<>();

3.2.2 常用方法

雙端隊列支持在兩端進行元素操作，下面是主要方法分類：

插入操作

方法	描述	隊列滿時行為
addFirst(E e)	在隊頭添加元素	拋出異常
addLast(E e)	在隊尾添加元素	拋出異常
offerFirst(E e)	在隊頭添加元素	返回false
offerLast(E e)	在隊尾添加元素	返回false
push(E e)	在隊頭添加元素(同addFirst)	拋出異常
add(E e)	在隊尾添加元素(同addLast)	拋出異常

刪除操作

方法	描述	隊列空時行為
removeFirst()	移除并返回隊頭元素	拋出異常
removeLast()	移除并返回隊尾元素	拋出異常
pollFirst()	移除并返回隊頭元素	返回null
pollLast()	移除并返回隊尾元素	返回null
pop()	移除并返回隊頭元素(同removeFirst)	拋出異常
poll()	移除并返回隊頭元素(同pollFirst)	返回null

查看操作

方法	描述	隊列空時行為
getFirst()	獲取隊頭元素但不移除	拋出異常
getLast()	獲取隊尾元素但不移除	拋出異常
peekFirst()	獲取隊頭元素但不移除	返回null
peekLast()	獲取隊尾元素但不移除	返回null
peek()	獲取隊頭元素但不移除(同peekFirst)	返回null

3.2.3 雙端隊列的使用示例

public static void main(String[] args) {// 創建雙端隊列Deque<String> deque = new LinkedList<>();// 從兩端添加元素deque.addFirst("開頭");deque.offerFirst("最前面");deque.addLast("結尾");deque.offerLast("最后面");// 查看隊列內容System.out.println(deque);  // 輸出: [最前面, 開頭, 結尾, 最后面]// 不刪除元素查看兩端System.out.println("隊頭: " + deque.peekFirst());  // 輸出: 最前面System.out.println("隊尾: " + deque.peekLast());   // 輸出: 最后面// 刪除并返回元素System.out.println("刪除隊頭: " + deque.pollFirst());  // 輸出: 最前面System.out.println("刪除隊尾: " + deque.pollLast());   // 輸出: 最后面// 刪除后的隊列System.out.println(deque);  // 輸出: [開頭, 結尾]// 使用棧方法(LIFO)deque.push("新頭部");            // 在隊頭添加System.out.println(deque);       // 輸出: [新頭部, 開頭, 結尾]System.out.println(deque.pop()); // 輸出: 新頭部// 使用隊列方法(FIFO)deque.offer("新結尾");           // 在隊尾添加System.out.println(deque);       // 輸出: [開頭, 結尾, 新結尾]System.out.println(deque.poll()); // 輸出: 開頭
}

3.3 雙端隊列的實現

雙端隊列可以通過鏈表或數組來實現，Java中的LinkedList和ArrayDeque分別代表這兩種實現方式。下面我們來看一個基于雙向鏈表的簡單實現：

/*** 雙向鏈表實現的雙端隊列*/
public class MyLinkedDeque<E> {// 節點類，包含元素值和前后引用private static class Node<E> {E item;Node<E> prev;Node<E> next;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.prev = prev;this.next = next;}}private Node<E> first;    // 隊列頭節點private Node<E> last;     // 隊列尾節點private int size;         // 元素個數// 從隊頭添加元素public void addFirst(E e) {Node<E> f = first;Node<E> newNode = new Node<>(null, e, f);first = newNode;if (f == null) {// 如果隊列為空，新節點同時是尾節點last = newNode;} else {// 更新原頭節點的前驅f.prev = newNode;}size++;}// 從隊尾添加元素public void addLast(E e) {Node<E> l = last;Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null) {// 如果隊列為空，新節點同時是頭節點first = newNode;} else {// 更新原尾節點的后繼l.next = newNode;}size++;}// 移除并返回隊頭元素public E removeFirst() {if (isEmpty()) {throw new NoSuchElementException("隊列為空");}E element = first.item;Node<E> next = first.next;// 釋放資源，幫助垃圾回收first.item = null;first.next = null;first = next;if (next == null) {// 隊列變空last = null;} else {next.prev = null;}size--;return element;}// 移除并返回隊尾元素public E removeLast() {if (isEmpty()) {throw new NoSuchElementException("隊列為空");}E element = last.item;Node<E> prev = last.prev;// 釋放資源last.item = null;last.prev = null;last = prev;if (prev == null) {// 隊列變空first = null;} else {prev.next = null;}size--;return element;}// 獲取隊頭元素但不移除public E peekFirst() {if (isEmpty()) {return null;}return first.item;}// 獲取隊尾元素但不移除public E peekLast() {if (isEmpty()) {return null;}return last.item;}// 檢查隊列是否為空public boolean isEmpty() {return size == 0;}// 返回隊列大小public int size() {return size;}// 清空隊列public void clear() {// 清理所有節點，幫助垃圾回收for (Node<E> x = first; x != null; ) {Node<E> next = x.next;x.item = null;x.next = null;x.prev = null;x = next;}first = last = null;size = 0;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder("[");Node<E> x = first;if (x != null) {sb.append(x.item);x = x.next;while (x != null) {sb.append(", ").append(x.item);x = x.next;}}return sb.append("]").toString();}
}

雙向鏈表實現的雙端隊列有以下優點：

• 兩端操作均為O(1)時間復雜度
• 無需預先指定容量，可動態擴展
• 實現直觀，易于理解

主要缺點：

• 每個元素需要額外空間存儲前后節點引用
• 內存分配不連續，可能影響緩存效率

相比之下，數組實現的雙端隊列(如ArrayDeque)在連續內存訪問方面有優勢，但需要處理數組擴容和循環索引計算等問題。