class MinStack {
public:
    MinStack() {
    }
    void push(int val) {
    }
    void pop() {
    }
    int top() {
    }
    int getMin() {
    }
};

class MinStack {
public:
    MinStack() {
    }
    void push(int val) {
        use.push(val);
        if(rem.empty()||rem.top()>=val)
        {
            rem.push(val);
        }
    }
    void pop() {
        if(rem.top()==use.top())
        {
            rem.pop();
        }
        use.pop();
    }
    int top() {
        return use.top();
    }
    int getMin() {
        return rem.top();
    }
private:
    stack<int>use;
    stack<int>rem;
};

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        long long res;
        stack<int> st1;
        for(auto e : tokens)
        {
            if(e=="+"||e=="-"||e=="*"||e=="/")
            {
                long long right=st1.top();
                st1.pop();
                long long left=st1.top();
                st1.pop();
                switch(e[0])
                {
                    case '+':st1.push(left+right);
                            break;
                    case '-':st1.push(left-right);
                            break;
                    case '*':st1.push((int)(left*right));
                            break;
                    case '/':st1.push(left/right);
                            break;
                }
            }
            else
            {
                st1.push(stoll(e));
            }
        }
        return st1.top();
    }
};

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空
接口如下：
class MyStack {
public:
    MyStack() {
    }
    void push(int x) {
    }
    int pop() {
    }
    int top() {
    }
    bool empty() {
    }
};

class MyStack {
public:
    MyStack() {
    }
    void push(int x) {
        if(q1.empty())
        {
            q1.push(x);
            while(!q2.empty())
            {
                q1.push(q2.front());
                q2.pop();
            }
        }
        else
        {
            q2.push(x);
            while(!q1.empty())
            {
                q2.push(q1.front());
                q1.pop();
            }
        }
    }
    int pop() {
        if(q1.empty())
        {
            int res=q2.front();
            q2.pop();
            return res;
        }
        else
        {
            int res=q1.front();
            q1.pop();
            return res;
        }
    }
    int top() {
        if(q1.empty())
        {
            int res=q2.front();
            return res;
        }
        else
        {
            int res=q1.front();
            return res;
        }
    }
    bool empty() {
        return q1.empty()&&q2.empty();
    }
private:
    queue<int> q1;
    queue<int> q2;
};

#include <iostream>
using namespace std;
#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
int main(){
        // 默认情况下，创建的是大堆，其底层按照小于号比较
        vector<int> v{3,2,7,6,0,4,1,9,8,5};
        priority_queue<int> q1;
        for (auto& e : v)
        q1.push(e);
        cout << q1.top() << endl;
        // 如果要创建小堆，将第三个模板参数换成greater比较方式
        priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
        cout << q2.top() << endl;
        return 0;
}

template <typename Ty>
struct greater {
    __device__ __forceinline__ Ty operator()(Ty arg1, Ty arg2) const {
        return (arg1 < arg2) ? arg2 : arg1;
    }
};

class Date
{
    public:
    Date(int year = 1900, int month = 1, int day = 1)
        : _year(year)
            , _month(month)
            , _day(day)
        {}
    bool operator<(const Date& d)const
    {
        return (_year < d._year) ||
            (_year == d._year && _month < d._month) ||
            (_year == d._year && _month == d._month && _day < d._day);
    }
    bool operator>(const Date& d)const
    {
        return (_year > d._year) ||
            (_year == d._year && _month > d._month) ||
            (_year == d._year && _month == d._month && _day > d._day);
    }
    friend ostream& operator<<(ostream& _cout, const Date& d)
    {
        _cout << d._year << "-" << d._month << "-" << d._day;
        return _cout;
    }
    private:
    int _year;
    int _month;
    int _day;
};
void TestPriorityQueue()
{
    // 大堆，需要用户在自定义类型中提供<的重载
    priority_queue<Date> q1;
    q1.push(Date(2018, 10, 29));
    q1.push(Date(2018, 10, 28));
    q1.push(Date(2018, 10, 30));
    cout << q1.top() << endl;
    // 如果要创建小堆，需要用户提供>的重载
    priority_queue<Date, vector<Date>, greater<Date>> q2;
    q2.push(Date(2018, 10, 29));
    q2.push(Date(2018, 10, 28));
    q2.push(Date(2018, 10, 30));
    cout << q2.top() << endl;
}

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

class Solution {
    public:
    int findKthLargest(vector<int>& nums, int k) {
        // 将数组中的元素先放入优先级队列中
        priority_queue<int> p(nums.begin(), nums.end());
        // 将优先级队列中前k-1个元素删除掉
        for(int i= 0; i < k-1; ++i)
        {
            p.pop();
        }
        return p.top();
    }
};

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
using namespace std;
namespace hxq
{
    template<class T, class Container = std::deque<T>>  // 定义模板类 stack，可以指定 T 类型和 Container 容器类型（默认为 deque）
        class stack
        {
            public:
            void push(const T& x)  // 在栈顶插入元素
            {
                _con.push_back(x);  // 使用容器的 push_back() 方法
            }
            void pop()  // 删除栈顶元素
            {
                _con.pop_back();  // 使用容器的 pop_back() 方法
            }
            T& top()  // 访问栈顶元素
            {
                return _con.back();  // 使用容器的 back() 方法
            }
            const T& top() const  // 访问栈顶元素（常量引用版本，用于 const 对象）
            {
                return _con.back();  // 使用容器的 back() 方法
            }
            bool empty()  const  // 判断栈是否为空
            {
                return _con.empty();  // 使用容器的 empty() 方法
            }
            size_t size() const  // 返回栈的大小
            {
                return _con.size();  // 使用容器的 size() 方法
            }
            private:
            Container _con;  // 使用模板类型参数指定容器类型
        };
}

#include <iostream>
#include <stack>  
#include <queue>  
#include <vector>  
#include <list>  
#include <algorithm>  
#include <functional>  
using namespace std;
namespace hxq
{
    template<class T, class Container = std::deque<T>>  // 定义模板类 hxq，可以指定 T 类型和 Container 容器类型（默认为 deque）
    class hxq
    {
    public:
        void push(const T& x)  // 将元素插入容器
        {
            _con.push_back(x);  // 使用容器的 push_back() 方法
        }
        void pop()  // 删除容器中的第一个元素
        {
            _con.pop_front();  // 使用容器的 pop_front() 方法
        }
        T& back()  // 访问容器中最后一个元素
        {
            return _con.back();  // 使用容器的 back() 方法
        }
        T& front()  // 访问容器中第一个元素
        {
            return _con.front();  // 使用容器的 front() 方法
        }
        const T& back() const  // 访问容器中最后一个元素（常量引用版本，用于 const 对象）
        {
            return _con.back();
        }
        const T& front() const  // 访问容器中第一个元素（常量引用版本，用于 const 对象）
        {
            return _con.front();
        }
        bool empty()  const  // 判断容器是否为空
        {
            return _con.empty();  // 使用容器的 empty() 方法
        }
        size_t size() const  // 返回容器中元素的个数
        {
            return _con.size();  // 使用容器的 size() 方法
        }
    private:
        Container _con;  // 使用模板类型参数指定容器类型
    };
}

#include <iostream> 
#include <stack>  
#include <queue>  
#include <vector> 
#include <list>  
#include <algorithm> 
#include <functional>  
using namespace std;
namespace hxq
{
    template<class T, class Container = vector<T>, class Compare = std::less<T>>
        // 优先队列类 hxq，可以指定 T 类型和 Container 容器类型（默认为 vector），Compare类型默认为小于号比较
        class priority_queue
        {
            public:
            priority_queue()
            {}
            // 模板构造函数，可以使用迭代器区间初始化堆容器
            template <class InputIterator>
                priority_queue(InputIterator first, InputIterator last)
            {
                while (first != last)
                {
                    _con.push_back(*first);  // 将元素插入容器
                    ++first;
                }
                // 建堆，从最后一个非叶节点开始，自底向上调整直至节点0
                for (int i = (_con.size()-1-1)/2; i >= 0; --i)
                {
                    adjust_down(i);
                }
            }
            // 对 child 所在的节点进行向上调整操作，维护堆的性质
            void adjust_up(size_t child)
            {
                Compare com;  // 定义比较方式
                size_t parent = (child - 1) / 2;  // 计算父节点的下标
                while (child > 0)  // 当 child 不为堆顶节点时，不断向上调整
                {
                    if (com(_con[parent], _con[child]))  // 如果父节点小于子节点，则进行交换操作
                    {
                        std::swap(_con[child], _con[parent]);
                        child = parent;
                        parent = (child - 1) / 2;
                    }
                    else  // 否则跳出循环
                    {
                        break;
                    }
                }
            }
            // 往优先队列中插入元素 x，并进行向上调整操作
            void push(const T& x)
            {
                _con.push_back(x);  // 插入元素
                adjust_up(_con.size() - 1);  // 向上调整
            }
            // 对 parent 所在的节点进行向下调整操作，维护堆的性质
            void adjust_down(size_t parent)
            {
                Compare com;  // 定义比较方式
                size_t child = parent * 2 + 1;  // 计算左孩子节点的下标
                while (child < _con.size())  // 当左孩子存在时，不断向下调整
                {
                    // 选出左右孩子中较大（或较小）的那一个
                    if (child + 1 < _con.size() && com(_con[child],_con[child + 1]))
                    {
                        ++child;
                    }
                    if (com(_con[parent],_con[child]))  // 如果父节点小于子节点，则进行交换操作
                    {
                        std::swap(_con[child], _con[parent]);
                        parent = child;
                        child = parent * 2 + 1;
                    }
                    else  // 否则跳出循环
                    {
                        break;
                    }
                }
            }
            // 弹出堆顶元素，并在弹出之前进行向下调整操作
            void pop()
            {
                std::swap(_con[0], _con[_con.size() - 1]);  // 将堆顶元素和最后一个元素交换
                _con.pop_back();  // 弹出最后一个元素
                adjust_down(0);  // 向下调整堆顶节点
            }
            // 返回优先队列中堆顶元素的引用
            const T& top()
            {
                return _con[0];
            }
            // 判断容器是否为空
            bool empty()  const
            {
                return _con.empty();
            }
            // 返回容器中元素的个数
            size_t size() const
            {
                return _con.size();
            }
            private:
            Container _con;  // 使用模板类型参数指定容器类型
        };
}