【数据结构—栈】用四道力扣原题帮你彻底搞懂“栈”（详细）_关于栈的问题

目录

1.栈的概念及使用(Stack)

1.1概念

1.2 栈的使用

2.四道栈的相关OJ题

2.1逆波兰表达式求值

2.2括号匹配

2.3验证栈序列

2.4最小栈

---

1.栈的概念及使用(Stack)

1.1概念

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

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

出栈：栈的删除操作叫做出栈。出数据在栈顶。

栈在现实生活中的例子：

1.2 栈的使用

public static void main(String[] args) {
   Stack<Integer> s = new Stack();
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    System.out.println(s.size()); // 获取栈中有效元素个数---> 4
    System.out.println(s.peek()); // 获取栈顶元素---> 4
    s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
 if(s.empty()){
    System.out.println("栈空");
 }
 else{
    System.out.println(s.size());
  }
}

2.四道栈的相关OJ题

2.1逆波兰表达式求值

leetcode原题链接：逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

• 1 <= tokens.length <= 104
• tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

 

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中

解题思路：

逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下主要操作：

如果遇到操作数，则将操作数入栈；

如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

例如：1 3 + 4 -

按照上图过程，我们可以得出以下Java题解代码：

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {               //遍历字符数组
            String token = tokens[i];
            if (isNumber(token)) {                  //判断数组元素是否为操作数
                stack.push(Integer.parseInt(token));//是操作数则将其转为int类型
            } else {                   //如果是运算符则进行运算
                int num2 = stack.pop();//先弹出一个操作数作为右操作数
                int num1 = stack.pop();//后弹出一个操作数作为左操作数
                switch (token) {       //将运算符与两个操作数进行运算
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();  //弹出栈中最后也是唯一一个数，即为答案
    }
 
    public boolean isNumber(String token) { //判断是否为操作数
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));              
    }
}

2.2括号匹配

leetcode原题链接：括号匹配

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

解题思路：

我们可以遍历字符串，遇到左括号就入栈，遇到右括号就与栈顶元素匹配（判断），看是否匹配，如果不匹配则不是有效括号，匹配则弹出栈顶元素（此时消除一对括号）

注意“ )) ”这个用例，我们遇到右括号需要判断栈是否为空，如果栈已经为空，此时字符串是右括号也不是有效括号。

因此，我们只需要解决三种情况：

①不匹配 ②左括号多③右括号多

那什么时候才算匹配呢？

当栈当中的元素为空并且字符串也遍历完成的时候

（  i 指的是遍历字符数组时的指向下标）

而考虑到字符串匹配是一对一对的，符号数肯定是偶数，所以我们可以得出以下Java题解代码：

class Solution {
   
    public boolean isValid(String s) {
   if (s.length() % 2 != 0) {return false;}//字符串匹配是一对一对的，如果是奇数则证明有多余符号
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '{' || c == '(' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {return false;}
                if ((c == '}' && stack.peek() == '{')
                        || (c == ')' && stack.peek() == '(')
                        || (c == ']' && stack.peek() == '[')) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();//数组遍历结束后，如果栈中还有多余符号，则匹配失败
 
    }
}

2.3验证栈序列

leetcode原题链接：验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：

• 1 <= pushed.length <= 1000
• 0 <= pushed[i] <= 1000
• pushed 的所有元素互不相同
• popped.length == pushed.length
• popped 是 pushed 的一个排列

解题思路：

题目要我们判断两个序列是否符合入栈出栈的次序，我们就可以定义一个辅助栈来模拟，再采用双指针i，j来实现。对于入栈序列，只要栈为空，序列肯定要依次入栈。那什么时候出来呢？自然是遇到一个元素等于当前的出栈序列的元素，那我们就放弃入栈，让它先出来。

1.因为弹出序列是要依据压入序列来判断的，所以首先要遍历压入序列数组；
2.在遍历压入数组时，每次都需要判断当前数值是否是弹出，即比较pushA[i] == popA[j]，相同即弹出，不同则将数据压入栈；
3.不断比较，遍历完成后，判断数据是否全部出栈。如果能按照这个次序将两个序列都访问完，那说明是可以匹配入栈出栈次序的。

Java题解代码：

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int n = pushed.length;
        //辅助栈
        Stack<Integer> s = new Stack<>();
        //遍历入栈的下标
        int j = 0;
        //遍历出栈的数组
        for(int i = 0; i < n; i++){
            //入栈：栈为空或者栈顶不等于出栈数组
            while(j < n && (s.isEmpty() || s.peek() != popped[i])){
                s.push(pushed[j]);
                j++;
            }
            //栈顶等于出栈数组
            if(s.peek() == popped[i])
                s.pop();
            //不匹配序列
            else
                return false;
        }
        return true;
    }
 
}

2.4最小栈

leetcode原题链接：最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

• -231 <= val <= 231 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 104 次

解题思路：

假设一个辅助栈 minStack，用来存stack中的最小值

入栈（push）过程：

出栈（pop）过程：

Java题解代码：

class MinStack {
 
    private  Stack<Integer> stack;
    private  Stack<Integer> minStack;
    public MinStack() {
 
        stack=new Stack<>();
        minStack =new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }else{
            int peekVal=minStack.peek();
            //-1<3
            if(val<= peekVal){
                minStack.push(val);
            }
        }
    }
    
    public void pop() {
        int val= stack.pop();
        if(!minStack.empty()){
            if (val==minStack.peek()){
                minStack.pop();
            }
        }
 
    }
 
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
    if(!minStack.empty()){
        return minStack.peek();
    }
        return -1;
    }
}