C++初阶-stack/queue/priority_queue的使用和模拟

class MyQueue {
public:
    MyQueue() {
//不需要写什么，对于自定义类型stack会自动调用其构造函数
    }
    
    void push(int x) {
        //入栈栈入数据
        st1.push(x);
    }
    
    int pop() {
        int ret;
        //出栈栈有无数据
        if(!st2.empty())
        {
            ret=st2.top();
            st2.pop();
            return ret;
        }
        else
        {
            //将数据入栈出栈
            while(!st1.empty())
            {
                st2.push(st1.top());
                st1.pop();
            }
            //pop数据
            ret=st2.top();
            st2.pop();
            return ret;
        }
    }
    
    int peek() {
        if(!st2.empty())
        {
            return st2.top();
        }
        else
        {
            while(!st1.empty())
            {
                st2.push(st1.top());
                st1.pop();
            }
            return st2.top();
        }
    }
    
    bool empty() {
        return st1.empty()&&st2.empty();
    }
    private:
    stack<int> st1;
    stack<int> st2;
};

class MyStack {
public:
    MyStack() {

    }
    
    void push(int x) {
        //入有数据队列
        if(q1.empty())
        {
            q2.push(x);
        }
        else
        {
            q1.push(x);
        }
    }
    
    int pop() {
        //确定哪个队列有数据
        queue<int>*q=&q1;
        queue<int>*nonq=&q2;
        if(q1.empty())
        {
            q=&q2;
            nonq=&q1;
        }
        //出队列再入队列
        while(q->size()>1)
        {
            nonq->push(q->front());
            q->pop();
        }
        //pop数据
        int ret=q->front();
        q->pop();
        return ret;
    }
    
    int top() {
        if(!q1.empty())
        {
            return q1.back();
        }
        else
        {
            return q2.back();
        }
    }
    
    bool empty() {
        return q1.empty()&&q2.empty();
    }
    private:
    queue<int> q1;
    queue<int> q2;
};

#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;
	// 堆排序输出数据
	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}cout << endl;
	while (!q2.empty())
	{
		cout << q2.top() << " ";
		q2.pop();
	}cout << 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 TestPriorityQueue2()
{
	// 大堆，需要用户在自定义类型中提供<的重载
	priority_queue<Date> q1;
	q1.push(Date(2021, 10, 19));
	q1.push(Date(2021, 10, 29));
	q1.push(Date(2021, 12, 16));
	q1.push(Date(2021, 8, 18));
	q1.push(Date(2021, 9, 15));
	cout << q1.top() << endl;
	// 如果要创建小堆，需要用户提供>的重载
	priority_queue<Date, vector<Date>, greater<Date>> q2;
	q2.push(Date(2021, 10, 19));
	q2.push(Date(2021, 10, 29));
	q2.push(Date(2021, 12, 16));
	q2.push(Date(2021, 8, 18));
	q2.push(Date(2021, 9, 15));
	cout << q2.top() << endl;
	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}cout << endl;
	while (!q2.empty())
	{
		cout << q2.top() << " ";
		q2.pop();
	}cout << endl;
}

namespace cole
{
	template<class T,class Container=std::deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			con.push_back(x);
		}

		void pop()
		{
			con.pop_back();
		}

		const T& top()
		{
			return con.back();
		}

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

		bool empty()
		{
			return con.empty();
		}
	private:
		Container con;
	};
}

namespace cole
{
	template<class T,class Container=std::deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			con.push_back(x);
		}

		void pop()
		{
			con.pop_front();
		}

		const T& front()
		{
			return con.front();
		}

		const T& back()
		{
			return con.back();
		}

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

		bool empty()
		{
			return con.empty();
		}
	private:
		Container con;
	};
}

namespace cole
{
	//仿函数-函数对象（该类对象可以像函数一样使用）
	template<class T>
	struct less
	{
		bool operator()(const T& a, const T& b)
		{
			return a < b;
		}
	};
	template<class T>
	struct greater
	{
		bool operator()(const T& a, const T& b)
		{
			return a > b;
		}
	};

	template<class T,class Container=std::deque<T>,class Compare=less<T>>//默认大堆
	class priority_queue
	{
	public:
		//向上调整数据
		void Adjustup(size_t child)
		{
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				//是否调整
				if (cmp(con[parent], con[child]))
				{
					swap(con[child], con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		//向下调整数据
		void Adjustdown(size_t parent)
		{
			size_t child = parent * 2 + 1;
			while (child < con.size())
			{
				//比较左右子节点
				if (child + 1 < con.size() && cmp(con[child], con[child + 1]))
				{
					++child;
				}
				//是否调整
				if (cmp(con[parent], con[child]))
				{
					swap(con[child], con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void push(const T& x)
		{
			con.push_back(x);
			Adjustup(con.size() - 1);
		}

		void pop()
		{
			swap(con[0], con[con.size() - 1]);
			con.pop_back();
			Adjustdown(0);
		}

		const T& top()
		{
			return con[0];
		}

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

		bool empty()
		{
			return con.empty();
		}
	private:
		Container con;
		Compare cmp;
	};
}