stack和queue和优先级队列（大堆和小堆）模拟实现和仿函数讲解

• 1.适配器简单了解
• 2.stack模拟实现
• 2.queue模拟实现
• 3.优先级队列
• 4.仿函数

当我们写stack之前我们先来简单了解下适配器，就以我们手机充电为例子，大家都知道我们家用电是220，手机充电有个充电线，而手机充电的电源适配器，用不了那么高的电，会相应的降低，这样子会没有那么危险，而适配器最重要的作用是转换，转换成我想要的东西

写之前我们就要用到stack的适配器了，deque有了它实现栈就特别简单了，栈是先进后出

#pragma once

namespace stk
{
	template>
	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;

	};

	void test_stack()
	{
		stack s;
		//stack> s;
		//stack> s;
		//stack s; // 

		s.push(1);
		s.push(2);
		s.push(3);
		s.push(4);
		s.push(300);

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

};

这样子就写完了，可以看到写栈的代码特别简单，而且少，也好理解，因为写这个栈只要调用库里面封装好的函数就行了
上面test的代码
stack s;
stack s;
stack s;
stack s;
这些不同类型的都可以运行不会报错，
除了 stack s; 为什么呢？
运行报告

会出现截断或者溢出的问题

和栈不一样的是先进先出

#pragma once

namespace que
{
	template>
	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;
	};

	void test_queue()
	{
		//queue q;
		queue> q;
		//queue> q; // 不行

		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);

		while (!q.empty())
		{
			cout << q.front() << " ";
			q.pop();
		}
		cout << endl;
	}
}

这里要注意的是vector是不支持的，因为vector不支持头删

优先级队列我放在队列后面的

	// 优先级队列 -- 大堆 <  小堆 >
	template>
	class priority_queue
	{
	public:
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (_con[parent] < _con[child])
				{
					swap(_con[parent], _con[child]);
					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())
			{
				if (child+1 < _con.size() && _con[child] < _con[child+1])				
				{
					++child;
				}

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

		void pop()
		{
			assert(!_con.empty());
			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;
	};

	void test_priority_queue()
	{
		priority_queue pq;
		pq.push(2);
		pq.push(5);
		pq.push(1);
		pq.push(6);
		pq.push(8);

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

这样子就可以了，但是这样子控制大堆或者小堆就很麻烦，这个时候我们就用仿函数
仿函数其实是赋值来的但是看起来很像函数

	template
	struct less
	{
		bool operator()(const T& x, const T& y) const
		{
			return x < y;
		}
	};

	template
	struct greater
	{
		bool operator()(const T& x, const T& y) const
		{
			return x > y;
		}
	};

我们在模板里面加上greater，再把向上调整，和向下调整改下，我们就是小堆
代码

	template
	struct less
	{
		bool operator()(const T& x, const T& y) const
		{
			return x < y;
		}
	};

	template
	struct greater
	{
		bool operator()(const T& x, const T& y) const
		{
			return x > y;
		}
	};

	// 优先级队列 -- 大堆 <  小堆 >
	template, class Compare = less>
	class priority_queue
	{
	public:
		void AdjustUp(int child)
		{
			Compare comFunc;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (comFunc(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					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)
		{
			Compare comFunc;
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				//if (child+1 < _con.size() && _con[child] < _con[child+1])
				if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1]))
				{
					++child;
				}

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

		void pop()
		{
			assert(!_con.empty());
			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;
	};

	void test_priority_queue()
	{
		

		//priority_queue pq;
		priority_queue, greater> pq;

		pq.push(2);
		pq.push(5);
		pq.push(1);
		pq.push(6);
		pq.push(8);

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

运行结果

我们不加上greator，因为我们默认是less是大堆

仿函数的优点是用来代替函数指针
因为c++是c衍生过来的，所以c++是会支持c的用法
下面为了支持函数指针为什么怎么写，如果不指定函数地址，那么就会调用构造函数，如果没有写构造函数就是随机值，写了如果没有函数的地址，那么指向的就是空指针，那么函数的地址是什么，函数名就可以当函数的地址，所以才有了下面的写法

	priority_queue, bool(*)(int, int)> pq(ComIntLess);

	// 优先级队列 -- 大堆 <  小堆 >
	template, class Compare = less>
	class priority_queue
	{
		Compare _comFunc;
	public:
		priority_queue(const Compare& comFunc = Compare())
			:_comFunc(comFunc)
		{}

		void AdjustUp(int child)
		{
			//Compare comFunc;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (_comFunc(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					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)
		{
			//Compare comFunc;
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				//if (child+1 < _con.size() && _con[child] < _con[child+1])
				if (child + 1 < _con.size() && _comFunc(_con[child], _con[child + 1]))
				{
					++child;
				}

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

		void pop()
		{
			assert(!_con.empty());
			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;
	};

	bool ComIntLess(int x1, int x2)
	{
		return x1 > x2;
	}

	void test_priority_queue()
	{
		//priority_queue, greater> pq;
		//priority_queue> pq;
		priority_queue, bool(*)(int, int)> pq(ComIntLess);


		pq.push(2);
		pq.push(5);
		pq.push(1);
		pq.push(6);
		pq.push(8);

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

-

运行结果
如果没用函数指针默认就是大堆，因为之前用仿函数实现了，如果用函数指针实现大堆和上面实现小堆一样，其实可以看的出来函数指针比起仿函数来讲真的是麻烦太多了

接下来要比较下面的代码怎么用sort来比较

// 商品
struct Goods
{
	string _name;
	double _price;
	size_t _saleNum;
};



void test_goods()
{
	Goods gds[4] = { { "苹果", 2.1, 1000}, { "香蕉", 3.0, 200}, { "橙子", 2.2,300}, { "菠萝", 1.5,50} };
}

这样子？

看到报错了，要比较可以用operator<

可以看到没有问题了，但是这只能比较价格啊，要是我想比较其他怎么办？而且继续用operator也不行因为只有一个相同的参数，也构不成函数重载。
这个时候就要看仿函数了

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#include"stack.h"
#include"queue.h"

// 商品
struct Goods
{
	string _name;
	double _price;
	size_t _saleNum;

	//bool operator<(const Goods& g) const
	//{
	//	return _price < g._price;
	//}
};

struct LessPrice
{
	bool operator()(const Goods& g1, const Goods& g2) const
	{
		return g1._price < g2._price;
	}
};

struct GreaterPrice
{
	bool operator()(const Goods& g1, const Goods& g2) const
	{
		return g1._price > g2._price;
	}
};

struct LessSaleNum
{
	bool operator()(const Goods& g1, const Goods& g2) const
	{
		return g1._saleNum < g2._saleNum;
	}
};


struct GreaterSaleNum
{
	bool operator()(const Goods& g1, const Goods& g2) const
	{
		return g1._saleNum > g2._saleNum;
	}
};



void test_goods()
{
	int i = 0;
	Goods gds[4] = { { "苹果", 2.1, 1000}, { "香蕉", 3.0, 200}, { "橙子", 2.2,300}, { "菠萝", 1.5,50} };
	sort(gds, gds + 4, LessPrice());
	for (i = 0; i < 4; i++)
	{
		cout << gds[i]._name << " ";
		cout << gds[i]._price << " ";
		cout << gds[i]._saleNum << " ";
	}
	cout << endl;
	sort(gds, gds + 4, GreaterPrice());
	for (i = 0; i < 4; i++)
	{
		cout << gds[i]._name << " ";
		cout << gds[i]._price << " ";
		cout << gds[i]._saleNum << " ";
	}
	cout << endl;
	sort(gds, gds + 4, LessSaleNum());
	for (i = 0; i < 4; i++)
	{
		cout << gds[i]._name << " ";
		cout << gds[i]._price << " ";
		cout << gds[i]._saleNum << " ";
	}
	cout << endl;
	sort(gds, gds + 4, GreaterSaleNum());
	for (i = 0; i < 4; i++)
	{
		cout << gds[i]._name << " ";
		cout << gds[i]._price << " ";
		cout << gds[i]._saleNum << " ";
	}
	cout << endl;
}


int main()
{
	test_goods();
	return 0;
}

运行结果
可以看到很舒服，想比较什么就调用什么