用输入栈和输出栈实现队列

当输出栈为空时，输入栈的全部入输出栈

class MyQueue {
public:
    stack<int> in;
    stack<int> out;
    MyQueue() {
    }
    void push(int x) {
        in.push(x);
    }
    int pop() {
        if(out.empty()) {
            while(!in.empty()) {
                int k = in.top();
                in.pop();
                out.push(k);
            }
        }
        int res = out.top();
        out.pop();
        return res;
    }
    int peek() {
        if(out.empty()) {
            while(!in.empty()) {
                int k = in.top();
                in.pop();
                out.push(k);
            }
        }
        return out.top();
    }
    bool empty() {
        return in.empty()&&out.empty();
    }
};

队列实现栈

两个队列实现栈：将新插入的值插入队列B，再把队列A的元素依次插入队列B的后面，此时队列B中的顺序和栈顺序一样，然后再交换队列A和B。
一个队列实现栈：将除了最后一个元素的其他元素依次弹出后再插入，此时顺序相当于栈的顺序了。

class MyStack {
public:
    queue<int> queue1;
    queue<int> queue2;

    /** Initialize your data structure here. */
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        queue2.push(x);
        while (!queue1.empty()) {
            queue2.push(queue1.front());
            queue1.pop();
        }
        swap(queue1, queue2);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int r = queue1.front();
        queue1.pop();
        return r;
    }

    /** Get the top element. */
    int top() {
        int r = queue1.front();
        return r;
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return queue1.empty();
    }
};

栈的应用

“开心消消乐”：删除字符串中所有相邻重复项，要求最后得到的字符串没有相邻的重复项

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

multiset

set, multiset, map, multimap的插入删除查找都是log级别
unordered_set, unordered_map, unordered_multiset, unordered_multimap的插入删除查找平均为常数级别，最坏是O(n)级别
注意rbegin()函数

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        multiset<int> mset;
        for(int i=0;i<k;i++) mset.insert(nums[i]);
        vector<int> res;res.push_back(*mset.rbegin());
        for(int i=0;i<nums.size()-k;i++) {
            mset.erase(mset.find(nums[i]));
            mset.insert(nums[i+k]);
            res.push_back(*mset.rbegin());
        }
        return res;
    }
};

自定义队列

自定义单调队列（基于deque）
https://leetcode-cn.com/problems/sliding-window-maximum/

class MyQueue { //单调队列（从大到小）
public:
    deque<int> que; // 使用deque来实现单调队列
    // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    // 同时pop之前判断队列当前是否为空。
    void pop(int value) {
        if (!que.empty() && value == que.front()) {
            que.pop_front();
        }
    }
    // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
    // 这样就保持了队列里的数值是单调从大到小的了。
    void push(int value) {
        while (!que.empty() && value > que.back()) {
            que.pop_back();
        }
        que.push_back(value);

    }
    // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
    int front() {
        return que.front();
    }
};

优先队列

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res;
        map<int,int> ma;
        priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> >>pq;
        for(auto i:nums) ma[i]++;
        for(auto& pa:ma)
        {
            pq.emplace(pa.second,pa.first);
            if(pq.size()>k) pq.pop();
        }
        while(!pq.empty())
        {
            res.emplace_back(pq.top().second);
            pq.pop();
        }
        return res;
    }
};

自定义类型的优先队列

#include <iostream>
#include <queue>
using namespace std;

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};

int main() 
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty()) 
    {
        cout << d.top().x << '\n';
        d.pop();
    }
    cout << endl;

    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(c);
    f.push(b);
    f.push(a);
    while (!f.empty()) 
    {
        cout << f.top().x << '\n';
        f.pop();
    }
}

算法