stack&queue的模拟实现

stack 与 queue 作为容器适配器，都默认选择了 deque 作为其底层容器。

#pragma once
#include <deque>
using namespace std;

namespace zs
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& val)
		{
			_cont.push_back(val);
		}

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

		T& top()
		{
			return _cont.back();
		}

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

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

		size_t size() const
		{
			return _cont.size();
		}
	private:
		Container _cont;
	};

	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& val)
		{
			_cont.push_back(val);
		}

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

		T& front()
		{
			return _cont.front();
		}

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

		T& back()
		{
			return _cont.back();
		}

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

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

		size_t size() const
		{
			return _cont.size();
		}
	private:
		Container _cont;
	};
}

deque 的介绍

deque(双端队列) 是一种双开口的“连续”空间的数据结构。
双开口是指，可以在头尾两端进行插入删除，且时间复杂度都是O(1)。
但deque并不是真的连续的物理空间，而是由一段又一段连续的小空间拼接而成的。

为什么会选择 deque 作为 stack 和 queue 的默认底层容器呢？
与 vector 相比，deque 头部插入删除效率高，扩容也不需要搬移大量的元素。
与 list 相比，空间利用率更高，不需要存储额外字段。
deque 也有很多缺陷：
deque 的底层结构决定了它的迭代器设计会很复杂。
遍历以及对数据的随机访问效率会比较低。
完成对中间数据的插入删除操作也会更复杂。
stack 和 queue 的特点能够很好地规避 dqeue 的缺陷，而充分利用到了 deque 的优点，而且这也是 deque 为数不多的应用中的一个。

priority_queue的模拟实现

priority_queue(优先级队列)其实就是一个堆结构，默认使用 vector 作为其底层容器。

#pragma once
#include <vector>
using namespace std;

namespace zs
{
	// Compare 进行比较的仿函数 默认less->大堆 greater->小堆
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		priority_queue()
		{}

		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_cont.push_back(*first);
				++first;
			}

			// 向下建堆
			for (int i = (_cont.size() - 1 - 1) / 2; i >= 0 ; --i)
			{
				adjust_down(i);
			}
		}

		void adjust_up(size_t child)
		{
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_cont[child] > _cont[parent])
				//if (_cont[parent] < _cont[child])
				if (Compare()(_cont[parent], _cont[child]))
				{
					::swap(_cont[parent], _cont[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

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

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

			while (child < _cont.size())
			{
				//if (child + 1 < _cont.size() && _cont[child + 1] > _cont[child])
				//if (child + 1 < _cont.size() && _cont[child] < _cont[child + 1])
				if (child + 1 < _cont.size() && Compare()(_cont[child], _cont[child + 1]))
				{
					++child;
				}
				//if (_cont[child] > _cont[parent])
				//if (_cont[parent] < _cont[child])
				if (Compare()(_cont[parent], _cont[child]))
				{
					::swap(_cont[parent], _cont[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void pop()
		{
			::swap(_cont.front(), _cont.back());
			_cont.pop_back();

			adjust_down(0);
		}

		const T& top() const
		{
			return _cont.front();
		}

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

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

	private:
		Container _cont;
	};

	/*
	*  仿函数，也叫函数对象，主要还是一个类
	*  因为重载了operator(), 可以像函数一样使用
	*/
	template<class T>
	class less
	{
	public:
		bool operator()(const T& val1, const T& val2) const
		{
			return val1 < val2;
		}
	};

	template<class T>
	class greater
	{
	public:
		bool operator()(const T& val1, const T& val2) const
		{
			return val1 > val2;
		}
	};
}