关于标准库中的 stack / queue / 优先级队列(涉及部分仿函数，deque）

    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()
		{
			return _con.back();
		}

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

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

	private:
		Container _con;
	};

2.queue的介绍

翻译：

• 1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。

• 2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

• 3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

??? ?????empty ：检测队列是否为空

???????? size ：返回队列中有效元素的个数

??????? ?front ：返回队头元素的引用

?????? ??back ：返回队尾元素的引用

???????? push_back ：在队列尾部入队列

????? ???pop_front ：在队列头部出队列

• 4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

    //适配器模式/配接器
	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()
		{
			return _con.front();
		}

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

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

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

	private:
		Container _con;
	};

3.优先级队列（堆）

priority_queue的文档介绍

• 1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

• 2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。

• 3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

• 4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

priority_queue的使用

#include <iostream>

#include <vector>

#include <functional>

#include <queue>

using namespace std;


int main()
{
	vector<int> v{3, 7, 4, 2, 5, 6, 8, 9, 1, 0};

	//默认大堆
	priority_queue<int> pq;   

	//大于仿函数 - 小堆
	//priority_queue<int, vector<int>, greater<int>> pq;  

	for (auto e : v)
	{
		pq.push(e);
	}
	
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;

	return 0;
}

大堆输出：

小堆输出：

接口实现：

	template<class T, class Container = vector<T>>
	class priority_queue
	{
	public:

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

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

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

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

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


	private:
		Container _con;
	};

堆的插入: (演示图表为小堆）

代码实现：向上调整

        void Adjust_up(int child)
		{
			int parent = (child - 1) / 2;

			while (child > 0)
			{
				if (_con[child] > _con[parent])
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

堆的删除：(演示图表为小堆）

代码实现：向下调整

		void Adjust_down(int parent)
		{
			size_t child = parent * 2 + 1;

			while (child < _con.size())
			{
				//child + 1 < _con.size() 是为了防止右孩子越界
				if (child + 1 < _con.size() && _con[child + 1] > _con[child]) 
				{
					child++;
				}

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

			}

		}

完整代码：

????????????????????????????????????????????????????????????????????????????????????????????????priority_queue.h? 初始版本

	template<class T, class Container = vector<T>>
	class priority_queue
	{
	public:
		// 向上调整
		void Adjust_up(int child)
		{
			int parent = (child - 1) / 2;

			while (child > 0)
			{
				if (_con[child] > _con[parent])
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

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

		//向下调整
		void Adjust_down(int parent)
		{
			size_t child = parent * 2 + 1;

			while (child < _con.size())
			{
				//child + 1 < _con.size() 是为了防止右孩子越界
				if (child + 1 < _con.size() && _con[child + 1] > _con[child]) 
				{
					child++;
				}

				if (_con[child] > _con[parent])
				{
					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();
			Adjust_down(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()
	{
		vector<int> v{3, 7, 4, 2, 5, 6, 8, 9, 1, 0};

		//默认大堆
		priority_queue<int> pq;   

		for (auto e : v)
		{
			pq.push(e);
		}

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

运行结果：

? ? ? ? ?至此，完成priority_queue初始版本，但是这里存在一个问题，以上代码默认实现的是大堆，那如何修改为小堆呢？每次去修改向上/向下调整代码也能实现，但是太过繁琐，而在 stl 库里面，这里运用了一个语法：传入第三个模板参数---仿函数

进阶完整版代码如下：

????????????????????????????????????????????????????????????????????????????????????????????????????????priority_queue.h

#pragma once

namespace dwr
{
	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 T, class Container = vector<T>, class Comapre = less<T>>
	class priority_queue
	{
	public:
		// 向上调整
		void Adjust_up(int child)
		{
			Comapre com;

			int parent = (child - 1) / 2;

			while (child > 0)
			{
				//if (_con[child] > _con[parent])
				if(com(_con[parent], _con[child]))  // 注意： 默认是less 小于
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

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

		//向下调整
		void Adjust_down(int parent)
		{
			Comapre com;

			size_t child = parent * 2 + 1;

			while (child < _con.size())
			{
				//child + 1 < _con.size() 是为了防止右孩子越界
				//if (child + 1 < _con.size() && _con[child + 1] > _con[child]) 
				if (child + 1 < _con.size() 
					&& Comapre()( _con[child] , _con[child + 1])) //这里是匿名对象调用operator[]
				{
					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();
			Adjust_down(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()
	{
		vector<int> v{3, 7, 4, 2, 5, 6, 8, 9, 1, 0};

		//大于仿函数 - 小堆
		priority_queue<int, vector<int>, greater<int>> pq;

		for (auto e : v)
		{
			pq.push(e);
		}

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

}

????????????????????????????????????????????????????????????????????????????????????????????????????????????????test.cpp

#include <iostream>

#include <vector>

#include <functional>

#include <queue>

using namespace std;

#include "priority_queue.h"


int main()
{
	dwr::test_priority_queue();

	return 0;
}

例：

STL标准库中stack和queue的底层结构

? ? ? ? ? ? ? ? ? ??

deque的简单介绍

deque的缺陷

为什么选择deque作为stack和queue的底层默认容器？

????????1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。

????????2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

以上仅代表个人观点，欢迎讨论