算法总结-栈和队列

1.栈实现队列

思路：两个栈实现，一个出一个进。

pop() 把sin的元素出栈赋值给sout，赋值完后sout pop的第一个就是队头元素

peek() 直接调用上述实现的pop函数 

class MyQueue {
public:
    MyQueue() {
 
    }
    stack<int> sin;
    stack<int> sout;
    void push(int x) {
        sin.push(x);
    }
    
    int pop() {
        if(sout.empty())
        {
            while(!sin.empty())
            {
                sout.push(sin.top());
                sin.pop();
            }
        }
        int res=sout.top();
        sout.pop();
       //两个栈实现 弹出后另外一个栈不需要赋值了 后续直接用sout操作
        return res;
    }
    
    int peek() {
        int res=this->pop();
        //这里是sout再push进来
        sout.push(res);
        return res;
    }
    
    bool empty() {  
        return sin.empty()&&sout.empty();
    }
};

2.队列实现栈

思路：单个队列实现。

pop：把队列的头元素依次插入到队尾，除了最后一个（这个元素是要pop出去的）。

top：直接调用队列的back方法

class MyStack {
public:
    MyStack() {
 
    }
    queue<int> q1;
    void push(int x) {
        q1.push(x);
    }
    
    int pop() {
        int size=q1.size();
        size--;
        while(size--)
        {
            q1.push(q1.front());
            q1.pop();
        }
        int res=q1.front();
        //记得要pop
        q1.pop();
        return res;
    }
    
    int top() {
        int res=q1.back();
        return res;
    }
    
    bool empty() {
        return q1.empty();
    }
};

 20. 有效的括号

思路：用栈来实现，遍历s对于每一个左括号，栈里push进一个相应的右括号。两种失败情况，如果栈的top和s[i]相等就返回true

class Solution {
public:
    bool isValid(string s) {
        stack<char> sk;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='(')
            {
                sk.push(')');
            }
            else if(s[i]=='[')
            {
                sk.push(']');
            }
            else if(s[i]=='{')
            {
                sk.push('}');
            }
// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
            else if(sk.empty()||sk.top()!=s[i])
            {
                return false;
            }
            else
            {
                //sk.top()==s[i] 栈弹出
                sk.pop();
            }
        }
     return sk.empty();
    }
};

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

注意 push的逻辑

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> sk;
        for(int i=0;i<s.size();i++)
        {
            //注意 push的逻辑
            if(sk.empty()||sk.top()!=s[i])
            {
                sk.push(s[i]);
            }
            else{
                sk.pop();
            }
        }
        string res="";
        while(!sk.empty())
        {
            res+=sk.top();
            sk.pop();
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

150. 逆波兰表达式求值

用2 减去 1 

要用stoll把string转成int

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> sk;
      
        for(int i=0;i<tokens.size();i++)
        {
            if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/")
            {
                int num1=sk.top();
                sk.pop();
                int num2=sk.top();
                //这里也要pop掉
                  sk.pop();
                if(tokens[i]=="+")
                sk.push(num2+num1);
                 if(tokens[i]=="-")
                sk.push(num2-num1);
                 if(tokens[i]=="*")
                sk.push(num2*num1);
                 if(tokens[i]=="/")
                sk.push(num2/num1);
            }
            else{
            //字符串要转成 int
        sk.push(stoll(tokens[i]));
            }
         
        }   
        return sk.top();
    }
};

239. 滑动窗口最大值

deque双端队列 

思路 用deque模拟滑动窗口动，封装好pop、push、front方法

class Solution {
public:
    class Mydeque
    {
         public:
        deque<int> de;
        void pop(int value)
        {
            //窗口移除的元素是第一个元素 那么pop 其他的都不操作
            if(!de.empty()&&value==de.front())
            {
                de.pop_front();
            }
        }
        void push(int value)
        {
            //先pop 循环判断 值大于最后一个值就pop
            while(!de.empty() &&value>de.back())
            {
               de.pop_back();
            }
             //再push
             de.push_back(value);
        }
        int front()
        {
            return de.front();
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        Mydeque que;
        vector<int> result;
        for(int i=0;i<k;i++)
        {
            que.push(nums[i]);
        }
        result.push_back(que.front());
        for(int i=k;i<nums.size();i++)
        {
            que.pop(nums[i-k]);
            que.push(nums[i]);
            result.push_back(que.front());
        }
        return result;
    }
};

347. 前 K 个高频元素 

小顶堆队列

先用哈希map存储每个元素的频率

放入队列中 控制队列大小

小顶堆=>反向输出到结果集

class Solution {
public:
   class mycmp{
    //  public:
    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) {
        //<int,int>
        unordered_map<int,int> map;
         vector<int> result(k);
        for(int i=0;i<nums.size();i++)
        {
            map[nums[i]]++;
        }
        priority_queue<pair<int,int>,vector<pair<int,int>>,mycmp> pri_que;
        for(unordered_map<int,int>:: iterator it=map.begin();it!=map.end();it++)
        {
            pri_que.push(*it);
            if(pri_que.size()>k)
            {
                pri_que.pop();
            }
        }
        for(int i=k-1;i>=0;i--)
        {
            //pri_que.top().first;
            result[i]=pri_que.top().first;
            pri_que.pop();
        }
        return result;
 
    }
};