目录
一、什么是栈？
二、Java中的栈帧
三、栈的应用
四、栈的基本方法
五、栈的几种实现方式
1、基于简单数组的实现方式：
2、基于动态数组的实现方式：
3、基于链表的实现方式：
基于数组实现和基于链表实现的比较
（1）基于数组实现的栈：
（2）基于链表实现的栈：
4、基于队列的实现方式：
六、双端栈
1、定义
2、特点
3、示例
java基础类型 栈七、关于栈的习题应用
1、括号匹配
2、逆波兰表达式求值
3、表达式求值
4、函数调用堆栈
5、汉诺塔问题
6、迷宫求解
引言：
在Java编程语言中，栈（Stack）是一种非常重要的数据结构，它在方法调用和变量存储中扮演着关键的角色。了解Java中的栈对于程序员来说至关重要，本篇博客将详细介绍Java中的栈的知识，并结合一些例子来帮助读者更好地理解。
一、什么是栈？
栈（Stack）是一种常见的数据结构，具有后进先出（LIFO，Last In First Out）的特性，即最后入栈的元素最先出栈。栈通常用于存储临时性的数据，如方法调用过程中的局部变量、操作数栈等。在计算机科学中，栈的应用非常广泛，包括编程语言中的函数调用、内存分配以及表达式求值等领域。在Java编程语言中，栈也被广泛应用于方法调用和内存管理的过程中。
二、Java中的栈帧
在Java虚拟机（JVM）中，每个方法在运行时都会创建一个对应的栈帧（Stack Frame），栈帧用于存储方法的局部变量、操作数栈、动态链接、返回地址等信息。
栈帧的结构如下：
- 局部变量表（Local Variable Table）：局部变量表用于存储方法参数和方法内部定义的局部变量。局部变量表中的每个槽位可以存储一个基本类型的值或对象引用。在方法调用时，参数和本地变量的值会被压入局部变量表；在方法执行期间，可以通过索引来访问局部变量表中的值。
- 操作数栈（Operand Stack）：操作数栈是用于执行方法时进行计算的临时数据存储区域。操作数栈的元素可以是任意的Java数据类型，包括基本类型和对象引用。在方法执行过程中，操作数栈用于存储方法执行过程中的计算结果、方法参数以及临时变量等数据。
- 动态链接（Dynamic Linking）：动态链接指向运行时常量池中该方法的符号引用的指针。在Java中，动态链接主要用于解析方法调用的目标地址，以便在运行时能够正确调用方法。
- 方法返回地址：方法返回地址是指向方法调用者的指令地址。当方法执行完毕后，JVM会使用返回地址恢复执行方法调用者的指令。
栈帧的创建和销毁是在方法调用和返回过程中自动进行的。每当发生方法调用时，JVM会为该方法创建一个新的栈帧并将其推入调用栈（Call Stack），当方法返回时，对应的栈帧会被销毁，栈顶指针会回到前一个方法的栈帧。栈帧的动态创建和销毁确保了方法的独立性和互相调用的正确性。
三、栈的应用
- 符号匹配
- HTML和XML文件中的标签匹配（实质还是符号匹配）
- 实现函数调用
- 文本编辑器中的撤销
- 网页浏览器中已访问页面的历史记录
- 作为一个算法的辅助数据结构
四、栈的基本方法
- push(Object item)：将元素item压入栈顶。
- pop()：弹出栈顶元素，并将其从栈中删除。
- peek()：返回栈顶元素，但不删除它。
- isEmpty()：判断栈是否为空，返回布尔值。
- search(Object item)：搜索元素item在栈中的位置（从栈顶开始），如果找到则返回其距离栈顶的位置（栈顶为1），如果未找到则返回-1。
- clear()：对当前栈进行清空。
下面是一个示例代码，演示了如何使用Stack类进行栈的基本操作：
执行以上代码，输出结果为：
通过使用Stack类提供的基本方法，我们可以方便地对栈进行操作，包括压入、弹出、查看栈顶元素、判断栈是否为空以及搜索元素在栈中的位置。
五、栈的几种实现方式
1、基于简单数组的实现方式：
使用简单数组作为底层数据结构来实现栈，通过将栈顶元素的索引存储在变量中，实现压栈和弹栈操作，每次压栈时将元素添加到数组末尾，每次弹栈时将栈顶元素从数组中删除。由于数组的长度是固定的，需要提前定义栈的最大容量。
示例：
2、基于动态数组的实现方式：
使用动态数组（如ArrayList）作为底层数据结构来实现栈，通过在动态数组的尾部进行插入和删除操作来实现栈的功能。当栈容量不足时，动态数组可以自动进行扩容，当栈元素减少时，动态数组可以自动进行缩容。这种实现方式提供了动态调整容量的特性。
示例：
3、基于链表的实现方式：
使用链表作为底层数据结构来实现栈，链表的头部或尾部作为栈顶，每次插入和删除操作都在链表的头部进行，通过修改引用来实现栈的操作。链表实现的栈可以动态增加和缩小容量，不需要提前定义栈的最大容量，但相对于数组实现，需要更多的空间开销。
示例：
基于数组实现和基于链表实现的比较
（1）基于数组实现的栈：
- 各个操作都是常数时间开销
- 每隔一段时间进行的倍增操作的时间开销较大
（2）基于链表实现的栈：
- 栈规模的增加和减小都很容易
- 各个操作都是常数时间开销
- 每个操作都需要使用额外的空间和时间开销来处理指针
4、基于队列的实现方式：
使用队列作为底层数据结构来实现栈，可以使用两个队列来模拟栈的操作。当压栈时，将元素添加到非空队列中；当弹栈时，将非空队列中的元素依次弹出并放入另一个空队列中，直到剩下最后一个元素，即栈顶元素，然后弹出。这种实现方式可以保持栈顶元素总是在队列的尾部，模拟了栈的后进先出（LIFO）特性。
示例：
六、双端栈
1、定义
双端栈（Double Ended Stack），也被称为双端队列（Deque），是一种支持在两端进行插入和删除操作的数据结构。它可以在栈顶和栈底执行压栈和弹栈操作，因此既能模拟栈的后进先出（LIFO）特性，又可以模拟队列的先进先出（FIFO）特性。
双端栈是线性表的一种,更是栈的一个特殊分类，可用借用动态数组+栈的组合实现。
2、特点
双端栈的特点是可以从两个方向进行操作，即从左侧插入和删除元素，也可以从右侧插入和删除元素。这使得双端栈在某些场景下可以提供更灵活的操作和更高的效率。
3、示例
下面是一个使用Java的Deque实现双端栈的示例代码：
在这个示例中，我们使用了Java的Deque，具体是ArrayDeque实现类。ArrayDeque是基于可调整大小的数组实现的双端队列，可以在队列的两端进行插入和删除操作。我们将其作为双端栈的底层数据结构来实现。
通过双端栈，我们可以在栈顶和栈底进行元素的插入和删除操作。例如：
在这个例子中，我们将元素依次压栈，并使用peek方法查看栈顶元素。随后，我们连续进行了三次弹栈操作，可以看到栈的后进先出特性。最后，我们通过isEmpty方法验证栈是否为空。
通过双端栈，我们可以自由地在栈顶和栈底进行操作，根据具体的需求实现不同的功能。
七、关于栈的习题应用
1、括号匹配
给定一个包含括号字符的字符串，判断括号是否匹配，例如 “((()))” 是匹配的，而 “(()” 则不匹配。可以使用栈来实现括号匹配的算法。
在上面的示例代码中，我们定义了一个isBracketMatch方法来判断输入的字符串中的括号是否匹配。我们使用一个Stack<Character>来存储左括号，遍历输入字符串，遇到左括号就入栈，遇到右括号就出栈并匹配。最后检查栈是否为空来判断括号是否完全匹配。
在main方法中我们则可以测试该方法的使用，可以看到input1是匹配的，而input2则不匹配。
2、逆波兰表达式求值
给定一个逆波兰表达式，计算其值。逆波兰表达式是一种通过后缀表达式来进行计算的算法，可以使用栈来实现逆波兰表达式的求值。
在以上示例代码中，我们定义了一个evalRPN方法，用于计算给定的逆波兰表达式的值。我们使用一个Stack<Integer>来存储操作数，遍历逆波兰表达式，当遇到操作数时入栈，当遇到运算符时从栈中弹出相应数量的操作数进行计算后将结果入栈。最终栈中剩下的元素即为逆波兰表达式的计算结果。
在main方法中我们则可以测试该方法的使用，可以看到给定逆波兰表达式 {“2”, “1”, “+”, “3”, “*”} 的值为9。
3、表达式求值
给定一个中缀表达式（如 3 * (4 + 5) - 2），计算其值。可以使用栈来将中缀表达式转换为后缀表达式，然后使用栈来求解后缀表达式。
在以上示例代码中，我们定义了三个方法：
- evaluateInfixExpression：用于计算给定中缀表达式的值。这个方法首先将中缀表达式转换为后缀表达式，然后再调用evaluatePostfixExpression方法对后缀表达式求值。
- infixToPostfix：用于将中缀表达式转换为后缀表达式。这个方法使用一个StringBuilder来构建后缀表达式，同时使用一个栈来辅助转换。遍历中缀表达式的字符，遇到数字直接添加到后缀表达式中，遇到左括号入栈，遇到右括号则将栈顶的运算符全部弹出并添加到后缀表达式中，直到遇到左括号，括号不添加到最终结果中；遇到运算符时，如果栈顶的运算符的优先级高于或等于当前运算符，则将栈顶的运算符弹出并添加到后缀表达式中，然后将当前运算符入栈。
- evaluatePostfixExpression：用于对后缀表达式进行求值。这个方法使用一个栈来存储操作数，遍历后缀表达式的字符，遇到数字就入栈，遇到运算符就从栈中弹出相应数量的操作数进行计算后将结果入栈。返回栈中剩下的元素即为后缀表达式的计算结果。
在main方法中我们则可以测试该方法的使用，可以看到给定中缀表达式 “3 * (4 + 5) - 2” 的值为25。
4、函数调用堆栈
理解函数调用时栈的使用情况，包括函数调用、参数传递、局部变量的存储等，可以通过手动模拟函数调用过程并使用栈来实现。
在以上示例代码中，我们定义了四个函数：func1、func2、func3和func4。这些函数之间通过函数调用进行嵌套调用。
在main方法中，我们手动创建了一个栈帧栈stack，并在每个函数中使用stack来保存函数调用过程中的栈帧信息。在每个函数开始时，我们使用来将当前函数的栈帧入栈；在每个函数结束时，我们使用来将当前函数的栈帧出栈。
最后，在main方法中，我们输出了栈帧信息，可以看到函数调用的顺序和栈帧的变化情况。
5、汉诺塔问题
使用栈来求解经典的汉诺塔问题，将 n 个盘子从一个柱子移动到另一个柱子，需要借助第三个柱子作为中转。
在以上示例代码中，我们使用栈来模拟汉诺塔问题的求解过程。首先我们定义了一个HanoiStep类来表示汉诺塔问题的每一步移动，包括盘子数n以及起始柱子、中转柱子、目标柱子的信息。然后我们使用栈stack来记录每一步的移动过程，初始时将整个问题压入栈中，然后在循环中弹出栈顶的移动步骤，直到栈中的步骤全部完成。
通过这种方式，我们可以使用栈来求解经典的汉诺塔问题，将n个盘子从一个柱子移动到另一个柱子，并借助第三个柱子作为中转。
6、迷宫求解
使用栈来搜索迷宫路径，深度优先搜索算法可以使用栈来实现，通过回溯法找出迷宫的所有路径。
在以上示例代码中，我们定义了一个MazeSolver类来表示迷宫求解的过程。在findPaths方法中，我们使用栈stack来记录搜索过程中的路径信息，初始时将起始点入栈，然后在循环中不断弹出栈顶的点进行搜索，直到栈为空。在搜索过程中，我们通过遍历四个方向来扩展搜索空间，将有效的下一步点入栈，并且对访问过的点进行标记，防止重复访问。
通过这种方式，我们可以使用栈来实现深度优先搜索算法，通过回溯法找出迷宫的所有路径。这样可以得出迷宫中从起点到终点的所有可能路径。
总结：
本篇博客详细介绍了Java中栈的知识，包括栈的基本概念、栈帧的结构、Java中的栈帧、栈的应用、栈的基本方法、栈的几种实现方式、双端栈以及关于栈的习题应用。希望读者能通过本文更加深入地理解Java中栈的相关知识，并在实际编程中灵活运用。
通过学习本篇博客，相信读者对Java中的栈有了更清晰的认识，也能更加熟练地运用栈来解决实际的编程问题。感谢阅读！
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/574.html