【代码随想录】二刷-栈和队列

8

栈和队列

  • 《代码随想录》

    232. 用栈实现队列

  • 使用两个栈来模拟队列,stIn用来输入,stOut用来输出。
    • push: 直接将元素push进stIn
    • pop: 将stIn中的元素导入stOut,再由stOut上pop出来。如果stOut()非空,直接从stOut中取,否则先从stIn中push进stOut。
    • peek: 复用pop,取出第一个,然后再push进stOut。
    • empty: 元素分开存储在stIn和stOut两个栈中,所以要同时判断是否为空。
  • 补充: 实际开发中,一定要懂得复用,功能相近的函数要抽象出来,不要大量的复制粘贴,很容易出问题。
class MyQueue {
public:
    stack<int>stIn;// 输入栈
    stack<int>stOut;// 输出栈

    MyQueue() {

    }

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

    int pop() {
        if(stOut.empty()){
            while(!stIn.empty()){
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int ret = stOut.top();
        stOut.pop();
        return ret;
    }

    int peek() {
        int ret = pop();// 直接调用pop,然后在把对应元素push回去
        stOut.push(ret);
        return ret;
    }

    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

225. 用队列实现栈

  • 两个队列实现栈
    • que2起到辅助作用,备份,详见下方que1=que2。
      • 在pop的时候保存去掉最后一个元素之后的队列。重新赋值个que1,然后情况que2。
class MyStack {
public:
    queue<int>que1;
    queue<int>que2;// 起辅助作用
    MyStack() {

    }

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

    int pop() {
        int size = que1.size();
        size--;
        while(size--){
            que2.push(que1.front());
            que1.pop();
        }
        int ret = que1.front();
        que1.pop();
        que1 = que2;// que2作用
        // 清空que2
        while(!que2.empty()){
            que2.pop();
        }
        return ret;
    }

    int top() {
        return que1.back();
    }

    bool empty() {
        return que1.empty();
    }
};
  • 其实使用一个栈即可
    • 将队列前面的push->pop到后面,只剩之前最后一个元素不动,然后队列pop即可。
class MyStack {
public:
    queue<int>que1;
    MyStack() {

    }

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

    int pop() {
        int size = que1.size();
        size--;
        while(size--){
            que1.push(que1.front());
            que1.pop();
        }
        int ret = que1.front();
        que1.pop();
        return ret;
    }

    int top() {
        return que1.back();
    }

    bool empty() {
        return que1.empty();
    }
};

20. 有效的括号

  • 方法一
    • 这个方法写法有点乱,判断是否可以组成一个完整的一组括号,最后判断栈是否为空,为空则说明全部匹配成功。
    • 左括号直接push进,遇到右括号进行判断,若与栈顶无法组成完整括号,直接return false。
    • 注意括号是一层一层包含的。例如:"{[]()}。所以"[(])"为括号的非法包含。
class Solution {
public:
    bool isValid(string s) {
        stack<char>st;
        for(char& c:s){
            // if(st.empty())st.push(c);
            if(c == ')'){
                if(!st.empty() && st.top() == '(')st.pop();// 是否可以匹配
                else{
                    return false;// 无法匹配
                    //st.push(c);
                }
            }else if(c == ']'){
                if(!st.empty() && st.top() == '[')st.pop();
                else{
                    return false;
                    //st.push(c);
                }
            }else if(c == '}'){
                if(!st.empty() && st.top() == '{')st.pop();
                else{
                    return false;
                    //st.push(c);
                }
            }else{
                st.push(c);
            }
        }
        return st.empty();
    }
};
  • 方法二
    • 同方法一,但是push进的是对应左括号的右括号,遇到右括号如果与栈顶相等再pop出去,反之return false了。
    • 注意括号是一层一层包含的。例如:"{[]()}。所以"[(])"为括号的非法包含。
class Solution {
public:
    bool isValid(string s) {
        // 奇数长度,肯定不符合
        if(s.size() % 2 != 0)return false;
        stack<int>st;
        for(char& c:s){
            if(c == '(')st.push(')');
            else if(c == '[')st.push(']');
            else if(c == '{')st.push('}');
            else if(st.empty() || c != st.top())return false;// 如果为空,则说明还没有左括号呢,此时这个c为右括号,无法匹配成功。
            else st.pop();// c == st.top(),到这里肯定是非空
        }
        return st.empty();
    }
};

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

  • 栈的简单使用
  • 补充:
    • 递归的实现就是: 每一次调用递归都会把函数的局部变量、参数值和返回地址等压入调用栈中,然后递归返回的时候,从栈顶弹出上一次的各项参数,所以这就是为什么递归可以返回上一层位置的原因。
    • 在企业项目开发中,尽量不要使用递归!在项目比较大的时候,由于参数多,全局变量等等,使用递归很容易判断不充分return的条件,非常容易无限递归(或者递归层级过深),造成栈溢出错误(这种问题还不好排查)。
class Solution {
public:
    string removeDuplicates(string s) {
        stack<char>st;
        for(char& c:s){
            if(!st.empty() && st.top() == c)st.pop();// 注意条件控制,栈要非空。
            else st.push(c);
        }
        string ret;
        while(!st.empty()){
            ret += st.top();
            st.pop();
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
};

150. 逆波兰表达式求值

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long>st;
        int ret = 0;
        for(string &s:tokens){
            // 如果是符号,则取出两个数,然后进行运算->push回去
            if(s == "+" || s == "-" || s == "*" || s == "/"){
                long long num1 = st.top();
                st.pop();
                long long num2 = st.top();
                st.pop();
                // 注意运算符是谁对谁后一个对前一个
                if(s == "+")st.push(num2+num1);
                else if(s == "-")st.push(num2-num1);
                else if(s == "*")st.push(num2*num1);
                else if(s == "/")st.push(num2/num1);
            }else st.push(stoll(s));
        }
        return st.top();// 栈中剩的最后一个值为最终结果
    }
};

239. 滑动窗口最大值

  • 单调队列
    • 放进去窗口的元素,然后随着窗口的移动,单调队列也一进一出,每次移动后,队列告诉我们里面的最大值(front方法)是什么。
    • 队列没有必要维护窗口中的所有元素,而只需要维护有可能成为窗口最大值的元素就可以了,同时保证队列里的元素数值是由大到小的(push方法)。
      • 不要以为单调队列就是对窗口里的数进行排序,如果是那样的话,跟优先级队列又有什么区别呢。
  • 详见代码中的注释,看不懂就多看下面的动画演示。

在这里插入图片描述

class Solution {
public:
    class myQueue{
        deque<int>que;
    public:
        void pop(int v){ // 如果当前要pop的元素是队头的,即最大的,那就pop,否则继续保留最大的。
            if(!que.empty() && v == que.front()){
                que.pop_front();
            }
        }
        // 从后面开始,如果要放入窗口的元素大于后面的。
        // 那就pop出来,最终将v push进去,要么为最大的,要么队列中v前面有最大的。
        // 使得,队头的元素肯定为当前窗口的最大值。
        void push(int v){
            while(!que.empty() && v > que.back()){
                que.pop_back();
            }
            que.push_back(v);
        }
        // 取得队头元素,即当前窗口的最大值。
        int front(){
            return que.front();
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int>ret;
        myQueue que;
        // 先往里面弄k个,这样下面才能统一管理
        for(int i = 0; i < k ;i++){
            que.push(nums[i]);
        }
        ret.push_back(que.front());
        for(int i = k ;i < nums.size();i++){
            // 下面两步为窗口的移动,这两步的先后顺序无影响。
            que.pop(nums[i-k]);// 去掉最左边元素
            que.push(nums[i]);// 去掉最右边元素
            // 收集结果
            ret.push_back(que.front());
        }
        return ret;
    }
};

347. 前 K 个高频元素

  • 这个题在一刷的时候漏掉了。
  • 方法:
    • 先统计每个元素出现的频率。
    • 使用一个小顶堆,按照元素出现的频率排序,小顶指的是,最小的出现频率在堆顶。
    • 使用k控制堆中的元素数量,保持堆中有k个元素,这k个元素即是数组中前k个高频元素。
  • 小插曲: 结果让返回前k个出现的高频元素,我开始还理解错了,以为是跟上面那个题似的,维护一个k个的窗口, 每次保存窗口内出现频率最高的元素~。
class Solution {
public:
    // 小顶堆排序
    class myComparion{
    public:
        // k v:元素-频率,按照频率排序,堆顶为频率小的——小顶堆。
        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>map;// map[nums[i]]对应元素出现的次数
        for(int i = 0; i < nums.size();i++){
            map[nums[i]]++;
        }

        // 小顶堆
        // k-v 元素-频率
        priority_queue<pair<int,int>,vector<pair<int,int>>,myComparion>pri_que;

        // 用固定大小为k的小顶堆,扫描所有频率的数值
        for(unordered_map<int,int>::iterator it = map.begin();it != map.end();it++){
            pri_que.push(*it);
            if(pri_que.size() > k){// 如果堆中的元素数量大于k,则弹出堆顶元素,即
                pri_que.pop();
            }
        }

        // 找出前k个高频元素,因为小顶推先弹出的是最小的,所以倒叙来输出到数组中
        // 我们要的是从频率高的到频率低的。
        vector<int>ret(k);
        for(int i = k-1;i >=0 ;i--){// 实际上队列中最多也就维持了k个元素,如上面循环中所示。
            ret[i] = pri_que.top().first;
            pri_que.pop();
        }
        return ret;
    }   
};