Java集合框架：栈、Stack详解
目录
一、栈
二、栈的使用
1. Stack类
2. 栈的模拟实现
三、栈的应用场景
1. 改变元素的序列
2. 将递归转化为循环（如：逆序打印链表）
3. 栈的oj题练习（oj题中都用到了栈这种数据结构）
四、栈，虚拟机栈，栈帧的区别
前言
栈是一种数据结构，一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。数据插入和删除的操作的一端称作栈顶，另一端称作栈底。栈中的数据元素遵守一个原则：先进后出。
一、栈
| 压栈：栈的插入操作叫做压栈/ 进栈，压栈在栈顶操作。 |
| 出栈：栈的删除操作叫做出栈，出栈数据也是在栈顶。 |
如下图解：
栈中的数据元素遵循后进先出的原则（Last in first out）就像子弹的上膛操作和射击操作。
二、栈的使用
在Java集合框架中，栈使用的具体类是Stack，（但是并不是只有Sack一个类可以当作栈来使用）接下来就具体介绍下集合框架中栈的使用。
1. Stack类
Stack类的方法的使用：
| Stack（） | 实例化一个栈（此时栈是空的） |
| E push（E e） | 压栈操作，将e元素入栈，并返回e |
| E pop（） | 将栈顶元素出栈并返回 |
| E peek（） | 获取栈顶元素（但此时栈顶元素并没有出栈，只是看了一眼栈顶元素是哪个） |
| int size（） | 获取栈中有效元素个数 |
| boolean empty（） | 判断栈是否为空（是否有元素），返回值为布尔类型 |
栈方法的使用演示：
public static void main(String[] args) {Stack stack = new Stack<>();stack.push(1);stack.push(2);stack.push(3);stack.push(4);System.out.println(stack.size());System.out.println(stack.peek());System.out.println(stack.pop());System.out.println(stack.size());System.out.println(stack.empty());} 要想真正了解Stack类中方法实现的逻辑最好还是模拟实现一个栈；
2. 栈的模拟实现
//用数组/顺序表实现的栈
//顺序栈public class MyStack {public int[] elem;public int usedSize;public MyStack() {this.elem = new int[10];}//压栈public void push(int val) {if (isFull()) {elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize++] = val;}public boolean isFull() {return usedSize == elem.length;}//出栈public int pop() {if (isEmpty()) {throw new EmptyException("栈是空的！");}/*int val = elem[usedSize - 1];usedSize--;return val;*/return elem[--usedSize];}public boolean isEmpty() {return usedSize == 0;}//求栈中元素个数public int size() {return usedSize;}//获取栈顶元素public int peek() {if (isEmpty()) {throw new EmptyException("栈是空的！");}return elem[usedSize - 1];}三、栈的应用场景
1. 改变元素的序列
2. 将递归转化为循环（如：逆序打印链表）
几种打印链表的方式：
//递归打印链表(逆序打印链表)public void display3(ListNode pHead) {if (pHead == null) return;if (pHead.next == null) {System.out.print(pHead.val + " ");return;}display3(pHead.next);System.out.print(pHead.val + " ");}//用栈结构打印链表(逆序打印链表)public void display4() {Stack stack = new Stack<>();ListNode cur = head;while (cur != null) {stack.push(cur);cur = cur.next;}//遍历栈while (!stack.isEmpty()) {ListNode top = stack.pop();System.out.print(top.val + " ");}System.out.println();}//遍历打印链表public void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();} 3. 栈的oj题练习（oj题中都用到了栈这种数据结构）
| 1. 括号匹配 力扣 | 思路：用栈这种数据结构即可解决问题：遇到的左括号就入栈，如果遇到右括号就获取栈顶元素进行匹配，能够匹配就出栈。 最后看栈是否为空，如果站空，则括号就是匹配的。 |
| 2. 逆波兰表达式求值 力扣 | 思路：遇到操作数就入栈，遇到运算符就出栈两个操作数(注：先出右操作数，再出左边操作数) ，进行运算，之后把运算结果入栈，然后重复上述操作，最后栈中的元素就是表达式的结果。 |
| 3. 出栈入栈次序匹配 栈的压入、弹出序列_牛客题霸 | 思路：先入栈压入序列，在压入序列入栈的过程中，判断出栈序列中的数据和入栈序列中的数据是否相同，如果相同就开始出栈，最后看栈是否为空，如果栈空，入栈序列和出栈序列就是相对应的。 |
| 4. 最小栈 力扣 | 思路：用两个栈，其中一个放入的元素是入栈的序列，另一个栈维护最小值，当minStack空时，先入栈第一个元素，之后和入栈序列中的元素进行比较，如果minStack中的栈顶元素比当前入栈元素大，此时就更新minStack中的最小值。 |
四、栈，虚拟机栈，栈帧的区别
| 栈 | 是一种数据结构，在Java标准库中有对应的实现 --> Stack类，而Stack类是继承于Vector的，和Vector的区别：Stack不是线程安全的，而Vector是线程安全的。 |
| 虚拟机栈 | 是一块有特殊作用的内存空间，jvm为了对数据更好的管理，将内存按照不同的需求划分出的一种结构。 栈区：包含方法调用的相关信息，最主要的就是栈帧，其中栈帧是按照栈这种数据结构实现的。 |
| 栈帧 | 当new一个对象或赋值内置类型时，jvm就会在栈区中开辟一块空间，这块空间就是在栈区中，栈帧也是一种结构，包含局部变量表，操作数....每个方法在运行时，jvm都会创建一个栈帧，然后将栈帧入栈到虚拟机栈中执行方法体，当方法调用结束时，该方法对应的栈帧就会从虚拟机中出栈。 |
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！