数据结构——栈

一、栈的概念

栈：是一种线性结构，只能在固定的一端进行插入和删除操作。进行插入和删除操作的一端叫栈顶，另外一端叫栈底。遵循先进后出的原则。
栈就像一个杯子，杯口（栈顶），杯底（栈底），先放进的葡萄，后吃到，后放入的葡萄，先吃到。
在这里插入图片描述

二、栈的使用

E 这里是泛型。
在这里插入图片描述

三、栈的模拟实现

在这里插入图片描述

import java.util.Arrays;public class MyStack {private int[] elem;//栈有用的大小private int usedSize;public MyStack() {this.elem = new int[10];}public int size() {return this.usedSize;}//弹出栈顶元素public int pop() {if(isEmpty()) {throw new StackEmptyException("栈空，不能出栈！");}int val = elem[usedSize-1];usedSize--;return val;}//入栈public void push(int val) {if(isFull()) {this.elem = Arrays.copyOf(this.elem,this.elem.length*2);}elem[usedSize++]=val;}private Boolean isFull () {return usedSize == this.elem.length;}//取出栈顶元素public int peek() {if (isEmpty()) {throw new StackEmptyException("栈空，不能取栈顶元素！");}return elem[usedSize-1];}public boolean isEmpty() {return usedSize == 0;}}

public class StackEmptyException extends RuntimeException{public StackEmptyException() {}public StackEmptyException(String message) {super(message);}
}

public class Test {public static void main(String[] args) {MyStack myStack = new MyStack();//依次入栈myStack.push(1);myStack.push(2);myStack.push(3);myStack.push(4);myStack.push(5);//栈有用的大小为5System.out.println(myStack.size());//依次弹栈System.out.println(myStack.pop());//5System.out.println(myStack.pop());//4System.out.println(myStack.pop());//3System.out.println(myStack.pop());//2System.out.println(myStack.pop());//1System.out.println(myStack.pop());//Exception in thread "main" StackEmptyException: 栈空，不能出栈！}}

四、栈的相关题目

若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A: 1,4,3,2
B: 2,3,4,1
C: 3,1,4,2
D: 3,4,2,1
一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（）。
A: 12345ABCDE
B: EDCBA54321
C: ABCDE12345
D: 54321EDCBA

1.C
2.B

3.括号匹配
遇到左边的括号就放入栈中，否则遇到右边的括号就出栈与其进行匹配。

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);if(ch =='(' || ch =='[' || ch =='{' ) {stack.push(ch);}else {if(stack.isEmpty()){return false;}if ( (stack.peek()=='(' && ch==')') || (stack.peek()=='[' && ch==']') || (stack.peek()=='{' && ch=='}')  ) {stack.pop();}else {return false;}}}if(stack.isEmpty()){return true;}return false;}
}

4.逆波兰表达式
在这里插入图片描述

class Solution {public int evalRPN(String[] s) {Stack<Integer> stack = new Stack<>();for(int i=0;i<s.length;i++) {if(Character.isDigit(s[i].charAt(0))) {stack.push(Integer.parseInt(s[i]));}else{int b = stack.pop();int a = stack.pop();switch (s[i]) {case "+":stack.push(a+b);break;case "-":stack.push(a-b);break;case "*":stack.push(a*b);break;case "/":stack.push(a/b);break;}}}return stack.pop();}
}

5.最小栈（需要用到2个栈）
一个栈a存放入栈的数据，另一个栈存b放a栈当前最小的数据。
在这里插入图片描述

class MinStack {public Stack<Integer> stack ;public Stack<Integer> minstack ;public MinStack() {stack = new Stack<>();minstack = new Stack<>();}public void push(int val) {stack.push(val);if (minstack.isEmpty()) {minstack.push(val);}else {if(val<=minstack.peek()) {minstack.push(val);}}}public void pop() {if(stack.isEmpty()) {return;}if(stack.peek().equals(minstack.peek())) {minstack.pop();}stack.pop();}public int top() {if(stack.isEmpty()) {return -1;}return stack.peek();}public int getMin() {if (stack.isEmpty()) {return -1;}return minstack.peek();}
}

6.栈的压入，弹出序列
在这里插入图片描述

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param pushV int整型一维数组* @param popV int整型一维数组* @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {// write code here// write code hereStack<Integer> stack = new Stack<>();int j=0;for (int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);while(stack.empty()!=true&& j<popV.length && stack.peek()==popV[j]) {stack.pop();j++;}}return stack.empty();}
}

五、栈、虚拟机栈、栈帧有什么区别呢？

栈: 只能在表的一端进行插入和删除运算的线性表，是一种数据结构。
虚拟机栈: Java虚拟机中用于存储方法所执行的变量和结果。
栈帧: 是在函数执行时的内存结构。