【数据结构】栈（Stack）的应用场景

02-29 1146阅读

文章目录

🌏前言
🍀改变元素的序列
- 🚩场景一
- - 📌解析：
  - 🚩场景二
  - - 📌解析：
    - 🎍将递归转化为循环
    - 🌳[括号匹配](https://leetcode.cn/problems/valid-parentheses/)
    - - 🚩题目描述：
      - 🚩示例：
      - 🚩思路解析：
      - 🚩代码实现：
      - 🎄[逆波兰表达式求值](https://leetcode.cn/problems/evaluate-reverse-polish-notation/)
      - 🐱‍👤拓展逆波兰式
        🐱‍👓什么叫做逆波兰表达式
        🐱‍🐉逆波兰表达式算法步骤
        🚩题目描述
        🚩示例：
        🚩解法思路
        🌴[出栈入栈次序匹配](https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking)
        🚩题目描述：
        🚩示例
        🚩解法思路：
        🚩代码实现：
        🌲[最小栈](https://leetcode.cn/problems/min-stack/description/)
        🚩题目描述：
        🚩示例：
        🚩思路解析：
        📌将元素val推入堆栈
        📌删除堆栈顶部的元素
        📌获取堆栈顶部的元素
        📌获取堆栈中的最小元素
        🚩完整代码：
        ⭕总结
        🌏前言
        
        栈（Stack）又名堆栈，作为一个== 先进后出== 的数据结构。
        
        它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
        
        🍀改变元素的序列
        
        🚩场景一
        
        若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（C）
        A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1
        📌解析：
        
        A选项进出入栈顺序：
        push(1)->push(2)->push(3)->push(4)->pop(4)->pop(3)->pop(2);
        B选型的出入栈顺序：
        push(1)->push(2)->pop(2)->push(3)->pop(3)->push(4)->pop(4)->pop(1);
        C选项出入栈顺序：
        push(1)->push(2)->push(3)->pop(3)------->？pop(1)
        这时候我们的我们的栈内元素为：
        所以C选项错误
        D选项出入栈顺序：
        pusn(1)->push(2)->push(3)->pop(3)->push(4)->pop(4)->pop(2)->pop(1);
        🚩场景二
        
        一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ B ）。
        A: 12345ABCDE B: EDCBA54321
        C: ABCDE12345 D: 54321EDCBA
        📌解析：
        
        依次入栈后，栈内元素为：
        所以答案为B；
        
        🎍将递归转化为循环
        
        比如：逆序打印链表
        
        在我们没有学习栈以前，我们可能会使用递归的方法进行打印，如下所示：
        
        // 递归方式 void printList(Node head){ if(null != head){ printList1(head.next); System.out.print(head.val + " "); } } // 循环方式 void printList1(Node head) { if (null == head) { return; } }
        
        其实我们发现逆序打印链表的本质不就是：排在前面的后打印，排在后面的先打印
        
        这不就是栈先进后出的思想吗
        
        所以我们可以先让链表的每一个依次进栈，再出栈即可，实现如下：
        
        Stack s = new Stack(); // 将链表中的结点保存在栈中 Node cur = head; while(null != cur){ s.push(cur); cur = cur.next; } // 将栈中的元素出栈 while(!s.empty()){ System.out.print(s.pop().val + " "); }
        
        🌳括号匹配
        
        🚩题目描述：
        
        给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
        
        有效字符串需满足：
        
        左括号必须用相同类型的右括号闭合。
        左括号必须以正确的顺序闭合。
        每个右括号都有一个对应的相同类型的左括号。
        class Solution { public boolean isValid(String s) { } }
        
        🚩示例：
        
        🚩思路解析：
        
        我们利用栈的方法进行解决：
        
        如果是左括号，就让他进栈
        如果是右括号，就让它与栈顶元素进行比较
        如果栈顶元素与该右括号构成一对，则让栈顶元素出栈
        若不是一对，则返回false；
        特殊情况考虑：
        
        右括号进来时栈为空，此时直接返回false就好
        左括号太多，遍历完后，栈内还有元素，这时候需要进行为空的判断
        若为空，返回true；反之则为false；
        🚩代码实现：
        
        class Solution { public boolean isValid(String s) { Stack characterStack = new Stack(); for(int i = 0;i
        🎄逆波兰表达式求值
        
        🐱‍👤拓展逆波兰式
        
        🐱‍👓什么叫做逆波兰表达式
        
        逻辑提问式类似于算术表达式，对于检索而言，这种表达式并不是最优和最简洁的形式，需要进行必要的转换。
        
        1929年波兰的逻辑学家卢卡西维兹(Jan Lucasiewicz)提出了将运算符放在运算项后面的逻辑表达式，又称“逆波兰表达式”。
        
        采用这种表达式组织逻辑提问式非常方便检索运算，是日本的福岛先生最早将逆波兰表达式应用于情报检索的，故又称为“福岛方法”。 [2]
        
        逆波兰表达式又叫做后缀表达式，是一种没有括号，并严格遵循“从左到右”运算的后缀式表达方法，如下表所示：
        
        🐱‍🐉逆波兰表达式算法步骤
        
        首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。
        
        读入一个用中缀表示的简单算术表达式，为方便起见，设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。
        
        从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。
        
        如果不是数字，该字符则是运算符，此时需比较优先关系。具体做法是：将该字符与运算符栈顶的运算符的优先关系相比较。如果该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。若不是的话，则将栈顶的运算符从栈中弹出，直到栈项运算符的优先级低于当前运算符，将该字符入栈。
        
        重复步骤1～2，直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。
        
        🚩题目描述
        
        给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。
        
        请你计算该表达式。返回一个表示表达式值的整数。
        
        🚨注意：
        
        有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
        每个操作数（运算对象）都可以是一个整数或者另一个表达式。
        两个整数之间的除法总是向零截断。
        表达式中不含除零运算。
        输入是一个根据逆波兰表示法表示的算术表达式。
        答案及所有中间计算结果可以用 32 位整数表示。
        class Solution { public int evalRPN(String[] tokens) { } }
        
        🚩示例：
        
        🚩解法思路
        
        如果当前字符为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。
        
        🚨注意：先出来的数为左操作数，后出来的数为右操作数
        
        代码实现如下：
        
        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; } }
        
        🌴出栈入栈次序匹配
        
        🚩题目描述：
        
        输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
        
        0 public boolean IsPopOrder(int [] pushA,int [] popA) { int n = pushA.length; //辅助栈 Stack //入栈：栈为空或者栈顶不等于出栈数组 while(j