一.栈与队列的模拟实现

严格来说，栈与队列不像vector和list一样是容器，它是一种容器适配器。

什么是适配器？
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，这种模式是将一种接口转换为客户需要的另一种接口。

栈与队列就是根据客户需求，用vector或list等容器的功能转换而来的容器适配器。但其实库里默认实现它们的容器都是双端队列(deque)，但在此处我将用vector和list模拟实现栈与队列的基本接口。

1.stack

	template<class T,class Container = vector<T>>
	//栈可以用vector和list实现，默认用vector
	class stack
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		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;
	};

Container指实现stack的容器，这里给了缺省参数类型vector。栈的所有功能调vector的接口即可，而且这些接口一般能实现栈的容器都有。

2.queue

	template<class T,class Container = list<T>>
	//queue有头删，vector虽然可以用insert在头部插入，但还是用有专门头删的list好
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_front();
			//如果容器是vector，但这里是pop_front，明显是语法错误，但如果你不调用的话就不会报错
			//这也是按需实例化的结果
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
		const T& back()
		{
			return _con.back();
		}
		const T& front()
		{
			return _con.front();
		}
	private:
		Container _con;
	};

总结

对于栈来说，使用vector是优于list的。
1.尾插效率高：list和vector的尾插/删的时间复杂度都是O(1),但vector比list进行的指针操作少，并且不用开辟空间获取节点；
2.缓存利用率高：vector的底层是连续内存，读取栈顶数据时可以高效利用cpu缓存，明显比list的不连续内存好；
3.内存开销低 ：vector只需少量额外空间，而list的节点所需空间明显更多；
4.接口更匹配：vector 的 back()、push_back()、pop_back() 与栈语义完全匹配，无需处理链表指针，代码更简洁。

对于对列来说，list是要优于vector的。
最重要的原因就是头删效率高 ：list头删改一下节点的指向就好了(N(1))，而vector是要移动全部元素的(O(N))；

看完stack和queue的实现可以发现它们不能用vector或list的其中一个统一实现。那是否有其他的容器既可以实现栈也可以实现对列呢？有的，那就是双端队列deque。

二.双端队列deque

1.deque的介绍

deque是一种双开口的’'连续"空间结构。双开口：可以头插和尾插的时间复杂度都是O(1),与vector相比，它不需要移动数据；与list相比，它的空间利用率更高。

就像前面说的，vector适用于stack但不适合于queue，list使用于queue但不适于queue。为了创造一个即使配于stack也适配于queue的容器，deque就孕育而生，它有着list和stack的影子，虽然没有完全继承list和vector各自的全部有点，但是已经可以完美适配于stack和queue了。

2.deque的数据结构

deque并不是真正意义上的连续，它是由一段段小空间拼接而成的，它实际上像一个二维数组，空间结构如下：

由图可知，deque类中有四个成员变量：
node：指向中控数组(储存指针的数组)数据的二级指针；
cur:指向当前缓存区(*node指向的缓冲区)访问的数据的指针；
first:指向当前缓冲区的开头(并非开头的数据，就是指该内存块的开头)的指针；
last:指向当前缓冲区的末尾(内存块的末尾)的下一位置的指针。
在这四个成员变量中，只有node指向的是中控数组，其他的都指向储存数据的缓存区。

该结构是怎么访问数据的

该结构将一块块小空间的开头地址储存在中控数组中，node指向中控数组中的数组，通过对node的解引用，我们可以找到储存数据的内存块，再通过first和last给出了该内存的的范围，通过cur对数据进行访问。

遍历的步骤

先让node指向中控数组储存的第一个元素，通过对其解引用从cur(不一定对于first，它是指向逻辑意义的开头，即第一个有效数据)开始遍历，当到该缓冲区的last后，对node++再到下一个缓冲区，重复这样的操作找到遍历完全部数组。

尾插

找到储存最后一个数据的缓存区，如果没满，直接尾插在该缓冲区；如果该缓冲区已满，那就会新开一个缓冲区，让该数据储存于该缓冲区的first，同时将该缓冲区的first尾插到中控数组中。

头插

找到储存第一个数据的缓冲区，如果它没满，直接将书局头插在该缓冲区；如果满了，就会新开一个缓冲区，让该数据储存在该缓冲区last的前一位置，同时将该缓冲区的first尾插到中控数组中。

中控数组是怎么储存数据的

一开始，中控数组是只有中几个数据(至少一个)是存了缓冲区的地址的，因为前面要为因为头插而开辟的缓冲区预留空间，后面则为因为尾插或中间插入而导致的开辟的缓冲区预留空间。当头插或尾插到尽头了就会开辟一个更大的空间来储存这些缓冲区的地址。

迭代器

deque因为融合了list和vector，所以它是可以用[]访问的，同时迭代器也可以+n。

3.deque的缺陷

相比于vector，deque的头删/插不用移动其他数据，效率极高；而且扩容时不用搬运大量数据。
相比于list，deque的空间利用率很高。
但是deque有一个致命缺陷：
不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其
是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实
际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看
到的一个应用就是，STL用其作为stack和queue的底层数据结构。

三.优先对列priority_queue

1.priority_queue的介绍

1.优先对列同栈与队列一样是一种容器适配器；
2.优先队列的底层是堆，并且默认是大堆，对优先队列取数据只能取到所有数据中的最大值，删除也只能从最大值开始删起。既然底层是堆，那么就说明模拟实现它的容器必须支持随即迭代器，因为经常要通过下标来调整数据；
3.优先函数默认用vector实现，当然也可以手动选择容器，但要满足随机访问；
4.它的接口并不多，常用的有push、pop、top；

2.priority_queue的模拟实现

其结构：

template<class T,class Container = vector<T>>
class priority_queue
{
	public:
	private:
		Container _con;
}

插入数据

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

因为我们要始终保持数据在逻辑结构上是堆，所以每插入一个数据都得向上调整。

		void AdjustUp(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 Adjustdown(int parent)
		{
			int child = 2 * parent + 1;//左孩子
			while (child < size())
			{
				if (child + 1 < size() && compare()(_con[child] , _con[child + 1]))//假设左孩子更大
				{
					++child;
				}
				if (compare()(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
					break;
			}
		}
		void pop()
		{
			assert(!empty());
			swap(_con[0], _con[size() - 1]);
			_con.pop_back();
			Adjustdown(0);
		}

其他接口

//取堆顶元素
		void top()
		{
			assert(!empty());
			return _con[0];
		}
//获取有效数据个数
		size_t size()
		{
			return _con.size();
		}
//判空
		bool empty()
		{
			return _con.empty();
		}

四.仿函数

我们实现的优先队列是默认排大堆的，那如果我们想要排小堆怎么办？直接对成员函数进行修改吗？这显然是不现实的。这个时候就要用上仿函数(是一种类)了。

template<class T>
class func
{
public:
	bool operator()(const T& val1,const T& val2)
	{
		return val1 < val2;
	}
};
int main()
{
	func<int> f1;
	cout << f1(1, 2) << endl;
	cout << func<int>()(2, 3) << endl;//匿名构造
	return 0;
}

比如这个代码，我们在模板类func中重载了操作符 “()”，这使得我们可以像调用函数一样使用该类的对象。这种类就是仿函数。

那我们该怎么用仿函数对模拟的优先队列进行调整呢？
我们可以写两个比较大小的仿函数，然后在优先队列模板类上加一个模板参数，将该参数应用于成员函数中比较的小的代码即可。

	template<class T>
	struct less//用来建大堆
	{
		bool operator()(const T& val1, const T& val2)
		{
			return val1 < val2;
		}
	};
	template<class T>
	struct greater//用来建小堆
	{
		bool operator()(const T& val1, const T& val2)
		{
			return val1 > val2;
		}
	};
	
	//template<class T,class Container = vector<T>>
	template<class T,class Container = vector<T>,class compare = less<T>>
	
	//用上仿函数灵活建立大小堆,这里默认用less以建大堆
	class pripority_queue//默认大堆
	{
	public:
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
			
				//if (_con[child] > _con[parent])
				if (compare()(_con[parent],_con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}

				else
					break;
			}
		}
		void Adjustdown(int parent)
		{
			int child = 2 * parent + 1;//左孩子
			while (child < size())
			{
			
				if (child + 1 < size() && compare()(_con[child] , _con[child + 1]))
				//假设左孩子更大
				{
					++child;
				}
				
				if (compare()(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = 2 * parent + 1;
				}
				
				else
					break;
			}
		}
		void push(const T& val)
		{
			_con.push_back(val);
			AdjustUp(_con.size() - 1);//将新插入数据的下标传给向上调整函数
		}
		void pop()
		{
			assert(!empty());
			swap(_con[0], _con[size() - 1]);//将堆顶数据与第一个数据交换位置
			_con.pop_back();
			Adjustdown(0);//要将第一个元素向下调整
		}
		void top()
		{
			assert(!empty());
			return _con[0];
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

一定要注意传给仿函数参数的位置！！

完整代码

代码链接