stack,queue,priority_queue的模拟实现及常用接口

#include<queue>
#include<iostream>
#include<list>
using namespace std;
int main()
{
	priority_queue<int> s1;
	s1.push(5);
	s1.push(3);
	s1.push(7);
	s1.push(2);
	s1.push(6);
	while (!s1.empty())
	{
		cout <<s1.top()<<" ";
		s1.pop();
	}
	return 0;
}

3.2 priority_queue的模拟实现

priority_queue的底层就是一个堆，因此它的模拟实现，和堆的类似

#include<vector>
namespace chuxin
{
	// 默认是大堆
	template<class T, class Container = vector<T>>
	class priority_queue
	{
	public:
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (_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;

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

				if (_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;
	};
}

这种方法还是有缺陷，发现只能排降序，有没有一种方法既能排升序又能排降序？这时候就需要仿函数了

3.3 仿函数

来看看下面这段冒泡排序

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		// 单趟
		int flag = 0;
		for (int i = 1; i < n - j; i++)
		{
			if (a[i] < a[i - 1])
			{
				swap(a[i - 1], a[i]);
				flag = 1;
			}
		}

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

发现它的逻辑是排一个升序，如果要排一个降序怎么办，为了一个比较重载一个大部分相似的函数，显然不怎么好，而且比较的数据可能不同，有时候比较整形，有时候是浮点型，这时候就可以利用模版自己写一个比较函数，而这个函数称为仿函数

// 仿函数：本质是一个类，这个类重载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;
}

此时就发现，改变是否是升降序，就可以利用两个类对象就可以做到，此时priority_queue的比较就是这样

#include<vector>
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;
	}
};
namespace chuxin
{
	// 默认是大堆
	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;
	};
}