学习目录

• 栈(Stack)
• • • 栈的概念
    • 栈的使用
    • 栈相关的应用场景
    • 栈的模拟实现
    • 中缀表达式 转 后缀表达式

栈(Stack)

栈的概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作.
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，遵守先进后出，后进先出的原则

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

在集合框架中，Stack的继承实现关系如下：
从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表
不同的是Vector类，是线程安全的动态数组，但是性能较差 , 现在已经不是很常用了 , 可以说已经过时了

栈的使用

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);int x = stack.pop();//取出栈顶的元素返回System.out.println(x);System.out.println("当前元素有:"+ stack.size());int n = stack.peek();//获取当前栈顶的元素System.out.println(n);if(stack.empty()){System.out.println("空栈！");}else{System.out.println("当前栈空间为："+stack.size());}}

栈相关的应用场景

1. . 改变元素的序列

若进栈序列为 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：1、2、3、4、5、A、B、C、D、E
B： E、D、C、B、A、5、4、3、2、1
C： A、B、C、D、E、1、2、3、4、5
D： 5、4、3、2、1、E、D、C、B、A

图解：

栈的模拟实现

public class MyStack {public int[] elen;public int usedsize;public MyStack() {this.elen = new int[10];}//压栈public int push(int val){if(isFull()){// 扩容elen = Arrays.copyOf(elen,2*elen.length);}this.elen[usedsize] = val;usedsize++;return val;}// 判断数组的空间是否满了public boolean isFull(){return usedsize == elen.length;}// 弹出public int pop(){if(empty()){throw new MyEmptyStackException("栈为空！");}int n = elen[usedsize-1];usedsize--;return n;// 第二种方法  这种方法和上面比较简洁一点// return elen[--usedsize];}// 判断数组是否为空public boolean empty(){return usedsize == 0;}// 获取栈顶元素public int peet(){if(empty()){throw new MyEmptyStackException("栈为空！");}return elen[usedsize-1];}
}

中缀表达式 转 后缀表达式

• 基本概念
  中缀表达式：
  操作符以中缀形式位于运算数中间，日常通用的算术和逻辑公式表示方法，(例如：1+2 、 3*4)
  后缀表达式：
  又称逆波兰式，操作符以后缀形式位于两个运算数后，(例如：1+2 在转换成后缀表达形式就是1 2 +)
  前缀表达式：
  又称波兰式，操作符以前缀形式位于两个运算数前（如：3+2的前缀表达形式就是+ 3 2）

例如：

中缀转后缀表达式通常是应用在计算器上
👀👀👀
例如：

力扣链接: 逆波兰表达式求值

将后缀表达式：1 2 3 * + 4 5 * 6 + 7 * + 进行计算，求结果？

public int evalRPN(String[] tokens) {Stack stack = new Stack<>();//1.遍利 tokens 数组，判断当中的字符串的类型for(String x : tokens){//如果不是运算符的情况下if(!isOperations(x)){// Integer.parseInt() 是把字符串转换成整数stack.push(Integer.parseInt(x));// 压栈}else{int n2 = stack.pop();int n1 = stack.pop();switch(x) {case "+":stack.push(n1+n2);break;case "-":stack.push(n1-n2);break;case "*":stack.push(n1*n2);break;case "/":stack.push(n1/n2);break;}}}return stack.pop();}// 判断是否是运算符public boolean isOperations(String s){if(s.equals("+") ||s.equals("-") ||s.equals("*") ||s.equals("/") ){return true;}return false;}

• 有效的括号
  力扣链接: 有效的括号

public boolean isValid(String s) {// 创建栈Stack stack = new Stack<>();// 遍历for(int i = 0;i// 获取元素赋值给  chchar ch = s.charAt(i);// 1.判断是否是 左括号if(ch == '(' || ch == '[' || ch == '{'){stack.push(ch);// 压栈}else{// 2.遇到了右括号，但是栈为空，不匹配if(stack.empty()){//判断栈是否为空return false;}// 获取char ch2 = stack.peek();// 3.如果满足下面任何的条件逻辑，都是匹配的if(ch2 == '(' && ch == ')' || ch2 == '{' && ch == '}'|| ch2 == '[' && ch == ']'){stack.pop();}else{return false;}}}// 4. 遍历完成后，如果最后栈不为空，说明左括号还在栈中没有匹配if(!stack.empty()){return false;}return true;}