栈的应用场景（高频面试题）

概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈
顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。

类似于子弹装在弹夹里，先压进去的，总是最后出来，栈也是这样，遵从先进后出的原则。

目录

概念

1.改变元素的序列

2. 将递归转化为循环

3. 括号匹配 

4. 逆波兰表达式求值

题目描述

5. 出栈入栈次序匹配

题目描述

---

 

1.改变元素的序列

这是一道选择题，需要注意的是题目为进栈的过程可以出栈。

A选项为1,4,3,2，第一个出的为1，我们要把1先入栈然后在出栈，第二个为4，我们要把2,3,4依次入栈，然后依次出栈，从顶部出，正好为4,3,2,。因此A满足。

B选项为2,3,4,1，第一个出的为2，我们要把1,2依次入栈，然后才能出一个2，此时栈内还有一个1，第二个出的为3，我们要把3入栈再出栈，第三个为4，把4入栈再出栈1最后把1出栈。因此B满足。

C选项为3,1,4,2，第一个出的为3，我们就要把1,2,3，依次入栈，然后出一个3，第二个出的为1，但此时在栈顶的为2，且1比2先入栈，所以1不能先出栈。因此C不满足，此题选C。

D选项为3,4,2,1，第一个出的为3，我们把1,2,3依次入栈，然后出一个3，此时1,2还在栈中，第二个出的为4，我们把4入栈在出栈，接着为2,1我们把栈内的1,2从栈顶出栈就能得到。因此D满足。

---

 这道题需要注意的是，他是依次入栈，再依次出栈。

依次入栈，再从栈顶依次出栈，顺序则为EDCBA54321，此题选B。

---

2. 将递归转化为循环

比如：逆序打印链表

//递归方式
    public void printList(ListNode head){
        if(head.next!=null){
            printList(head.next);
        }
        System.out.print(head.val+" ");
    }

递归方式很简单，条件为head.next不为空，就递归到head.next，直到走到最后一个开始打印，然后往回打印。

public void pintList(ListNode head){
        ListNode cur=head;
        Stack<ListNode> stack=new Stack<>();
        //依次入栈
        while(cur!=null){
            stack.push(cur);
            cur=cur.next;
        }
        //出栈且打印
        while (!stack.empty()){
            System.out.print(stack.pop().val+" ");
        }
    }

如果用栈来解决，首先将链表都遍历一遍，全部依次入栈，最后一个元素正好在栈顶，然后在依次出栈并打印即可，这样就将递归改做了循环，用栈来实现。

运行结果

---

3. 括号匹配
 

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

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.empty()){
                   return false;
               }
               if(ch==')'&&stack.peek()=='('||ch==']'&&stack.peek()=='['
                        ||ch=='}'&&stack.peek()=='{'){
                    stack.pop();
                }
                else{
                    return false;
                }
            }
        }
        if(stack.empty()){
            return true;
        }
        return false;
    }

  

有了以上的分析结果，我们首先定义栈，遍历字符串拿到的是字符，所以类型应该定义为Character。接着我们便利字符串，进入循环，我们定义ch用来接收取到的字符，用charAt（）转换为字符，接着判断是否为左括号（‘（’ ‘[’ '{'）,如果是，直接入栈，不是我们再进行那四种结果的判断，如果此时栈空了，则说明右括号多了，如果此时左右括号匹配我们就出栈，如果不匹配，栈也没空就说明左右括号不匹配。走完循环说明字符串已经便利完成，且之前的都匹配成功，我们在判断栈是否为空，如果为空，说明此时正好都匹配成功，如果不为空就说明左括号多了。

---

4. 逆波兰表达式求值

逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J・卢卡西维兹(J・ Lukasiewicz)于1929年首先提出的一种表达式的表示方法 。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面。

题目描述

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

public int evalRPN(String[] tokens) {
        Stack <Integer>stack=new Stack<>();
        for (String x:tokens){
            if(!isSymbol(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.peek();
        
    }
    private boolean isSymbol(String x){
        if(x.equals("+")||x.equals("-")||x.equals("*")||x.equals("/")){
            return true;
        }
        return false;
    }

根据分析结果 ，我们首先定义栈，由于是数字运算，只有数字入栈，我们将栈定义为Integer类型，接着我们用for each来遍历字符串数组，进入循环，我们要判断此时的x为数字还是运算符，这里我写了一个private修饰的方法来判断。判断后，如果是数字我们就将它入栈，如果不是数字就是运算符，我们应该switch语句进行匹配，匹配到哪个运算符就执行哪个运算符的操作。将运算结果在入栈，循环走完，说明数组遍历完成，最后栈中的数据就为最终中缀表达式的计算结果。

注意：

1. 判断是否为运算符时要用equals（）方法。
2. 入栈时要用Integer.parseInt(x)将字符串转为整形。
3. 最终结果就为栈中最后的数据。

---

5. 出栈入栈次序匹配

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

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]){
                stack.pop();
                j++;
            }
        }
        if(stack.empty()){
            return true;
        }
        return false;
    }

 

思路，有了我们先遍历pushA数组将其中数据依次入栈，入栈一个，进入循环，再对栈顶的值与popA[]中的元素比较，如果等于就出栈一个。j从0开始，由于可能会连续匹配到，连续出栈，所以得用循环，如果前一个匹配到了，才能对popA中下一个值进行匹配。因此循环条件应该为:  
j<popA.length&&!stack.empty()&&stack.peek()==popA[j]

首先数组不能越界，还有栈中也不能为空，接着就要与栈顶值进行比较，匹配了出栈顶值，j++。
最后两个循环走完看栈是否空，如果空，说明都匹配到了，如果不为空，说明还有未匹配到的说明次序不对。