作者：爱塔居

专栏：数据结构

作者简介：大三学生，希望跟大家一起进步

目录

一、栈

1.1 概念

1.2 栈的使用

1.3 示例

二、栈的应用场景

2.1 改变元素的序列

2.2 逆波兰表达式求值

2.3 括号匹配

2.4 栈的压入、弹出序列

一、栈

1.1 概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。

1.2 栈的使用

1.3 示例

import java.util.Stack;
public class Test {public static void main(String[] args) {Stack stack=new Stack<>();stack.push(1);//压栈stack.push(2);//压栈System.out.println(stack.size());//获取栈中有效元素元素stack.pop();//出栈int b=stack.peek();//获取栈顶元素System.out.println(b);}
}

二、栈的应用场景

2.1 改变元素的序列

1.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

2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。
A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA

2.2 逆波兰表达式求值

力扣

将中缀表达式"1+((2+3)*4)-5"转换为后缀表达式为:"1 2 3+4*+5-"

步骤：

全部括号分开：((1+((2+3)*4))-5)

把符号都移到对应的括号外面：

((1((23)+4)*)+5)-

删除所有括号：123+4*+5-

思路：遍历后缀表达式，只要是数字就入栈，是字符就弹出栈顶的两个元素，参与运算，最后把运算之后的结果，再次入栈。

class Solution {public int evalRPN(String[] tokens) {Stack stack=new Stack<>();for(String x:tokens){if(!isOperation(x)){stack.push(Integer.parseInt(x));//不是运算符号，放入栈中}else{int num2=stack.pop();//如果是运算符号，把栈中两个元素出栈int num1=stack.pop();switch(x){
//判断运算符号，将出栈的两个数运算后，进栈case "+":stack.push(num1+num2);break;case "-":stack.push(num1-num2);break;case "*":stack.push(num1*num2);break;case "/":stack.push(num1/num2);break;}}}
//到最后，栈中只有一个元素，出栈return stack.pop();}
//判断是否是运算符号private boolean isOperation(String x){if(x.equals("+")||x.equals("-")||x.equals("*")||x.equals("/")){return true;}return false;}}

2.3 括号匹配

力扣

思路：

左括号多：字符串遍历完成但是栈不空；

右括号多：字符串没完，栈空了;

不匹配;

class Solution {public boolean isValid(String s) {Stack stack=new Stack<>();for(int i=0;i

import java.util.Stack;
public class Solution {public boolean IsPopOrder(int [] pushA, int [] popA) {int n=pushA.length;Stack stack=new Stack<>();int j=0;
for(int i=0;i