栈的OJ题（逆波兰表达式求值+括号匹配+出入栈顺序匹配+最小栈）

---

栈的练习题

---

一、 逆波兰表达式求值

• 平时使用是算式是中缀表达式
• 逆波兰表达式是一种后缀表达式，算符写在后面。

优点：
1.去掉括号后表达式无歧义
2.适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
3.中缀转后缀：加上括号，将对应的运算符放在括号外

1.题目

2.思路

• 通过栈来实现，遍历数组，如果取得是运算符，从栈顶取两个元素参与运算，
• 如果不是运算符，就将元素压栈

3.解题步骤

• 1.new一个Integer类型的栈
• 2.遍历字符串数组，
• 3.写一个方法判断当前取的字符串是不是运算符
• 4.如果不是运算符，进行压栈
• 5.如果是运算符，就取出栈顶的两个元素，
• 6.根据运算符的类型，在 switch语句中运算，将结果压栈
• 7.最后栈中只有一个最终结果，取出并返回

4. 代码

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String x : tokens) {//遍历字符串数字
            if (!isOperation(x)) {//判断当前字符串是不是运算法
                stack.push(Integer.parseInt(x));//如果不是运算符，将字符串转化为Integer类型并压栈
            } 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
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

二、括号匹配

1.题目

2.思路

1.左括号压栈，遇到匹配的右括号，对应的左括号出栈
2.如果左括号多，遍历完后，栈不为空，不匹配
3.如果右括号多，字符串遍历不完，栈就空了，不匹配
4.遍历完字符串，且栈是空的，说明符合条件

3.解题步骤

• 1.遍历字符串依次取出字符
• 2.如果是左括号，压栈，栈里面存的都是左括号
• 3.否则就是右括号，如果栈此时为空，证明右括号超出
• 4.栈不为空，查看栈顶元素是否与取的符号相匹配，如果匹配，出栈，不匹配返回false
• 5.最后直接返回栈是否为空的判断，栈为空说明所有括号都匹配成功，不为空证明左括号超出

4. 代码

 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.isEmpty()) {//如果栈是空的
                    return false;//说明右括号多
                }
                char ch2 = stack.peek();//查看栈顶的左括号
                if (ch2 == '[' && ch == ']' || ch2 == '{' && ch == '}' || ch2 == '(' && ch == ')') {
                    stack.pop();//如果左括号和右括号匹配，存的左括号出栈
                }else {
                    return false;//不匹配
                }
            }
        }
        return stack.isEmpty();//如果栈是空的，返回true，否则返回false
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三、出入栈顺序匹配

1.题目

2.思路

遍历数组，每次循环从push数组中向栈里压进一个元素，在pop数组中进行比较
如果相等，出栈，继续压进push数组的下一个元素
最后栈为空，说明数组中的顺序相匹配

3.解题步骤

• 1.给栈中压入一个元素
• 2.查看栈顶的元素是否等于popV数组中的值
• 3.加入循环的条件：j不能越界，避免越界异常,要pop元素,栈不能是空的,避免空指针异常
• 4.如果相等，出栈，j后移
• 5.不相等，没进入循环，i向后移动，在栈中重新压入新的元素与j匹配
• 6.最后数组遍历完后，栈为空说明符合题意

4. 代码

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型一维数组
     * @param popV int整型一维数组
     * @return bool布尔型
     */
    public boolean IsPopOrder(int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);//给栈中压入一个元素
            while (j < popV.length && !stack.empty() && stack.peek().equals(popV[j])) {
                //j< popV.length j不能越界，避免越界异常
                // 要pop元素,栈不能是空的,避免空指针异常
                //查看栈顶的元素是否等于popV数组中的值
                stack.pop();//相等，出栈
                j++;//j向后移动
            }//不相等，没进入循环，i向后移动，在栈中重新压入新的元素与j匹配
        }
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

四、最小栈

1.题目

2.思路

1.用两个栈，在普通栈压进元素的时候，与最小栈的栈顶元素比较
2.如果小于最小栈的栈顶元素，将该元素压进最小栈，当做当前的最小值
3.如果栈中删除了最小的元素，最小栈同样移除，最小栈改变

3.解题步骤

• 1.push:给stack压进元素，同时判断如果最小栈为空，压进该元素，如果不为空，将该元素与最小栈的栈顶比较，小于等于的数放进最小栈
• 2.pop:在栈中取出元素时，要比较是否与最小栈的栈顶元素相等，如果相等，同时取出
• 3.top:当栈不为空的时候，返回栈顶元素
• 4.getMin：返回最小栈的栈顶元素；

4. 代码

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 {
            if (val <= minstack.peek()) {
                minstack.push(val);
            }
        }
    }

     public void pop() {
        if (!stack.empty()){
            Integer val = stack.pop();
            if (val.equals(minstack.peek())){//维护最小栈
                minstack.pop();
            }
        }
    }

    public int top() {
        if (!stack.empty()){
            return stack.peek();
        }
        return -1;
    }

    public int getMin() {
        return minstack.peek();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

五、栈、虚拟机栈、栈帧的区别

• 栈是一种数据结构
• 函数在虚拟机栈上开辟内存
• 开辟的内存叫做栈帧

点击移步博客主页，欢迎光临~