深入掌握栈与队列，用Java构建高效数据处理之道

  咦咦咦，各位小可爱，我是你们的好伙伴——bug菌，今天又来给大家普及Java SE相关知识点了，别躲起来啊，听我讲干货还不快点赞，赞多了我就有动力讲得更嗨啦！所以呀，养成先点赞后阅读的好习惯，别被干货淹没了哦~

🏆本文收录于「滚雪球学Java」专栏，专业攻坚指数级提升，助你一臂之力，带你早日登顶🚀，欢迎大家关注&&收藏！持续更新中，up！up！up！！

环境说明：Windows 10 + IntelliJ IDEA 2021.3.2 + Jdk 1.8

👋 朋友们，欢迎来到数据结构和算法的世界！今天我们要讲的是两种非常基础但又超级有用的结构——栈（Stack）和队列（Queue）。这两个结构看似简单，却在实际开发中有广泛应用。通过今天的学习，希望你不仅能掌握它们的实现方式，还能理解它们的应用场景，甚至在日常项目中游刃有余地运用它们！那就让我们一起出发，探索栈与队列的秘密吧！

📖 目录

1. ✨ 前言
2. 📜 摘要
3. 📚 简介
4. 🔍 概述
5. 📑 核心源码解读
6. 📂 案例分析
7. 🚀 应用场景演示
8. 👍 优缺点分析
9. 🔨 类代码方法介绍及演示
10. 🧪 测试用例
11. 📊 测试结果预期
12. 📝 测试代码分析
13. 📌 小结
14. 🔔 总结
15. 📬 寄语

✨ 前言

栈和队列是计算机科学中不可或缺的基础结构，虽然简单却能有效解决许多实际问题。在Java语言中，栈可以通过Stack类实现，而队列可以使用Queue接口或者LinkedList来实现。这两种结构在日常开发中应用广泛，无论是用于管理浏览历史、页面导航，还是用于任务调度，栈和队列都能带来巨大便利。所以掌握它们不仅是编程入门的关键，更是编写高效代码的重要技能。接下来，让我们一步步深入它们的世界！

📜 摘要

本文详细探讨Java语言下栈和队列的实现与应用，包括两者的特性、源码实现、典型应用场景和常见测试用例。通过通俗易懂的解释和代码实例，帮助你轻松理解栈和队列的工作机制，并应用到实际开发中。

📚 简介

栈（Stack） 是一种后进先出（LIFO，Last In First Out）的数据结构。具体来说，数据只能从栈的顶部进行插入和删除操作，像极了生活中叠放的盘子——我们只能从顶部拿出或放入新盘子。栈在程序设计中有广泛应用，常用于递归调用、表达式求值和浏览器的前进后退功能等。

队列（Queue） 是一种先进先出（FIFO，First In First Out）的数据结构。数据从队列尾部加入，从队列头部取出，类似于排队买票。队列被广泛用于任务排队、缓冲区等需要顺序处理的场景，如线程池、进程调度和消息传递等。

🔍 概述

1. 栈：在Java中，通过Stack类实现。基本操作包括push（压栈）、pop（出栈）和peek（查看栈顶元素）。栈在递归算法、数学表达式计算等方面有极高的适用性。
2. 队列：在Java中，可以通过Queue接口或LinkedList来实现。主要操作有enqueue（入队）和dequeue（出队），常用于任务排队、资源管理等应用。

📑 核心源码解读

我们来看看如何用Java实现这两个结构，并解释各个操作的细节。

栈的实现

import java.util.Stack;

public class MyStack {
    private Stack<Integer> stack;

    public MyStack() {
        this.stack = new Stack<>();
    }

    // 压栈操作
    public void push(int value) {
        stack.push(value);
    }

    // 出栈操作
    public int pop() {
        return stack.pop();
    }

    // 查看栈顶元素
    public int peek() {
        return stack.peek();
    }
}

在上面的代码中，我们使用Java的Stack类来实现了一个整数类型的栈。通过push方法将元素加入栈顶，pop方法移除栈顶元素，peek方法返回栈顶元素但不移除它。

队列的实现

import java.util.LinkedList;
import java.util.Queue;

public class MyQueue {
    private Queue<Integer> queue;

    public MyQueue() {
        this.queue = new LinkedList<>();
    }

    // 入队操作
    public void enqueue(int value) {
        queue.add(value);
    }

    // 出队操作
    public int dequeue() {
        return queue.poll();
    }

    // 查看队首元素
    public int peek() {
        return queue.peek();
    }
}

在队列实现中，我们使用LinkedList来模拟队列结构。enqueue方法将元素加入队尾，dequeue方法移除并返回队首元素，peek方法则返回队首元素但不移除。

这段代码定义了一个MyQueue类，它使用Java内置的LinkedList来实现队列功能。MyQueue类封装了队列的基本操作，包括入队、出队和查看队首元素。以下是代码的详细解析：

代码解析

import java.util.LinkedList;
import java.util.Queue;

1. 导入包：引入了java.util.LinkedList和java.util.Queue类。
   • Queue是Java的队列接口，定义了队列的基本操作。
   • LinkedList是一个具体实现，支持Queue接口的所有方法，并且由于链表结构，适合用于队列的操作。

public class MyQueue {
    private Queue<Integer> queue;

    public MyQueue() {
        this.queue = new LinkedList<>();
    }

2. MyQueue类定义：
   • queue属性是一个Queue接口类型的变量，使用LinkedList作为其实现。
   • 在构造方法MyQueue()中，初始化queue为一个空的LinkedList。这样可以使用队列的标准操作方法来进行元素的增删和查看。

    // 入队操作
    public void enqueue(int value) {
        queue.add(value);
    }

3. 入队操作：
   • enqueue(int value)方法用于将一个整数value添加到队列的尾部。
   • 通过调用queue.add(value)实现入队操作。add()方法将元素插入到LinkedList末尾，符合队列的“先进先出”（FIFO）规则。

    // 出队操作
    public int dequeue() {
        return queue.poll();
    }

4. 出队操作：
   • dequeue()方法用于从队列头部移除并返回队首元素。
   • 通过调用queue.poll()实现出队操作。poll()方法会删除并返回队首元素。如果队列为空，poll()会返回null，避免抛出异常。

    // 查看队首元素
    public int peek() {
        return queue.peek();
    }
}

5. 查看队首元素：
   • peek()方法用于返回队首元素，但不移除该元素。
   • queue.peek()实现了此功能。若队列为空，peek()返回null，否则返回队首元素的值。

小结

MyQueue类通过LinkedList实现了一个基本的整数队列，支持以下操作：

• enqueue(int value)：将元素添加到队列尾部，实现入队。
• dequeue()：移除并返回队首元素，实现出队操作；如果队列为空，返回null。
• peek()：返回队首元素但不移除，若队列为空则返回null。

此实现基于LinkedList的特点，使得队列的入队和出队操作高效，适用于先进先出的数据管理需求。

📂 案例分析

案例1：浏览器的回退与前进功能

浏览器的“后退”与“前进”功能就是栈的经典应用。假设用户按顺序访问了A、B、C页面，并点击“后退”按钮，栈会记录下每个页面的状态，从C退到B再退到A。这种行为符合栈的“后进先出”特性。

案例2：银行排队系统

银行排队系统中，客户按照到达顺序排队，当柜台空闲时，队首的客户将被优先处理。这正是队列的“先进先出”特性，确保客户按到达顺序依次处理。

🚀 应用场景演示

• 栈的应用：浏览器历史回退、文件系统路径管理、函数调用栈等。
• 队列的应用：任务调度系统、消息传递系统、打印机任务队列等。

👍 优缺点分析

• 栈的优缺点：

  • 优点：简单易用，适合递归或“后进先出”逻辑的需求。
  • 缺点：只能访问栈顶，限制了某些应用场景。

• 队列的优缺点：

  • 优点：满足顺序处理需求，适合任务排队和资源调度。
  • 缺点：在某些情况下，顺序处理效率不如更复杂的数据结构，如双向队列。

🔨 类代码方法介绍及演示

栈方法演示

MyStack stack = new MyStack();
stack.push(10);
stack.push(20);
System.out.println(stack.pop()); // 输出 20
System.out.println(stack.peek()); // 输出 10

队列方法演示

MyQueue queue = new MyQueue();
queue.enqueue(10);
queue.enqueue(20);
System.out.println(queue.dequeue()); // 输出 10
System.out.println(queue.peek()); // 输出 20

🧪 测试用例

栈测试

public static void main(String[] args) {
    MyStack stack = new MyStack();

    // 测试空栈的边界情况
    assert stack.peek() == null : "空栈peek测试失败";
    assert stack.pop() == null : "空栈pop测试失败";

    // 正常入栈出栈测试
    stack.push(1);
    stack.push(2);
    assert stack.pop() == 2 : "栈pop测试失败";
    assert stack.peek() == 1 : "栈peek测试失败";

    System.out.println("栈测试通过！");
}

队列测试

public static void main(String[] args) {
    MyQueue queue = new MyQueue();

    // 测试空队列的边界情况
    assert queue.peek() == null : "空队列peek测试失败";
    assert queue.dequeue() == null : "空队列dequeue测试失败";

    // 正常入队出队测试
    queue.enqueue(1);
    queue.enqueue(2);
    assert queue.dequeue() == 1 : "队列dequeue测试失败";
    assert queue.peek() == 2 : "队列peek测试失败";

    System.out.println("队列测试通过！");
}

📊 测试结果预期

• 栈测试：pop操作应返回2，peek操作应返回1。
• 队列测试：dequeue操作应返回1，peek操作应返回2。

📝 测试代码分析

  在本次的代码演示中，我将会深入剖析每句代码，详细阐述其背后的设计思想和实现逻辑。通过这样的讲解方式，我希望能够引导同学们逐步构建起对代码的深刻理解。我会先从代码的结构开始，逐步拆解每个模块的功能和作用，并指出关键的代码段，并解释它们是如何协同运行的。通过这样的讲解和实践相结合的方式，我相信每位同学都能够对代码有更深入的理解，并能够早日将其掌握，应用到自己的学习和工作中。

这段代码是对MyStack栈类的单元测试，分为空栈测试和正常入栈出栈测试，确保MyStack在各种情况下的行为都符合预期。以下是对代码的详细解析：

代码解析

public static void main(String[] args) {
    MyStack stack = new MyStack();

1. 初始化栈：创建一个MyStack类的实例stack。这个实例用于接下来的栈操作测试。

    // 测试空栈的边界情况
    assert stack.peek() == null : "空栈peek测试失败";
    assert stack.pop() == null : "空栈pop测试失败";

2. 空栈边界测试：

   • assert stack.peek() == null：调用peek()方法检查栈顶元素，但因为栈为空，peek()应返回null。若返回非null，断言会失败，并输出"空栈peek测试失败"的信息。
   • assert stack.pop() == null：调用pop()方法尝试从空栈中弹出元素，但因栈为空，pop()应返回null。若返回非null，断言会失败，并输出"空栈pop测试失败"的信息。

   通过这两条断言，验证MyStack在空栈状态下的peek()和pop()操作不会抛出异常，而是安全地返回null。

    // 正常入栈出栈测试
    stack.push(1);
    stack.push(2);
    assert stack.pop() == 2 : "栈pop测试失败";
    assert stack.peek() == 1 : "栈peek测试失败";

3. 正常入栈出栈测试：

   • stack.push(1)和stack.push(2)：将元素1和2依次压入栈中。由于栈的后进先出（LIFO）特性，元素2会位于栈顶。
   • assert stack.pop() == 2：调用pop()方法，将栈顶元素2弹出。若弹出的元素不是2，则断言会失败，提示"栈pop测试失败"。
   • assert stack.peek() == 1：此时栈顶元素应为1，因为2已弹出。调用peek()方法查看栈顶元素，若返回的不是1，断言会失败，提示"栈peek测试失败"。

   这些断言确保栈在有元素时能正确执行入栈和出栈操作，并保持后进先出的顺序。

    System.out.println("栈测试通过！");
}

4. 输出测试结果：若所有断言均通过，则输出"栈测试通过！"表示栈操作符合预期。

小结

该测试代码验证了MyStack类的两个关键方面：

• 空栈处理：在栈为空时，pop()和peek()返回null，避免异常，提高代码的健壮性。
• 正常操作：验证栈在有元素时的正确行为，确保后进先出的特性。

通过这些测试，我们可以更好地确认MyStack类的核心功能正确无误。

📌 小结

栈和队列虽简单，但在程序设计中应用广泛。本文不仅展示了它们的实现细节，还带你了解了它们的应用场景及优缺点。掌握了这些内容，相信你可以在日常编程中更加得心应手。

🔔 总结

栈和队列是编程中不可或缺的工具，它们帮助我们实现结构化的存取操作。希望通过本文，你能够掌握这两种数据结构，并灵活运用在你的项目中。无论是解决问题的能力，还是代码的组织方式，都能因此得到提升！

📬 寄语

学习数据结构并不总是简单的事，但它们能带给你写代码的自信与高效。希望大家在学习中找到乐趣，慢慢积累和进步，未来你会看到自己不一样的编程能力！加油！

  …

  好啦，这期的内容就基本接近尾声啦，若你想学习更多，可以参考这篇专栏总结《「滚雪球学Java」教程导航帖》，本专栏致力打造最硬核 Java 零基础系列学习内容，🚀打造全网精品硬核专栏，带你直线超车；欢迎大家订阅持续学习。

🌴附录源码

  如上涉及所有源码均已上传同步在「Gitee」，提供给同学们一对一参考学习，辅助你更迅速的掌握。

☀️建议/推荐你

  无论你是计算机专业的学生，还是对编程有兴趣的小伙伴，都建议直接毫无顾忌的学习此专栏「滚雪球学Java」，bug菌郑重承诺，凡是学习此专栏的同学，均能获取到所需的知识和技能，全网最快速入门Java编程，就像滚雪球一样，越滚越大，指数级提升。

  最后，如果这篇文章对你有所帮助，帮忙给作者来个一键三连，关注、点赞、收藏，您的支持就是我坚持写作最大的动力。

  同时欢迎大家关注公众号:「猿圈奇妙屋」 ，以便学习更多同类型的技术文章，免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板、技术文章Markdown文档等海量资料。

📣Who am I?

我是bug菌，CSDN | 掘金 | InfoQ | 51CTO | 华为云 | 阿里云 | 腾讯云 等社区博客专家，C站博客之星Top30，华为云2023年度十佳博主，掘金多年度人气作者Top40，掘金等各大社区平台签约作者，51CTO年度博主Top12，掘金/InfoQ/51CTO等社区优质创作者；全网粉丝合计 30w+；硬核微信公众号「猿圈奇妙屋」，欢迎你的加入！免费白嫖最新BAT互联网公司面试真题、4000G PDF电子书籍、简历模板等海量资料，你想要的我都有，关键是你不来拿哇。