如何在Java中使用Stack和Queue-java教程-PHP中文网

Stack遵循LIFO，Queue遵循FIFO；Java中推荐用ArrayDeque实现Stack，Queue常用LinkedList、ArrayDeque、PriorityQueue等，适用于表达式求值、BFS、任务调度等场景。

如何在java中使用stack和queue

在Java中，

Stack

登录后复制

和

Queue

登录后复制

是两种核心的数据结构，它们提供了一种管理数据序列的特定方式。简单来说，

Stack

登录后复制

遵循“后进先出”（LIFO）原则，就像一摞盘子，最后放上去的盘子最先被拿走；而

Queue

登录后复制

则遵循“先进先出”（FIFO）原则，就像排队买票，最先排队的人最先买到票。理解并恰当使用它们，能显著优化我们处理数据流和特定算法的效率。

解决方案

要在Java中使用

Stack

登录后复制

和

Queue

登录后复制

，我们需要了解它们的接口和常用实现。

使用

Stack

登录后复制

java.util.Stack

登录后复制

是Java集合框架中一个历史悠久的类，它继承自

Vector

登录后复制

，因此是同步的（线程安全），这在单线程环境中反而会带来不必要的性能开销。它的核心操作包括：

立即学习“Java免费学习笔记（深入）”；

```
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<String> 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<String> 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<Integer> 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<String> stringStack = new LinkedList<>();
        stringStack.push("A");
        stringStack.push("B");
        System.out.println("String栈顶: " + stringStack.peek()); // B
    }
}

登录后复制

总而言之，如果你需要一个栈，请优先考虑使用

Deque

登录后复制

接口的实现，尤其是

ArrayDeque

登录后复制

，它在性能和API设计上都更符合现代Java开发的最佳实践。

如知AI笔记

如知笔记——支持markdown的在线笔记，支持ai智能写作、AI搜索，支持DeepseekR1满血大模型

查看详情

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算法等图算法时。
```
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）调度算法就直接基于队列。