栈和队列及表达式求值问题

栈、队列及其常见变形、实战应用

栈(stack)

队列(queue)

双端队列(deque)

优先队列(priority queue)

一般的队列是以“时间”为顺序的(先进先出)
优先队列按照元素的“优先级”取出

“优先级”可以是自己定义的一个元素属性

许多数据结构都可以用来实现优先队列,例如二叉堆、二叉平衡树等

时间复杂度

栈、队列

• Push (入栈、入队) : 0(1)
• Pop (出栈、出队) : 0(1)
• Access (访问栈顶、访问队头) : 0(1)

双端队列

• 队头、队尾的插入、删除、访问也都是0(1)

优先队列

• 访问最值: 0(1)
• 插入:一般是0(logN), 一些高级数据结构可以做到0(1)
• 取最值: O(logN)

实战

20.有效的括号

https://leetcode.cn/problems/valid-parentheses/

• 栈与“括号序列”
• 最近相关性

class Solution {
public:
    //最近相关性,一般要想到栈
    bool isValid(string s) {
        for(char ch:s){
            if(ch=='(' || ch=='{' || ch=='[')
            {
                a.push(ch);
            }else{
                if(a.empty()) return false;
                if(ch==')' && a.top()!='(') return false;
                if(ch==']' && a.top()!='[') return false;
                if(ch=='}' && a.top()!='{') return false;
                a.pop();
            }
        }
        return a.empty();
    }

private:
    stack<char> a;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

155.最小栈

https://leetcode.cn/problems/min-stack/

• 前缀最小值

class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        s.push(val);
        if(preMin.empty()) preMin.push(val);
        else{
            preMin.push(min(val,preMin.top()));
        }
    }
    
    void pop() {
        s.pop();
        preMin.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return preMin.top();
    }
private:
    stack<int> preMin;
    stack<int> s;
};

/**
 * 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

表达式求值系列问题

150.逆波兰表达式求值

https://leetcode.cn/problems/evaluate-reverse-polish-notation/

建立一个用于存数的栈，逐一扫描后缀表达式中的元素。

• 如果遇到一个数,则把该数入栈
• 如果遇到运算符,就取出栈顶的两个数进行计算,然后把结果入栈

扫描完成后，栈中恰好剩下一个数,就是该后缀表达式的值。
时间复杂度0(n)

class Solution {
public:
    int evalRPN(vector<string>& tokens) {

        for(string& token:tokens){
            if(token== "+" || token== "-" ||token== "*" || token== "/")
            {
                int y=s.top();
                s.pop();
                int x=s.top();
                s.pop();
                s.push(cal(x,y,token));
            }else{
                s.push(atoi(token.c_str()));
            }
        }

        return s.top();
    }

    int cal(int x,int y,string token){
        if(token=="+") return x+y;
        if(token=="-") return x-y;
        if(token=="*") return x*y;
        if(token=="/") return x/y;
        return 0;
    }

private:
    stack<int> s;
};
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

class Solution {
public:
    int evalRPN(vector<string>& tokens) {

        stack<int> nums;
        for(int i=0;i<tokens.size();i++)
        {
            
            if(isNumber(tokens[i]))
            {
                int a=stoi(tokens[i]);
                nums.push(a);
            }else{
                int num2=nums.top();
                nums.pop();
                int num1=nums.top();
                nums.pop();
                switch(tokens[i][0]){
                    case '+':
                    nums.push(num1+num2);
                    break;
                    case '-':
                    nums.push(num1-num2);
                    break;
                    case '*':
                    nums.push(num1*num2);
                    break;
                    case '/':
                    nums.push(num1/num2);
                    break;
                }
            }
        }
        return nums.top();
    }
    bool isNumber(string& token) {
        return !(token == "+" || token == "-" || token == "*" || token == "/");
    }
};
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

224.基本计算器

https://leetcode.cn/problems/basic-calculator/

建立一个用于存运算符的栈,逐一扫描中缀表达式中的元素。

• 如果遇到一个数,输出该数
• 如果遇到左括号，把左括号入栈
• 如果遇到右括号,不断取出栈顶并输出,直到栈顶为左括号,然后把左括号出栈
• 如果遇到运算符，只要栈顶符号的优先级>=新符号，就不断取出栈顶并输出，最后把新符号进栈。优先级顺序为乘除号>加减号>左括号
• 思考:如何辨别运算符是加减法运算还是正负号?

依次取出并输出栈中的所有剩余符号。
最终输出的序列就是一个与原中缀表达式等价的后缀表达式，再对后缀表达式求值。
时间复杂度0(n)

class Solution {
public:
    int calculate(string s) {
        s +=" ";
        vector<string> tokens;
        string number="";
        bool needsZero = true;
        for(char ch : s){
            if(ch>='0' && ch<='9'){
                number+=ch;
                needsZero = false;
                continue;
            }else{
                if(!number.empty()){
                    tokens.push_back(number);
                    number = "";
                }
            }
            if(ch == ' ') continue;
            if(ch == '('){
                ops.push(ch);
                needsZero = true;
                continue;
            }
            if(ch ==')'){
                while(ops.top()!='('){
                    tokens.push_back(string(1,ops.top()));
                    ops.pop();
                }
                ops.pop();
                needsZero = false;
                continue;
            }
            if((ch == '+' || ch =='-') && needsZero ){
                tokens.push_back("0");
            }
            int currRank=getRank(ch);
            while(!ops.empty() && getRank(ops.top()) >=currRank){
                tokens.push_back(string(1,ops.top()));
                ops.pop();
            }
            ops.push(ch);
            needsZero = true;
        }
        while(!ops.empty()){
            tokens.push_back(string(1,ops.top()));
            ops.pop();
        }
        return evalRPN(tokens);
    }
public:
    int evalRPN(vector<string>& tokens) {

        for(string& token:tokens){
            if(token== "+" || token== "-" ||token== "*" || token== "/")
            {
                int y=s.top();
                s.pop();
                int x=s.top();
                s.pop();
                s.push(cal(x,y,token));
            }else{
                s.push(atoi(token.c_str()));
            }
        }

        return s.top();
    }

    int cal(int x,int y,string token){
        if(token=="+") return x+y;
        if(token=="-") return x-y;
        if(token=="*") return x*y;
        if(token=="/") return x/y;
        return 0;
    }

private:
    stack<int> s;

private:
    stack<char> ops;
    
    int getRank(char ch){
        if(ch =='*' || ch=='/' ) return 2;
        if(ch =='+' || ch=='-' ) return 1;
        return 0;
    }

};
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

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习