如何在Java中使用Stack和Queue
Stack遵循LIFO，Queue遵循FIFO；Java中推荐用ArrayDeque实现Stack，Queue常用LinkedList、ArrayDeque、PriorityQueue等，适用于表达式求值、BFS、任务调度等场景。
在Java中，
Stack和
Queue是两种核心的数据结构，它们提供了一种管理数据序列的特定方式。简单来说，
Stack遵循“后进先出”（LIFO）原则，就像一摞盘子，最后放上去的盘子最先被拿走；而
Queue则遵循“先进先出”（FIFO）原则，就像排队买票，最先排队的人最先买到票。理解并恰当使用它们，能显著优化我们处理数据流和特定算法的效率。
解决方案
要在Java中使用
Stack和
Queue，我们需要了解它们的接口和常用实现。
使用Stack
java.util.Stack是Java集合框架中一个历史悠久的类，它继承自
Vector，因此是同步的（线程安全），这在单线程环境中反而会带来不必要的性能开销。它的核心操作包括：
push(E item)
: 将元素压入栈顶。pop()
: 移除并返回栈顶元素。如果栈为空，会抛出EmptyStackException
。peek()
: 返回栈顶元素，但不移除。如果栈为空，会抛出EmptyStackException
。empty()
: 检查栈是否为空。search(Object o)
: 返回元素在栈中的1-based位置，如果不存在则返回-1。
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack browserHistory = new Stack<>();
// 访问页面
browserHistory.push("google.com");
browserHistory.push("baidu.com");
browserHistory.push("github.com");
System.out.println("当前页面: " + browserHistory.peek()); // github.com
// 后退
String lastVisited = browserHistory.pop();
System.out.println("后退到: " + browserHistory.peek()); // baidu.com
// 再次访问新页面
browserHistory.push("stackoverflow.com");
System.out.println("当前页面: " + browserHistory.peek()); // stackoverflow.com
System.out.println("栈是否为空: " + browserHistory.empty()); // false
}
} 使用Queue
java.util.Queue是一个接口，它定义了队列的基本行为。由于它是一个接口，我们需要选择一个具体的实现类。常用的实现包括
LinkedList和
ArrayDeque。
Queue的核心操作有两套，一套在操作失败时抛出异常，另一套返回特殊值（
null或
false），通常建议使用返回特殊值的方法：
-
抛出异常的方法:
add(E e)
: 将元素插入队列尾部。remove()
: 移除并返回队列头部元素。element()
: 返回队列头部元素，但不移除。
-
返回特殊值的方法 (推荐):
offer(E e)
: 将元素插入队列尾部，成功返回true
，失败返回false
。poll()
: 移除并返回队列头部元素。如果队列为空，返回null
。peek()
: 返回队列头部元素，但不移除。如果队列为空，返回null
。
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue taskQueue = new LinkedList<>(); // LinkedList是Queue的一个常用实现
// 添加任务
taskQueue.offer("任务A");
taskQueue.offer("任务B");
taskQueue.offer("任务C");
System.out.println("队列头部任务: " + taskQueue.peek()); // 任务A
// 处理任务
String currentTask = taskQueue.poll();
System.out.println("正在处理: " + currentTask); // 任务A
System.out.println("下一个任务: " + taskQueue.peek()); // 任务B
// 继续处理
taskQueue.poll();
taskQueue.poll();
System.out.println("队列是否为空: " + taskQueue.isEmpty()); // true
System.out.println("尝试获取空队列头部: " + taskQueue.poll()); // null
}
} Stack
和Deque
：我该如何选择，以及为什么？
这是个老生常谈但又很重要的问题。当我刚开始学习Java的时候，
Stack类似乎是理所当然的选择。然而，随着对集合框架的深入了解，我发现
java.util.Stack在现代Java开发中，通常不是实现栈行为的首选。
主要原因在于：
Stack类继承自
Vector，这意味着它是同步的。在多线程环境下，同步机制可以保证数据一致性，但在单线程环境下，这种同步开销是完全不必要的性能负担。此外，
Stack的API设计也略显陈旧，它直接暴露了
Vector的一些方法，比如
get(int index)，这在语义上与LIFO的栈操作有些冲突，可能导致误用。
所以，更推荐的做法是使用
java.util.Deque（双端队列）接口的实现类来模拟栈的行为。
Deque，顾名思义，是一个可以在两端进行插入和删除操作的队列。它提供了与栈操作完全对应的API方法：
push(E e)
: 相当于Stack
的push()
，将元素压入双端队列的头部。pop()
: 相当于Stack
的pop()
，移除并返回双端队列头部的元素。peek()
: 相当于Stack
的peek()
，返回双端队列头部的元素，但不移除。
ArrayDeque和
LinkedList都是
Deque接口的优秀实现。其中，
ArrayDeque通常被认为是实现栈和队列的更优选择，因为它基于数组实现，没有同步开销，且在大多数操作上比
LinkedList更快。
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeAsStackExample {
public static void main(String[] args) {
Deque stack = new ArrayDeque<>(); // 使用ArrayDeque作为栈
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("栈顶元素: " + stack.peek()); // 30
System.out.println("弹出元素: " + stack.pop()); // 30
System.out.println("新的栈顶元素: " + stack.peek()); // 20
// 尝试使用LinkedList作为栈
Deque stringStack = new LinkedList<>();
stringStack.push("A");
stringStack.push("B");
System.out.println("String栈顶: " + stringStack.peek()); // B
}
} 总而言之，如果你需要一个栈，请优先考虑使用
Deque接口的实现，尤其是
ArrayDeque，它在性能和API设计上都更符合现代Java开发的最佳实践。
Queue
接口的不同实现及其适用场景
Queue接口本身只定义了行为，具体的性能和特性则取决于其实现类。选择合适的
Queue实现对于程序的性能和健壮性至关重要。
-
LinkedList
:-
特点: 基于链表实现，因此在队列的两端进行插入和删除操作（
offer
和poll
）效率很高，时间复杂度为O(1)。它也可以作为Deque
使用，同时支持栈和队列操作。 -
适用场景: 当你需要频繁地在队列两端进行操作，且对内存占用没有极致要求时（链表节点会带来一些内存开销），
LinkedList
是一个不错的选择。例如，在实现一些简单的消息队列、任务调度器或者BFS算法时。
-
特点: 基于链表实现，因此在队列的两端进行插入和删除操作（
-
ArrayDeque
:-
特点: 基于可变大小的数组实现，没有同步开销，因此在单线程环境下通常比
LinkedList
和Stack
性能更好。它同样实现了Deque
接口，可以高效地作为栈或队列使用。 -
适用场景: 作为栈或队列的默认首选。在大多数情况下，如果你不需要线程安全，
ArrayDeque
在性能上会优于LinkedList
，因为它避免了链表节点的额外开销。尤其适合那些需要高性能、非阻塞的FIFO或LIFO操作的场景，比如解析器、算法中的状态管理。
-
特点: 基于可变大小的数组实现，没有同步开销，因此在单线程环境下通常比
-
PriorityQueue
:-
特点: 这是一个特殊的队列，它不遵循FIFO原则，而是根据元素的自然顺序或自定义的
Comparator
来决定元素的优先级。每次poll()
操作都会移除优先级最高的元素。 -
适用场景: 当你需要按照某种优先级顺序处理元素时，
PriorityQueue
是唯一的选择。例如，任务调度器中需要优先处理紧急任务，或者在实现Dijkstra算法、Prim算法等图算法时。
-
特点: 这是一个特殊的队列，它不遵循FIFO原则，而是根据元素的自然顺序或自定义的
-
ConcurrentLinkedQueue
(以及其他java.util.concurrent
包下的队列):-
特点:
ConcurrentLinkedQueue
是一个线程安全的非阻塞队列，基于链表实现。它通过CAS（Compare-And-Swap）操作来保证线程安全，而不是通过锁，因此在并发环境下性能通常优于synchronized
的队列。 -
适用场景: 在多线程环境中，当多个生产者和消费者需要安全地共享一个队列时，
ConcurrentLinkedQueue
是非常合适的。例如，生产者-消费者模式、日志收集系统、事件处理系统等。
-
特点:
选择哪种实现，关键在于你的具体需求：是需要高性能的单线程操作？还是需要线程安全的并发操作？亦或是需要基于优先级的处理？明确这些，选择自然就清晰了。
实际开发中，Stack
和Queue
有哪些常见应用场景？
在实际的软件开发中，
Stack和
Queue这两种看似简单的数据结构，却有着极其广泛且强大的应用。它们不仅仅是算法题的常客，更是许多复杂系统底层逻辑的基石。
Stack
的常见应用场景：
- 表达式求值与语法解析: 这是栈最经典的用途之一。例如，将中缀表达式转换为后缀表达式（逆波兰表达式），然后利用栈进行求值。编译器和解释器在解析代码时，也大量使用栈来处理函数调用、变量作用域等。
-
括号匹配: 检查代码中的括号（
()
,{},[]
）是否正确匹配，是栈的一个直接应用。每遇到一个左括号就入栈，遇到右括号就检查栈顶是否是对应的左括号，如果是则出栈。 - 深度优先搜索 (DFS): 在图或树的遍历中，非递归的DFS算法通常使用栈来保存待访问的节点。每访问一个节点，就将其未访问的邻居（或子节点）压入栈中。
- 浏览器历史记录 (前进/后退): 浏览器的“后退”功能就是一个典型的栈应用。每访问一个新页面，就将当前页面压入“后退栈”。点击“后退”时，从栈中弹出页面并跳转。如果还要实现“前进”功能，通常会使用两个栈。
- 函数调用栈: 操作系统和编程语言运行时环境，都使用栈来管理函数的调用。每当一个函数被调用时，其局部变量、参数和返回地址都会被压入栈中；函数执行完毕后，这些信息从栈中弹出。这就是为什么递归调用过深会导致“栈溢出”错误。
Queue
的常见应用场景：
- 广度优先搜索 (BFS): 与DFS对应，BFS算法在图或树的遍历中，使用队列来保存待访问的节点。它确保了先访问离起始点近的节点。
- 任务调度与消息队列: 生产者-消费者模式中，生产者将任务放入队列，消费者从队列中取出任务进行处理。这是构建高并发、解耦系统的重要手段，例如消息中间件（Kafka, RabbitMQ）的底层机制。
- 打印队列: 多个用户向打印机发送打印任务时，打印机通常会将这些任务放入一个队列，然后按照接收顺序逐一处理。
-
缓存淘汰策略: 虽然LRU（最近最少使用）通常用
LinkedHashMap
实现，但FIFO（先进先出）缓存淘汰策略可以直接用队列实现。最先进入缓存的数据，在缓存满时最先被淘汰。 -
操作系统进程调度: 操作系统中的CPU调度器，常常使用队列来管理处于就绪
状态的进程。例如，先来先服务（FCFS）调度算法就直接基于队列。
状态的进程。例如，先来先服务（FCFS）调度算法就直接基于队列。无论是简单的算法题，还是复杂的系统架构，
Stack和
Queue都以它们独特的访问模式，为我们提供了高效、简洁的数据管理方案。理解它们的特性和适用场景，是成为一个优秀程序员的必经之路。
