006_栈与队列 - Leetcode - 编程

# 一、理论基础

栈是先进后出，队列是先进先出，二者在 STL 中都是容器适配器，其底层实现可依靠 deque、list 等容器。

# 二、题目实践

# 1、232. 用栈实现队列

class MyQueue {
public:
    MyQueue() {
        //
    }
    
    void push(int x) {
        _st1.push(x);
    }
    
    int pop() {
        int ret = -1;
        while(!_st1.empty()) {
            int top = _st1.top();
            _st1.pop();
            _st2.push(top);
        } ret = _st2.top();
        _st2.pop();

        while(!_st2.empty()) {
            int top = _st2.top();
            _st2.pop();
            _st1.push(top);
        } return ret;
    }
    
    int peek() {
        int ret = -1;
        while(!_st1.empty()) {
            int top = _st1.top();
            _st1.pop();
            _st2.push(top);
        } ret = _st2.top();
        // _st2.pop();

        while(!_st2.empty()) {
            int top = _st2.top();
            _st2.pop();
            _st1.push(top);
        } return ret;
    }
    
    bool empty() {
        return _st1.empty();
    }
private:
    std::stack<int, vector<int>> _st1;
    std::stack<int, vector<int>> _st2;
};

官方题解比我简单一些。其实我不用每次 peek 和 pop 之后强迫症把数据又倒回 stack1。入队的时候无脑入栈 stack1，出队的时候，如果 stack1 非空，先把 stack1 倒到 stack2，再从 stack2 顶端 pop 即可。如果 stack1 为空，那就直接从 stack2 顶端 pop：


class MyQueue {
private:
    stack<int> inStack, outStack;

    void in2out() {
        while(!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }

public:
    MyQueue() {}

    void push(int x) {
        inStack.push(x);
    }

    int pop() {
        if(outStack.empty()) {
            in2out();
        }
        int x = outStack.top();
        outStack.pop();
        return x;
    }

    int peek() {
        if(outStack.empty()) {
            in2out();
        }
        return outStack.top();
    }

    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

# 2、225. 用队列实现栈

这题在做的时候相比上一题花了我好多时间，主要是感觉有一丢丢绕。

思路 1：
我的做法是两个队列来回倒腾，每一次 pop 和 top 都要把数据从 in 倒腾到 out，把 in 的最后一个标记住、处理，然后再把 out 倒腾回 in。其实比较麻烦，我还得有一个 size 来记录当前一共有多少元素，以定位到 in 的最后一个元素：

class MyStack {
public:
    MyStack() {
        //
    }
    
    void push(int x) {
        _que1.push(x);
        _size++;
    }
    
    int pop() {
        int ret = -1;
        while(_size != 1) {
            ret = _que1.front();
            _que1.pop();
            --_size;
            _que2.push(ret);
        } ret = _que1.front();
        _que1.pop();

        --_size;
        while(!_que2.empty()) {
            _que1.push(_que2.front());
            _que2.pop();
            ++_size;
        } return ret;
    }
    
    int top() {
        int ret = -1;
        while(!_que1.empty()) {
            ret = _que1.front();
            _que1.pop();
            _que2.push(ret);
        }

        while(!_que2.empty()) {
            _que1.push(_que2.front());
            _que2.pop();
        } return ret;
    }
    
    bool empty() {
        return _size == 0;
    }

private:
    std::queue<int, deque<int>> _que1;
    std::queue<int, deque<int>> _que2;
    int _size = 0;
};

但其实不用这样。

思路 2：
每次 push 进 in，然后再把 out 里的倒腾回来，这样就倒序了。
然后每次都 swap 一下 in 和 out，确保如果有数据的话都在 out 里：

class MyStack {
public:
    MyStack() {

    }
    
    void push(int x) {
        m_qIn.push(x);
        while(!m_qOut.empty()) {
            int top = m_qOut.front();
            m_qOut.pop();
            m_qIn.push(top);
        }

        swap(m_qIn, m_qOut);
        // while(!m_qIn.empty()) {
        //     int top = m_qIn.front();
        //     m_qIn.pop();
        //     m_qOut.push(top);
        // }
    }
    
    int pop() {
        if(!m_qOut.empty()) {
            int ret = m_qOut.front();
            m_qOut.pop();
            return ret;
        } else {
            return -1;
        }
    }
    
    int top() {
        if(!m_qOut.empty()) {
            return m_qOut.front();
        } else {
            return -1;
        }
    }
    
    bool empty() {
        return (m_qOut.empty());
    }

private:
    queue<int> m_qIn;
    queue<int> m_qOut;
};

思路 3：
还有一种方法更厉害，只需要用到一个 queue 就搞定了。思路就是，既然你 queue 是先进先出，那么我 pop 出去之后立马又 push 进来，然后当我 pop 了 len - 1 个元素之后，接下来再 pop 出来的就是目标值了：

class MyStack {
public:
    MyStack() {

    }
    
    void push(int x) {
        m_queue.push(x);
    }
    
    int pop() {
        int length = m_queue.size();

        for(int i = 0; i < length - 1; ++i) {
            int front = m_queue.front();
            m_queue.pop();
            m_queue.push(front);
        }

        int ret = m_queue.front();
        m_queue.pop();
        return ret;
    }
    
    int top() {
        int length = m_queue.size();
        int ret = -1;
        for(int i = 0; i < length; ++i) {
            int front = m_queue.front();
            if(i == length-1) ret = front;
            m_queue.pop();
            m_queue.push(front);
        } return ret;
    }
    
    bool empty() {
        return (m_queue.empty());
    }

private:
    queue<int> m_queue;
};

# 3、20. 有效的括号

#栈

这里我用一个 vector 模拟一个栈（因为我觉得没必要用到 stack），每次遇到左括号就压栈，遇到右括号就出栈，并且判断出栈的左括号与当前右括号是否匹配。一次遍历之后，如果括号都是有效的，则栈理应为空：

class Solution {
public:
    bool isValid(string s) {
        vector<char> st;
        for(int i = 0; i < s.size(); ++i) {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
                st.push_back(s[i]);
            } else {
                if(st.empty()) return false;
                char top = st[st.size()-1];
                if(s[i] == ')' && top == '(' ||
                    s[i] == '}' && top == '{' ||
                    s[i] == ']' && top == '[')
                {
                    st.pop_back();
                } else {
                    return false;
                }
            }
        } return st.empty();
    }
};

这里注意，vector 判空是有 empty 的，太久没写都生疏了。

还有一种不用栈的思路，就是，我们知道对于有效的括号来说，一定会有至少一对括号是紧邻着出现的，所以我们可以在字符串中寻找然后替换为空字符串，以消除。直到无法消除为止，此时判断字符串是否为空：

class Solution {
public:
    bool isValid(string s) {
        while(1) {
            int pos1 = s.find("()");
            int pos2 = s.find("[]");
            int pos3 = s.find("{}");
            if(pos1 != std::string::npos) {
                s.replace(pos1, 2, "");
            } else if (pos2 != std::string::npos) {
                s.replace(pos2, 2, "");
            } else if (pos3 != std::string::npos) {
                s.replace(pos3, 2, "");
            } else {
                return false;
            }
            
            if(s.empty()) return true;
        }
    }
};

# 4、1047. 删除字符串中的所有相邻重复项

#栈

class Solution {
public:
    string removeDuplicates(string s) {
        string st;
        st.push_back(s[0]);
        for(int i = 1; i < s.size(); ++i) {
            if(!st.empty() && s[i] == st[st.size()-1]) {
                st.pop_back();
            } else {
                st.push_back(s[i]);
            }
        } return st;
    }
};

同样的思路，但是官方写法更精简：

class Solution {
public:
    string removeDuplicates(string s) {
        string stk;
        for(char ch : s) {
            if(!stk.empty() && stk.back() == ch) {
                stk.pop_back();
            } else {
                stk.push_back(ch);
            }
        } return stk;
    }
};

因为 string 可以用 back 来获取末端元素！这就体现了对 API 的熟练程度了！

# 5、150. 逆波兰表达式求值

#栈

思路也是很显而易见 —— 遇到符号之后对栈顶两个元素进行运算：
这种情况下，根本不用考虑遇到连续运算符，反正一遇到运算符就计算并压入新的计算结果。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // 
        stack<string> st;
        for(auto s : tokens) {
            if(s == "+" || s == "-" || s == "*" || s == "/") {
                string v1, v2;
                v1 = st.top();
                st.pop();
                v2 = st.top();
                st.pop();
                if(s == "+") {
                    st.push(to_string(stoi(v2) + stoi(v1)));
                } else if(s == "-") {
                    st.push(to_string(stoi(v2) - stoi(v1)));
                } else if(s == "*") {
                    st.push(to_string(stoi(v2) * stoi(v1)));
                } else if(s == "/") {
                    st.push(to_string(stoi(v2) / stoi(v1)));
                }
            } else {
                st.push(s);
            }
        } return stoi(st.top());
    }
};

# 6、239. 滑动窗口最大值

#单调队列

这题有点难，不愧是 hard 题。

一开始我想的是用一个 deque 来模拟一个普通队列，然后每次迭代时一进一出，然后利用 max_element 对 deque 元素进行求最大值的操作。但是这样的话，其实和两层 for 循环进行暴力解没什么区别。

后来我也有想到优先队列，维护一个大顶堆。但是，这样虽然能够求得最大值，却无法在滑动窗口时选择该弹出哪个元素。

我也有想过维护一个 max 变量，和其相应的索引。然后试图通过判断右边移入元素和左边移出元素和我记录的 max 变量以及 max 索引的关系来解题，但是我没办法判断窗口中 “第二大”、“第三大” 等元素是什么，所以有可能在最左端移除了最大值，最右端进来的不是更大的值，则此时窗口中的最大值应该是原本窗口中的第二大值，但我无法索引。

最终看了题解，才知道要维护一个单调队列。有一点点抽象，但仔细思考之后还是能够理解的：

思路 1：

我们自定义一个单调队列，它应该具备以下条件：
该队列单调递减，队头元素（左边）始终最大，队尾元素（右边）始终最小。

则，当每一次有新的元素入队时，将该元素与队尾（右边）元素进行比较，把小于该值的元素从队列中 pop 出来，最终再把该元素 push 进去。这样，每次 push 之后，都能确保队列中的元素始终单调递减。

同时，每一次要将窗口最左边的元素出队时，我们需要判断该元素是否为队头（左边）元素 —— 因为如果它不是队头，说明它早就在我们的 push 操作时就被 pop 出来了，就不需要重复 pop 一个不存在的元素了。

这样做的目的是出于这样的一个思想：当窗口中存在一个最大值时，我们滑动窗口更新最大值时，要么是原本最大值的右侧出现了新的最大值，要么就是原本最大值的右侧始终没有新的最大值出现，原最大值滑出窗口，原最大值右边的第二大值继任成为最大值。第二大值只可能从最大值的右边出现。所以，基于此，我们在 push 时就可以把小于当前值的队尾元素 pop 出来。

class Solution {
private:
    class MyQueue {
    private:
        deque<int> que;
    public:
        void push(int val) {
            while(!que.empty() && val > que.back()) {
                que.pop_back();
            } que.push_back(val);
        }

        void pop(int val) {
            if(!que.empty() && val == que.front()) {
                que.pop_front();
            }
        }

        int front() {
            return que.front();
        }
    };


public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ret;
        MyQueue mq;
        for(int i = 0; i < k; ++i) {
            mq.push(nums[i]);
        } ret.push_back(mq.front());

        for(int j = k; j < nums.size(); ++j) {
            mq.push(nums[j]);
            mq.pop(nums[j - k]);
            ret.push_back(mq.front());
        } return ret;
    }
};

思路 2：
看了官方题解，发现用优先队列也可以（也确实因为 “最大值” 让人最直观地联想到优先队列）。

用一个大顶堆来记录最大值，这个大家都知道。但是，如上文所述，要解决窗口右滑时如何从优先队列中弹出窗口最左侧元素的问题。

这里我们在优先队列中存放的就不只是值，顺便把该值在 nums 中的索引给存入，形成一个 pair 键值对。

我们的优先队列根据 nums[i] 进行排序，可得最大值。然后我们右滑时，如果堆顶元素的索引小于窗口左端即将滑出的索引，则弹出。否则不用操作。（因为我们只考虑最大值。如果一个数值已经滑出窗口了，但它不在优先队列的堆顶，无所谓 —— 反正我们只会用到堆顶，后续总会有机会把它 pop 出来的）

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for(int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for(int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            while(q.top().second <= i - k) {
                q.pop();
            } ans.push_back(q.top().first);
        } return ans;
    }
};

# 7、347. 前 K 个高频元素

我想到的思路是，先用 map 一次遍历得到每个元素的频率，然后遍历这个 map，将其每个元素（键值对）压入优先队列中，以值为键，以键为值，利用优先队列的自动排序特性进行排序。最后再把优先队列的前 k 个元素 pop 出来压入数组中作为结果进行返回即可：

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for(int v : nums) {
            ++freq[v];
        }

        priority_queue<pair<int, int>> pq;
        for(auto p : freq) {
            pq.push({p.second, p.first});
        }

        vector<int> ret;
        for(int i = 0; i < k; ++i) {
            ret.push_back(pq.top().second);
            pq.pop();
        } return ret;
    }
};

看了一眼官方题解，思路差不多，但是它维护的是一个最小堆的优先队列，然后严格控制队列的大小为 k，最后再无脑把整个队列里的所有数据 pop 出来。思路大差不差，但是性能理论上会比我的解法优很多。

网友说：

“如果用最大堆，所有元素压入堆，复杂度是 nlogn，而且浪费内存。如果是用最小堆，则复杂度是 nlogk”

栈单调队列