数据结构-栈和队列刷题集(长期更新)

1. 万能计算器的实现以及源码分析

/**
 * 我们尝试写一个完整版的计算器,由于计算机不能很好的识别括号,所以一般要转换为逆波兰表达式求解
 * 思路解析 :
 * 1. 输入一个 中缀表达式
 * 2. 中缀表达式转化为list存储
 * 3. 把list转换为一个逆波兰表达式
 *      规则如下 首先准备两个栈,stack1 , list2(stack2)
 *      如果是数字直接装入 list2
 *      如果是括号 分为左括号跟右括号
 *         如果是左括号直接进入stack1
 *         如果是右括号 stack1 弹栈 ,弹出的元素进入stack2,直到出现 ')' ,抵消掉一个右括号
 *      如果是操作符
 *          如果stack1 为空 或者是 栈顶为左括号,那么直接入栈          <---------------------------
 *          如果操作符的优先级大于 栈顶 操作符的优先级,直接入栈                                    *
 *          如果操作符的优先级小于等于 栈顶操作符 ,那么就弹出栈顶元素入stack2,然后进入第一条比较 --------
 *
 * 4. 利用逆波兰表达式进行求值
 */
class MyCalculator{
    public static void main(String[] args) {
        String s = "1+ ((2 +3) *4 )-5";
        List<String> infixexperssion = toList(s);
        List<String> suffixexpression = toSuffixexpression(infixexperssion);
        int ret = calculate(suffixexpression);
        System.out.println(ret);
    }

    /**
     * 该方法的作用就是把一个字符串转换为一个中缀表达式的list
     * @param infixexpression : 中缀表达式
     * @return
     */
    public static List<String> toList(String infixexpression){
        List<String> ret = new ArrayList<>();
        int count = 0;
        while(count < infixexpression.length()){
            if(infixexpression.charAt(count) == ' '){
                count++;
                continue;
            }
            if(infixexpression.charAt(count) < '0' || infixexpression.charAt(count) > '9'
                    && infixexpression.charAt(count)!=' '){
                ret.add(infixexpression.charAt(count) + "");
                count++;
            }else{
                StringBuilder stringBuilder = new StringBuilder();
                while(count < infixexpression.length() && infixexpression.charAt(count)>='0'
                        && infixexpression.charAt(count)<='9'){
                    stringBuilder.append(infixexpression.charAt(count));
                    count++;
                }
                ret.add(stringBuilder.toString());
            }
        }
        return ret;
    }


    /**
     * 该方法的作用是将我们的中缀表达式转化为逆波兰表达式
     * @param infixexpression : 传入的中缀表达式
     * @return
     */
    public static List<String> toSuffixexpression(List<String> infixexpression){
        //首先创建两个栈,因为第二个栈不涉及弹栈操作,所以我们可以创建为顺序表
        Stack<String> stack = new Stack<>();
        List<String> list = new ArrayList<>();

        for(String elem : infixexpression){
            if(elem.equals("(")){
                stack.push(elem);
            }else if(elem.equals(")")){
                while(stack.size() != 0 && !stack.peek().equals("(")){
                    list.add(stack.pop());
                }
                stack.pop();
            }else if(isOperator(elem) ){
                if(stack.size() == 0 || stack.peek().equals("(") || priority(elem) > priority(stack.peek())){
                    stack.push(elem);
                    continue;
                }
                while(stack.size() != 0 && priority(elem) <= priority(stack.peek()) && !stack.peek().equals("(")){
                    list.add(stack.pop());
                }
                stack.push(elem);
            }else{
                list.add(elem);
            }
        }
        while(stack.size() != 0){
            list.add(stack.pop());
        }
        return list;
    }

    //判断是否是操作符
    public static boolean isOperator(String elem){
        if(elem.equals("+")||elem.equals("-")||elem.equals("*")||elem.equals("/")){
            return true;
        }
        return false;
    }

    //判断优先级的大小
    public static int priority(String elem){
        if(elem.equals("+") || elem.equals("-")){
            return 1;
        }else{
            return 2;
        }
    }

    /**
     * 最后收一下尾巴,用我们所得到的逆波兰表达式求出值
     * 求值的基本思路应该比较好理解
     * 如果是数字直接入栈,如果不是,弹出两个数字,然后进行运算结果入栈
     */
    public static int calculate(List<String> sufferixexperssion){
        Stack<String> stack = new Stack<>();
        for(String elem : sufferixexperssion){
            if(isOperator(elem)){
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                switch (elem){
                    case "+" :
                        stack.push((num1+num2)+"");
                        break;
                    case "-" :
                        stack.push((num1-num2)+"");
                        break;
                    case "*" :
                        stack.push((num1*num2)+"");
                        break;
                    case "/" :
                        stack.push((num1/num2)+"");
                        break;
                }
            }else{
                stack.push(elem);
            }
        }
        return Integer.parseInt(stack.pop());
    }
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

2. leetcode 150 逆波兰表达式求值

逆波兰表达式又叫做后缀表达式,因为计算机是好辨认出中缀表达式的计算顺序的,所以有时候要用后缀表达式进行求解
题目描述

思路分析:
1.如果是数字,直接入栈
2.如果是操作符,弹出两个数字分别作为右操作数跟左操作数运算,结果入栈
3.最后弹出栈内的最后一个元素
代码实现如下

	public static int evalRPN(String[] tokens) {
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < tokens.length; ++i) {
            String s = tokens[i];
            if (toolOperator(s)) {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                switch (s) {
                    case "+":
                        stack.push((num2 + num1) + "");
                        break;
                    case "-":
                        stack.push((num2 - num1) + "");
                        break;
                    case "*":
                        stack.push((num2 * num1) + "");
                        break;
                    case "/":
                        stack.push((num2 / num1) + "");
                        break;
                }
            } else {
                stack.push(s);
            }
        }
        return Integer.parseInt(stack.pop());
    }

    //判断是不是操作符
    public static boolean toolOperator(String s) {
        if (s.equals("+") || s.equals("-") || s.equals("*") || s.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

3.牛客 JZ31 栈的压入弹出序列

题目描述如下

思路分析

1. 首先创建一个栈用来保存我们的压入的数字
2. 创建两个指针分别指向两个数组的初始位置( i , j )
3. 遍历我们的pushV数组,压入进栈,在压入之后判断我们的popV[j]是不是与pushV[i]一致
   如果一致就弹栈, j++ , 如果不是继续压栈判断重复,最后看一看栈是否为空

代码实现如下

 /**
     * 栈的应用,正确的出栈顺序,给两个数组,一个是入栈的顺序的数组,一个是出栈的顺序的数组,请你判断该出栈序列是否是合理的
     * @param pushV : 入栈序列
     * @param  popV : 出栈序列
     * @return
     */
    public static boolean trueOrderPop(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(!stack.empty() && stack.peek() == popV[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4. leetcode 155 最小栈

思路分析
如果仅仅利用一个栈就想让查询复杂度达到O(1)级别是做不到的,所以我们需要引入另外一个栈,所以本题的基本思路就是,存在两个栈,一个普通栈,一个最小栈来保存最小值
本题的坑点就是由于我们的Integer是引用数据类型,进行比较的时候要用equals方法来进行比较,如果比较的双方有一方是基本数据类型,那就会进行基本的拆箱工作,就不用使用equals方法了
还有就是我们入栈的时候如果是与minStack栈顶相等的时候要一起入栈,stack与minstack栈顶元素一致的时候要一起出栈
代码实现如下

/**
 * 栈的应用 : 实现一个最小栈
 */
class MinStack {

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();
    
    public MinStack() {

    }

    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
            return;
        }
        if(minStack.peek() >= val){
            minStack.push(val);
        }   
    }

    
    public void pop() {
        if(minStack.peek().equals(stack.peek())){
            minStack.pop();
            stack.pop();
        }else{
            stack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

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

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
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
41
42
43
44
45
46
47
48
49
50