【C++】 世界里的 “秩序双雄”：stack 和 queue ！把 stack 想象成时光回溯胶囊，新记忆后入先取；queue 仿若忙碌流水线，任务依次稳步推进。

stack<int> s1;

class MinStack {
public:
    MinStack() {
    }
    
    void push(int val) {
        //插入到st栈
        st.push(val);
        //mak空栈 || val 小于 mak栈顶
         if(mak.empty() || val <= mak.top())
         {
            //插入到mak栈
            mak.push(val);
         }
    }
    
    void pop() {
        //st和mak栈顶相同---一起出栈
        if(st.top() == mak.top())
        {
            mak.pop();
        }
        st.pop();
    }   
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        //mak栈顶就是最小的数值了
        return mak.top();
    }
private:
   stack<int> st;
   stack<int> mak;

};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        size_t pushi = 0,popi = 0;
        //栈用来存放pushV的数据
        stack<int> st;
        while(pushi < pushV.size())
        {
            //把pushV入栈
            st.push(pushV[pushi++]);
            //st不能为空 && st栈顶等于popV[popi]
            while(!st.empty() && st.top() == popV[popi])
            {
                popi++;
                //等于就出栈
                st.pop();
            }
        }
        //栈里没有数据了，就说明所有数字都相等，返回true
        return st.empty();

    }
};

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
       stack<int> s1;
       for(auto& e:tokens)
       {
          
          if("+" == e || "-"== e||"*"== e|| "/"== e)
          {
            //操作符

            //取栈顶的2个元素
            int right = s1.top();
            s1.pop();
            int left = s1.top();
            s1.pop();
                //进行运算
                switch(e[0])
                {
                case '+':
                    s1.push(left + right);
                    break;
                case '-'://必须用后面的运算结果-去前面的数值
                    s1.push(left - right);
                    break;
                case '*':
                    s1.push(left * right);
                    break;
                case '/':
                    s1.push(left / right);
                    break;
                }

          }
          else
          {
            //不是操作符入栈
             s1.push(stoi(e));
          }
       }
       return s1.top();
    }
};

class MyQueue {
public:
    MyQueue() {
        
    }
// 入队操作：将元素 x 添加到队列尾部
    void push(int x) {
        // 将元素 x 压入栈 st 中
        // 由于栈是后进先出（LIFO），所以新元素会位于栈顶
        st.push(x);
    }

    // 出队操作：移除并返回队列头部的元素
    int pop() {
        // 如果 mak 栈为空，需要将 st 中的元素全部转移到 mak 中
        if (mak.empty()) {
            add(); // 调用辅助函数将 st 中的元素转移到 mak 中
        }
        // 现在 mak 的栈顶元素就是队列头部的元素
        int x = mak.top(); // 获取队列头部的元素
        mak.pop();         // 移除 mak 栈顶元素，相当于移除队列头部元素
        return x;          // 返回队列头部的元素
    }

    // 查看队列头部的元素（不移除）
    int peek() {
        // 如果 mak 栈为空，需要将 st 中的元素全部转移到 mak 中
        if (mak.empty()) {
            add(); // 调用辅助函数将 st 中的元素转移到 mak 中
        }
        // 返回 mak 栈顶元素，即队列头部的元素
        return mak.top();
    }

    // 检查队列是否为空
    bool empty() {
        // 队列为空当且仅当两个栈都为空
        return st.empty() && mak.empty();
    }

private:
    // 辅助函数：将 st 中的所有元素转移到 mak 中
    void add() {
        // 当 st 不为空时，持续将 st 的栈顶元素压入 mak 中
        while (!st.empty()) {
            mak.push(st.top()); // 将 st 的栈顶元素压入 mak 中
            st.pop();           // 移除 st 的栈顶元素
        }
    }
   stack<int> st;
   stack<int> mak;
};

#pragma once
#include<iostream>
#include<vector>
//模拟实现栈
using namespace std;
namespace bit
{
	template<class T, class container = vector<T>>
	class stack
	{
	public:
		//尾插
		void push(const T& x)
		{
			//直接调用vectit的尾插就行了
			_con.push_back(x);
		}
		//出栈-直接调用vectit的尾删
		void pop()
		{
			_con.pop_back();
		}
		//取栈顶-直接调用通用的接口 bakc
		T& top()
		{
			return _con.back();
		}
		const T& top()const
		{
			return _con.back();
		}
		//有效个数
		size_t size()
		{
			return _con.size();
		}
		//判断是否为空
		bool empty()
		{
			return _con.empty();
		}


	private:
		//vectit-list
		container _con;
	};
}

#include<iostream>
#include"stack.h"
int main()
{
	//bit::queue<int> st;
	bit::stack<int, list<int>> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	cout << "size:" << st.size() << endl;
	while (!st.empty())
	{
		cout << st.top() << endl;
		st.pop();
	}
}

queue<int> q1;

class MyStack {
public:
// 两个队列：
    // queue1 用于存储栈的元素
    // queue2 作为辅助队列，在 push 操作中用于重新排列元素
    queue<int> queue1;
    queue<int> queue2;

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

    }

    // 入栈操作：将元素 x 压入栈顶
    void push(int x) {
        // 将新元素 x 压入辅助队列 queue2 中
        queue2.push(x);

        // 将 queue1 中的所有元素依次出队并压入 queue2 中
        // 这样，queue2 中的元素顺序将被反转，模拟栈的 LIFO 特性
        while (!queue1.empty()) {
            queue2.push(queue1.front()); // 将 queue1 的队首元素压入 queue2
            queue1.pop();                 // 移除 queue1 的队首元素
        }

        // 交换 queue1 和 queue2，使得 queue1 始终存储栈的元素
        swap(queue1, queue2);
    }

    // 出栈操作：移除并返回栈顶的元素
    int pop() {
        // 检查 queue1 是否为空
        if (queue1.empty()) {
            // 如果 queue1 为空，说明栈中没有元素，抛出异常或处理错误
            throw std::out_of_range("Stack is empty");
        }

        // 获取 queue1 的队首元素，即栈顶元素
        int r = queue1.front();
        queue1.pop(); // 移除 queue1 的队首元素，相当于移除栈顶元素
        return r;     // 返回栈顶元素
    }

    // 获取栈顶元素
    int top() {
        // 检查 queue1 是否为空
        if (queue1.empty()) {
            // 如果 queue1 为空，说明栈中没有元素，抛出异常或处理错误
            throw std::out_of_range("Stack is empty");
        }

        // 返回 queue1 的队首元素，即栈顶元素
        return queue1.front();
    }

    // 检查栈是否为空
    bool empty() {
        // 栈为空当且仅当 queue1 为空
        return queue1.empty();
    }
};

#pragma once
#include<iostream>
#include<list>
#include<vector>
using namespace std;

namespace bit
{
    // 使用命名空间 bit 封装自定义队列类

    // 泛型队列类模板
    // T: 队列中元素的类型
    // container: 用于存储队列元素的容器类型，默认为 std::list<T>
    template<class T, class container = std::list<T>>
    class queue {
    public:
        // 构造函数
        queue() {
            // 默认构造函数，不需要初始化，因为容器默认构造
        }

        // 入队列操作：将元素 x 添加到队列尾部
        void push(const T& x) {
            _con.push_back(x); // 使用容器的 push_back 方法将元素添加到尾部
        }

        // 出队列操作：移除队列头部的元素
        void pop() {
            _con.pop_front(); // 使用容器的 pop_front 方法移除头部元素
        }

        // 获取队列尾部的元素（引用）
        T& back() {
            return _con.back(); // 使用容器的 back 方法获取尾部元素
        }

        // 获取队列尾部的元素（常量引用）
        const T& back() const {
            return _con.back(); // 常量版本，用于常量对象
        }

        // 获取队列头部的元素（引用）
        T& front() {
            return _con.front(); // 使用容器的 front 方法获取头部元素
        }

        // 获取队列头部的元素（常量引用）
        const T& front() const {
            return _con.front(); // 常量版本，用于常量对象
        }

        // 获取队列中有效元素的个数
        size_t size() {
            return _con.size(); // 使用容器的 size 方法获取元素个数
        }

        // 检查队列是否为空
        bool empty() {
            return _con.empty(); // 使用容器的 empty 方法检查是否为空
        }

    private:
        // 私有成员变量：用于存储队列元素的容器
        container _con;
    };
}

#include <iostream>    
#include "queue.h" 

int main() {
    // 创建一个 bit::queue<int> 类型的队列对象 st，用于存储整数类型的元素
    bit::queue<int> st;

    // 入队操作：将整数 1, 2, 3, 4 依次压入队列 st 中
    st.push(1); 
    st.push(2); 
    st.push(3); 
    st.push(4);

    // 输出队列的大小，即当前队列中元素的数量
    std::cout << "size:" << st.size() << std::endl; // 输出: size:4

    // 循环遍历队列，直到队列为空
    while (!st.empty()) 
    {
        // 输出队列头部的元素（最先进入队列的元素）
        std::cout << st.front() << std::endl; // 依次输出: 1, 2, 3, 4

        // 出队操作：移除队列头部的元素
        st.pop();
    }
    return 0; 
}

//小于比较的仿函数
template<class T>
class less
{
public:
	bool operator()
	{
		return x < y;
	}
};

//大于比较的仿函数
template<class T>
class greater
{
public:
	bool operator()
	{
		return x > y;
	}
};

#include <vector>
  #include <queue>
  #include <functional>   // greater算法的头文件
  
  void TestPriorityQueue()
 {
 // 默认情况下，创建的是大堆，其底层按照小于号比较
 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;
 }

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;
}

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

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

namespace bit
{
	//仿函数
	template<class T>
	struct less
	{
		bool operator()(const T& x, const T&y)const
		{
			return x < y;
		}
	};
	template<class T>
	struct greater
	{
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};
	
	template<class T, class container = vector<T>,class compare = greater<T>>
	class priority_queue
	{
	public:
		//强制生成默认构造
		priority_queue() = default;
		//迭代器区间
		template<class InputIterator>
		priority_queue(InputIterator a1, InputIterator a2)
			:_con(a1,a2)
		{
			for (int i = (_con.size()-1-1)/2; i >= 0 ; i--)
			{
			    //向上调整
				upwards(i);
			}
		}


		//向上调整算法
		void upwards(int node)
		{
			//计算出父亲节点
			int sz = (node - 1) / 2;
			while (node > 0)
			{
				compare com;
				//比较，孩子节点大于父亲节点
				if (com(_con[node] , _con[sz]))
				{
					//交换
					swap(_con[node], _con[sz]);
					//父亲节点给node
					node = sz;
					//找出新的父亲节点
					sz = (sz - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		//入堆
		void push(const T& x)
		{
			_con.push_back(x);
			//向上调整算法
			upwards(_con.size() - 1);
		}

		//向下调整算法
		void downwards(int node)
		{
			compare com;
			//计算出左孩子节点
			int sz = (node * 2) + 1;
			while (sz < _con.size())
			{
				//判断左孩子和右孩子那个大
				if (sz+1 < _con.size() && com(_con[sz + 1] ,_con[sz]))
				{
					sz++;
				}
				if (com(_con[sz] , _con[node]))
				{
					//交换
					swap(_con[sz], _con[node]);
					//孩子节点给node
					node = sz;
					//计算下一个左孩子节点
					sz = (node * 2) + 1;
				}
				else
				{
					break;
				}
			}

		}
		//删除堆顶数据
		void pop()
		{
			//堆顶和堆的最后一个元素交换
			swap(_con[0], _con[_con.size() - 1]);
			//删除堆的最后一个元素
			_con.pop_back();
			//向下调整算法
			downwards(0);


		}

		size_t size()
		{
			return _con.size();
		}

		const T& top()//取堆顶数据
		{
			return _con[0];
		}
		bool empty()//判空
		{
			return _con.empty();
		}


	private:
		container _con;
	};
}

#include"priority_queue.h"
int main()
{
	//bit::priority_queue<int> pq;
	bit::priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(1);
	pq.push(2);
	pq.push(3);
	pq.push(4);
	pq.push(5);

	while (!pq.empty())
	{
		cout << pq.top() << endl;
		pq.pop();
	}

	return 0;
}

#include<deque>
namespace bite
{
	template<class T, class Con = deque<T>>
	//template<class T, class Con = vector<T>>
	//template<class T, class Con = list<T>>
	class stack
	{
	public:
		stack() {}
		void push(const T& x) { _c.push_back(x); }
		void pop() { _c.pop_back(); }
		T& top() { return _c.back(); }
		const T& top()const { return _c.back(); }
		size_t size()const { return _c.size(); }
		bool empty()const { return _c.empty(); }
	private:
		Con _c;
	};
}

#include<deque>
#include <list>
namespace bite
{
	template<class T, class Con = deque<T>>
	//template<class T, class Con = list<T>>
	class queue
	{
	public:
		queue() {}
		void push(const T& x) { _c.push_back(x); }
		void pop() { _c.pop_front(); }
		T& back() { return _c.back(); }
		const T& back()const { return _c.back(); }
		T& front() { return _c.front(); }
		const T& front()const { return _c.front(); }
		size_t size()const { return _c.size(); }
		bool empty()const { return _c.empty(); }
	private:
		Con _c;
	};
}