前言

本文基于课堂课件与个人学习体会，将全面(也许吧)讲解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)在连续内存访问方面有优势，但需要处理数组扩容和循环索引计算等问题。