Java 【数据结构】 栈(Stack)和队列(Queue)【神装】

阅读本书更多章节>>>>

 登神长阶

 第三神装 Stack

   第四神装 Queue  

---

目录

🔋一.栈 Stack

💻1.概念

🖥️2.基本操作 

🖨️3.相关OJ题  

🖱️4.栈、虚拟机栈和栈帧的区别

🪫二.队列 Queue

🖲️1.概念

💽2.基本操作

🔌三.总结与反思

---

🔋一.栈 Stack

💻1.概念

        在 Java 中，栈（Stack）是一种后进先出（LIFO）的数据结构，用于存储元素。在栈中，只有栈顶的元素是可见的和可访问的，其他元素都被隐藏起来，直到栈顶的元素被移除或弹出。Java 中的 java.util.Stack 类实现了这种栈的数据结构，并且是线程安全的，继承自 Vector 类。

压栈：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。 出栈：栈的删除操作叫做出栈。 出数据在栈顶 。

🖥️2.基本操作 

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

示例

以下是一个使用 Stack 类的简单示例：

import java.util.Stack;public class StackExample {    public static void main(String[] args) {        Stack<String> stack = new Stack<>();                // 压栈操作        stack.push("Java");        stack.push("Python");        stack.push("C++");                // 弹栈操作        String topLanguage = stack.pop();        System.out.println("弹出栈顶元素：" + topLanguage);                // 查看栈顶元素        String currentTop = stack.peek();        System.out.println("当前栈顶元素：" + currentTop);                // 判空操作        if (stack.isEmpty()) {            System.out.println("栈为空");        } else {            System.out.println("栈不为空");        }    }}

这个示例展示了栈的基本操作，包括压栈、弹栈、查看栈顶元素和判空。栈在 Java 中常用于处理需要后进先出顺序的场景，例如表达式求值、逆序输出等。

🖨️3.相关OJ题  

括号匹配

 

逆波兰表达式

 

出栈入栈次序匹配

 

最小栈

🖱️4.栈、虚拟机栈和栈帧的区别

栈（Stack）：

在计算机科学中，栈是一种数据结构，遵循后进先出（LIFO）的原则，用于存储和管理函数调用、局部变量和临时数据。栈通常由操作系统提供支持，用于管理程序的执行环境和内存分配。

虚拟机栈（Java Virtual Machine Stack）：

虚拟机栈是 Java 虚拟机在执行 Java 程序时使用的内存区域之一，与线程生命周期相同。每个线程在创建时都会分配一个对应的虚拟机栈，用于存储方法的调用栈帧（Stack Frame）、局部变量表、操作数栈等信息。虚拟机栈中的栈帧存储了方法的运行时数据结构，每个方法的调用都会创建一个对应的栈帧。

栈帧（Stack Frame）：

栈帧是虚拟机栈中的一个重要概念，用于表示方法在虚拟机中的运行状态和执行信息。每个方法的调用都会对应一个栈帧，包含局部变量表、操作数栈、动态链接、返回地址等部分。当方法被调用时，会创建一个新的栈帧压入虚拟机栈，并在方法执行完毕后弹出栈帧，恢复上一个调用栈帧的执行。

区别总结：

栈 是一种数据结构，用于存储和管理数据，具有后进先出的特性。虚拟机栈 是 Java 虚拟机提供的内存区域，用于存储线程的方法调用栈帧和相关数据。栈帧 是虚拟机栈中的一个部分，用于表示方法的运行状态和执行信息，包含局部变量表、操作数栈等。

🪫二.队列 Queue

🖲️1.概念

        在 Java 中，队列（Queue）是一种先进先出（FIFO）的数据结构，用于存储元素。队列在 java.util 包中有多种实现，如 LinkedList、ArrayDeque 和 PriorityQueue。只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

💽2.基本操作

方法	功能
boolean offer(E e)	入队列
E poll()	出队列
peek()	获取队头元素
int size()	获取队列中有效元素个数
boolean isEmpty()	检测队列是否为空

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

public static void main(String[] args) {    Queue<Integer> q = new LinkedList<>();    q.offer(1);    q.offer(2);    q.offer(3);    q.offer(4);    q.offer(5); // 从队尾入队列    System.out.println(q.size());    System.out.println(q.peek()); // 获取队头元素    q.poll();    System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回    if(q.isEmpty()){    System.out.println("队列空");    }else{    System.out.println(q.size());    }}

这个示例展示了队列的基本操作，包括入队、出队、查看队头元素和判空。队列在 Java 中常用于实现任务调度、消息传递等场景，能够有效管理元素的顺序和执行顺序。

🔌三.总结与反思

💡人类也需要梦想者，这种人醉心于一种事业的大公无私的发展，因而不能注意自身的物质利益。——居里夫人

        在学习 Java 中的栈（Stack）和队列（Queue）这两种经典数据结构时，我深刻体会到它们的重要性和应用广泛性。通过掌握栈和队列的基本操作，如入栈、出栈、入队、出队，我加深了对数据结构的理解。

        在实践中，我意识到需要关注空间复杂度和时间复杂度的问题，尤其在处理大规模数据集时。异常处理也是学习中的重要环节，确保程序能够正常处理各种边界情况。了解栈和队列在算法和程序设计中的应用场景，如表达式求值、任务调度等，为我提供了有效的工具。通过深入研究 Java 中不同的栈和队列实现类，我学习了它们的特性和使用方法。

        我希望进一步应用所学知识，深入探索栈和队列在更复杂算法和数据结构中的应用，提升自己的编程能力。通过不断练习和实践，我相信能够更熟练地运用栈和队列，解决实际问题，并在日常开发中发挥它们的作用。我的学习之路将持续前行，为未来的软件开发工作做好准备。

---

🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀

以上，就是本期的全部内容啦，若有错误疏忽希望各位大佬及时指出💐

  制作不易，希望能对各位提供微小的帮助，可否留下你免费的赞呢🌸

 

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/xuetang/2024-04-27/162800.html，文章来源：网络cs，作者：纳雷武，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！