【C++】stack和queue

#include<deque>
namespace zlr
{
template<class T, class Container = deque<T>>
class stack
{
public:
    void push(const T& x)
    {
        _con.push_back(x);
    }

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

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

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

    bool empty() const
    {
        return _con.empty();
    }

private:
    Container _con;//自定义对象调用自己的析构和构造函数，我们不需要写
};

}

#include<deque>
#include <list>
namespace zlr
{
template<class T, class Container = deque<T>>
class queue
{
public:
    void push(const T& x)
    {
        _con.push_back(x);
    }

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

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

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

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

    bool empty() const
    {
        return _con.empty();
    }

private:
    Container _con;
};
}

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

 //仿函数：本质是一个类，这个类重载operator(),他的对象可以像函数一样使用
template<class T>
class Less//仿函数
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

template<class T>
class Greater//仿函数
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

 //< 升序
 //> 降序
template<class Compare>
void BubbleSort(int* a, int n, Compare com)
{
	for (int j = 0; j < n; j++)
	{
		// 单趟
		int flag = 0;
		for (int i = 1; i < n - j; i++)
		{
			//if (a[i] < a[i - 1])
			if (com(a[i], a[i - 1]))//通过仿函数，这里的比较逻辑
			{	                    //我们就可以通过传比较器（仿函数）控制
				swap(a[i - 1], a[i]);
				flag = 1;
			}
		}

		if (flag == 0)
		{
			break;
		}
	}
}

int main()
{
	Less<int> LessFunc;
	Greater<int> GreaterFunc;
	// 函数对象
	cout << LessFunc(1, 2) << endl;//仿函数的类可以像函数一样使用
	cout << LessFunc.operator()(1, 2) << endl;

	int a[] = { 9,1,2,5,7,4,6,3 };
	BubbleSort(a, 8, LessFunc);//传入比较器（仿函数）控制内部的比较逻辑
	BubbleSort(a, 8, GreaterFunc);

	BubbleSort(a, 8, Less<int>());//上面的使用方法太麻烦，这里可以使用匿名对象
	BubbleSort(a, 8, Greater<int>());

	return 0;
}

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 Date
{
	friend ostream& operator<<(ostream& _cout, const Date& d);
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);
	}
private:
	int _year;
	int _month;
	int _day;
};

ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day;
	return _cout;
}

class DateLess
{
public:
	bool operator()(Date* p1, Date* p2)
	{
		return *p1 < *p2;
	}
};

	// 1、类类型不支持比较大小
	// 2、支持比较大小，但是比较的逻辑不是你想要的
	// 需要自己实现仿函数

	priority_queue<Date*, vector<Date*>, DateLess> q2;
	priority_queue<Date*> q2;
	q2.push(new Date(2018, 10, 29));
	q2.push(new Date(2018, 10, 28));
	q2.push(new Date(2018, 10, 30));
	cout << *q2.top() << endl;
	q2.pop();

	cout << *q2.top() << endl;
	q2.pop();

	cout << *q2.top() << endl;
	q2.pop();

	priority_queue<int*> q3;
	q3.push(new int(2));
	q3.push(new int(1));
	q3.push(new int(3));

	cout << *q3.top() << endl;
	q3.pop();

	cout << *q3.top() << endl;
	q3.pop();

	cout << *q3.top() << endl;
	q3.pop();

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

namespace zlr
{
	// 默认是大堆
	template<class T, class Container = vector<T>, class Compare = Less<T>>
	class priority_queue
	{
	public:
		void AdjustUp(int child)//向上调整算法
		{
			Compare com;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void push(const T& x)
		{
			_con.push_back(x);

			AdjustUp(_con.size() - 1);
		}

		void AdjustDown(int parent)//向下调整算法
		{
			// 先假设左孩子小
			size_t child = parent * 2 + 1;

			Compare com;
			while (child < _con.size())  // child >= n说明孩子不存在，调整到叶子了
			{
				// 找出小的那个孩子
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++child;
				}

				//if (_con[parent] < _con[child])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

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

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

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

		bool empty() const
		{
			return _con.empty();
		}

	private:
		Container _con;
	};
}