七、栈与队列（stack and queue）

一、栈与队列基础

队列是先进先出，栈是先进后出。

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。

所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

那么问题来了，STL 中栈是用什么容器实现的？

从下图中可以看出，栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。

虽然 stack 和 queue 和 priority_queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为 stack 和 queue 和 priority_queue 只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque，而 priority_queue 默认使用 vector。

二、例题

（一）栈

1.232. 用栈实现队列

（1）思路

（2）代码

class MyQueue {
public:
stack<int> in;
stack<int> out;
    MyQueue() {
        
    }
    
    void push(int x) {
        in.push(x);
    }
    
    int pop() {
        // 只有当out为空的时候，再从in里导入数据（导入in全部数据）
        if (out.empty()) { 
             // 从in导入数据直到in为空
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        int result = out.top();
        out.pop();
        return result;
    }
    
    int peek() {
        int res = this->pop();
        out.push(res);
        return res;
    }
    
    bool empty() {
         return in.empty() && out.empty();
    }
};

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

（3）复杂度分析

时间复杂度：push和empty为O(1), pop和peek为O(n)
空间复杂度：O(n)

2.225. 用队列实现栈

（1）思路

（2）代码

（3）复杂度分析

3.20.有效的括号

（1）思路

（2）代码

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 == 1) {
            return false;
        }
        stack<char> t;
        for (auto ch : s) {
            if (ch == '(') { // 
                t.push(')');
            }
            else if (ch == '[') {
                t.push(']');
            }
            else if (ch == '{') {
                t.push('}');
            }
            else if (t.empty() || ch != t.top()) { 
                // 第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
                // 第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
                // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
                return false;
            }
            else {
                t.pop();
            }
        }
       return t.empty();
    }
};
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

（3）复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)

4.1047.删除相邻有效字符

（1）思路

我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在前一位是不是遍历过一样数值的元素，那么如何记录前面遍历过的元素呢？

所以就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。

（2）代码

class Solution {
public:
    string removeDuplicates(string s) {
        string result;
        for (char ch : s) {
            if (result.empty() || result.back() != ch) {
                result.push_back(ch);
            }
            else {
                result.pop_back();
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（3）复杂度分析

时间复杂度: O(n)
空间复杂度: O(1)，返回值不计空间复杂度

6.150. 逆波兰表达式求值

（1）思路

那么来看一下本题，其实逆波兰表达式相当于是二叉树中的后序遍历。 大家可以把运算符作为中间节点，按照后序遍历的规则画出一个二叉树。

（2）代码

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // 力扣修改了后台测试数据，需要用longlong
        stack<long long> st; 
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                long long num1 = st.top();
                st.pop();
                long long num2 = st.top();
                st.pop();
                if (tokens[i] == "+") st.push(num2 + num1);
                if (tokens[i] == "-") st.push(num2 - num1);
                if (tokens[i] == "*") st.push(num2 * num1);
                if (tokens[i] == "/") st.push(num2 / num1);
            } else {
                st.push(stoll(tokens[i]));
            }
        }

        int result = st.top();
        st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
        return result;
    }
};

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

（3）复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)

7.347. 前 K 个高频元素

（1）思路

首先统计元素出现的频率，这一类的问题可以使用map来进行统计。

然后是对频率进行排序，这里我们可以使用一种 容器适配器就是优先级队列。

什么是优先级队列呢？

其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？

缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

（2）代码

class Solution {
public:
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        for (int i = 0; i < nums.size(); i ++) {
            map[nums[i]]++;
        }
        priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison> pri_que;
        for (auto it = map.begin(); it != map.end(); it ++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
        }
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
    
};
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

（3）时间复杂度分析

时间复杂度: O(nlogk)
空间复杂度: O(n)