代码随想录--栈和队列

232.用栈实现队列

• lc232
• 思路：用两个栈实现队列；一个输入栈，一个输出栈；入队时，数据进入输入站，出队时，数据从输入栈出栈进入输出栈中，最后输出数据；
• 代码如下：

class MyQueue {
public:
    stack<int>input_;
    stack<int>output_;
    MyQueue() {}
    
    void push(int x) {
        input_.push(x);
    }
    
    int pop() {
        // 如果output中有元素，直接输出；否则从input中转移元素到output；如果input也为空，说明队列为空
        // 题目假设所有操作都有效
        if(output_.empty()){
            while(!input_.empty()){
                output_.push(input_.top());
                input_.pop();
            }
        }
        int ret = output_.top();
        output_.pop();
        return ret;
    }
    
    int peek() {
        // 注意可能需要先把数据从input转移到output中，再将数据push到ouput_顶部
        int temp = this->pop();
        output_.push(temp);
        return temp;
    }
    
    bool empty() {
        return output_.empty() && input_.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

225. 用队列实现栈

• lc225
• 思路：两个队列实现一个栈；其实一个队列就可以完成，输入时将数据放入队列中，输出时另一个队列保存数据，输入队列的最后一个元素即目标数据，最后把另一个队列的数据再还原回原队列中

class MyStack {
public:
    queue<int>q_;
    queue<int>temp_;
    MyStack() {

    }
    
    void push(int x) {
        q_.push(x);
    }
    
    int pop() {
        while(q_.size() > 1){
            // 转移到temp_中
            temp_.push(q_.front());
            q_.pop();
        }
        int ret = q_.front();
        q_.pop();
        // 最后从temp_还原到q_中
        while(!temp_.empty()){
            q_.push(temp_.front());
            temp_.pop();
        }
        return ret;
    }
    
    int top() {
        // 注意先pop再重新加入数据
        int ret = this->pop();
        q_.push(ret);
        return ret;
    }
    
    bool empty() {
        return q_.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

20. 有效的括号

• lc20
• 思路：栈的应用；string输入为左括号则入栈，遇到匹配的右括号出栈，若遇到不匹配的右括号或栈中没有左括号则报错；若最后栈不为空，也报错
• 代码如下：

class Solution {
public:
    bool isValid(string s) {
        stack<char>stk;
        for(auto i : s){
            if(i == '(') stk.push(')');
            else if(i == '{') stk.push('}');
            else if(i == '[') stk.push(']');
            else if(stk.empty() || stk.top() != i){
                return false;
            }
            else{
                stk.pop();
            }
        }
        // 检查栈是否为空
        return stk.empty();
    }
};

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

• lc1047
• 思路：栈的应用；如果栈顶部元素和输入元素相同，则弹出，最后栈中的元素倒序输出即可
• 代码如下：

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char>stk;
        for(auto i : s){
            if(!stk.empty() && stk.top() == i){
                stk.pop();
            } else{
                stk.push(i);
            }   
        }
        string ret;
        while(!stk.empty()){
            ret += stk.top();
            stk.pop();
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

150. 逆波兰表达式求值

• lc150
• 栈的应用：计算后缀表达式的值；遇到数字入栈，遇到符号则弹出两个数字计算，再把结果重新入栈
• 函数stoll：string–>long long
• 代码如下：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long>stk;
        for(auto i : tokens){
            if(i == "+" || i == "*" || i == "-" || i == "/"){
                long long t1 = stk.top();
                stk.pop();
                long long t2 = stk.top();
                stk.pop();
                long long ret = 0;
                if(i == "+") ret = t1 + t2;
                else if(i == "-") ret = t2 - t1;  
                else if(i == "*") ret = t1 * t2;  
                else if(i == "/") ret = t2 / t1;  // 注意顺序 
                cout << ret << endl; 
                stk.push(ret);
            } else{
                // 转换为数字
                cout << i << endl;
                stk.push(stoll(i));
            }
        }
        // 输出最后的值
        return stk.top();
    }
};

239. 滑动窗口最大值

• lc239
• 队列的应用；暴力：对于每个窗口都遍历一遍求最大值，时间复杂度O(n^2)；使用单调队列解决（限制的双端队列，队头出队，队尾可进队和出队；名字来源：当入队的元素比队列中元素大时，队列中元素出队，所以从队尾到队头呈现单挑上升的现象）：用队头维护最大值，每移动一次窗口，新的值加入（若新的值最大则到队头，否则从队尾出队），旧的值移出（如果旧的是最大值才移出）；记忆方法：新人能力不够or老人都被淘汰
• 代码如下：

class Solution {
private:
    class MyQueue {
        // 定义一个限制的双端队列
        public:
            deque<int>dq;

            void pop(int val){
                if(!dq.empty() && dq.front() == val){
                    dq.pop_front();
                }
            }
            void push(int x){
                // 新的大就把前面的弹出去
                while(!dq.empty() && dq.back() < x){
                    dq.pop_back();
                }
                dq.push_back(x);
            }
            int get_top(){
                return dq.front();
            }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int>ret;
        MyQueue q;
        for(int i = 0; i < k; i++){
            q.push(nums[i]);
        }
        ret.push_back(q.get_top());
        // 移动窗口
        int n = nums.size();
        for(int i = k; i < n; i++){
            q.push(nums[i]);  // 新的移入
            q.pop(nums[i - k]);  // 老的移出
            ret.push_back(q.get_top());
        }
        return ret;
    }
};

347. 前 K 个高频元素

• lc347
• 队列的应用；优先队列；暴力：排序后输出前K个元素，排序的时间复杂度为O(nlogn)；用小堆，每次调整的时间复杂度为O(logk)，则总时间复杂度为O(nlogk)：用map记录频率，用小堆维护前K个高频元素，遍历元素时，如果堆个数大于K则弹出频率小的，加入频率高的
• 学习使用priority_queue和小堆中比较类的书写
• 还有一题简单的topK可以复习一下：题目
• 代码如下：

class Solution {
public:
    // 定义比较类
    class MyCompare {
        public:
            bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs){
                return lhs.second > rhs.second;  // 小堆
            }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 记录频率
        unordered_map<int, int>mp;
        for(auto i : nums){
            mp[i]++;
        }
        // 小堆
        priority_queue<pair<int, int>, vector<pair<int, int>>, MyCompare>q;
        for(auto it : mp){
            q.push(it);
            if(q.size() > k) q.pop();
        }
        // 任意顺序输出
        vector<int>ret;
        while(!q.empty()){
            ret.push_back(q.top().first);
            q.pop();
        }
        return ret;
    }
};

end

• 栈的应用：括号匹配，递归，后缀表达式计算，中缀转后缀表达式，删除重复元素
• 队列的应用：单调队列，优先队列，BFS
• 至此，栈和队列的题目结束！！！