✨前言✨
之前已经学习过了栈的相关知识点，本次主要总结一下常见的栈的应用实例
1 出栈与入栈顺序问题：
1.1 选择题
一个栈的入栈顺序是A，B，C，D，E，则出栈顺序不可能的是?( )
A EDCBA
B DECBA
C DCEAB
D ABCDE
题目中隐含的条件就是出栈的同时也是可以进栈的
分析：
对于A选项而言就是不出栈，等A,B,C,D,E依次进栈之后依次出栈，所以是符合栈的后进先出特性的，对于B选项而言，等A,B,C,D进栈之后，在对D进行出栈，然后在将E进栈，然后再把E出栈，最后将C,B,A依次出栈，因此B选项也是正确的，对于C选项与B选项对于，很明显A是不能先于B出栈的，所以C选项是不符合的，D选项就是在进栈的同时进行出栈的操作，所以D选项也是符合要求的。
正确答案: C
1.2 编程题
代码题：OJ链接
public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { Stack<Integer> stack = new Stack<>();//创建一个栈 int j = 0;//遍历第二个数组 for(int i = 0;i<pushA.length;i++){//遍历第一个数组 stack.push(pushA[i]);//将第一个数组依次入栈 while(j<popA.length&&!stack.empty()&&stack.peek()==popA[j]){//当J下标元素与栈顶元素比较，是否相等，此时j必须是要有意义的，并且此时栈要不为空，才进行出栈操作 stack.pop(); j++; } } return stack.empty();//如果符合栈的特性，那么最后一定会是一个空栈。否则就是不符合栈的特性的 } }
2 中缀表达式转后缀表达式
2.1 填空题:
将（5+4）*3-2（中缀表达式也被称做为逆波兰式）转化为后缀表达式的结果为：
（1）按先加减后乘除的原则给表达式加括号
（2）在将符合移到对应的括号之后，就可以得到对应的后缀表达式
54+3*2-
2.2 编程题
逆波兰表达式求值：OJ链接
class Solution { public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for(int i = 0;i<tokens.length;i++){ String ch = tokens[i]; if(!INT(ch)){ //为整数值进栈 stack.push(Integer.parseInt(ch));//将字符串转化为整数放入栈中 }else{ //如果为运算符 int num1 = stack.pop(); int num2 = stack.pop(); int num=0; switch(ch){ case "+": num=num2+num1; break; case"-": num=num2-num1; break; case"*": num=num2*num1; break; case"/": num=num2/num1; break; } stack.push(num); } } return kohaostack.peek(); } public boolean INT(String val){ //判断是否为符号 if(val.equals("+")||val.equals("-")||val.equals("*")||val.equals("/")){ return true; } return false; } }
3 括号匹配问题：
对于栈中，括号匹配问题是一个挺重要的一个笔试的考点，具体题目分析如下：
4 最小栈的问题
最小栈：OJ链接
class MinStack { Stack<Integer> stack; Stack<Integer> minStack; public MinStack() { stack=new Stack<>(); minStack=new Stack<>(); } public void push(int val) { if(minStack.empty()){ stack.push(val); minStack.push(val); return; } if(minStack.peek()>=val){ stack.push(val); minStack.push(val); }else{ stack.push(val); } } public void pop() { if(stack.peek()>minStack.peek()){ stack.pop(); }else{ stack.pop(); minStack.pop(); } } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }
