回顾

对于STL，我们已经知道了vector和list，而它们是STL中被称为六大组件之一的容器，我们还学习了模拟实现stack，而stack在STL中被称为六大组件之一的适配器，今天，我们来学习queue的模拟实现和priority_queue的模拟实现，并且，它们也是适配器。

对于适配器而言，我们参照stack的模拟实现的经验，适配器的接口不过是调用容器的接口实现的，所以要实现一个适配器，只要理解了它的数据结构，实现是很简单的。

queue（队列）

什么是队列？在日常生活中，我们如果要去超市买东西，收银的时候如果人比较多，我们就需要排队，从队尾排，直到我们前面的人都收完钱，这就是一个队列，先排的人先走，后排的人后走。队列遵循的是先进先出的原则。

再回过头来看看stack，stack是遵循先进后出的原则，它与我们今天要学的queue相反。

所以，queue的整体还是很好理解的，那么我们如果要实现它，应该采用怎样的数据结构呢？ 

stack我们可以使用vector作为容器完成，那么queue呢？是否也能使用vector作为容器完成？

这里就需要考虑到我们的时间复杂度来进行衡量了，因为queue的先进后出的原则，如果我们要进行删除，就只能从队头的数据开始删除，但是如果从队头开始删除数据，vector作为连续的数组空间，那么势必每次删除都需要挪动数据，每次删除数据都将会是一个O(N)的时间复杂度，所以并不高效，也就不能使用vector作为queue的容器。那么大家是否已经想到了比较合适容器比较高效的实现我们的queue呢？ -----list和deque就很好，它们对于头删的成本并不高，时间也很高效！

而STL是采用deque作为queue的默认容器。

模拟实现queue

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

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

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

	bool empty() const
	{
		return _data.empty();
	}
		
	T& front()
	{
		return _data.front();
	}
	const T& front() const 
	{
		return _data.front();
	}

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

	const T& back() const
	{
		return _data.back();
	}
private:
	Container _data;
	};

模版的实现很简单，实现它的接口也只是调用容器的接口，这里也有一个原因说明了了为什么不能使用vector来作为容器，因为vector根本没有pop_front这个接口，也就不可能用来作为我们的容器。

priority_queue(优先级队列)

priority_queue与queue的区别还是挺大的，priority_queue的数据结构其实本质就是堆，对于堆的数据结构而言，它的容器可以为vector，而queue是不可以的。

 对于堆的内容，如果不太理解，可以去查找堆先关的内容，堆是一种基于二叉树的数据结构。

queue的增删是这样的（以大堆举例）

对于删除数据，它会先使堆顶元素（最大元素）与最后的元素交换，然后删除最大元素(尾删)，然后再进行堆排序，堆顶元素（本来是尾部的元素）进行向下调整，这一系列操作完成删除操作

对于插入数据，它先在尾部插入数据，然后再进行堆排序

因为它要采用堆的储存方式，所以，我们就必须要实现堆排的两个函数---向上调整和向下调整

向上调整和向下调整都是堆 用于保持堆结构的排序算法

向上调整

用于插入数据时，进行堆排序，保持堆的特性

void adjust_up(size_t pos)    //向上调整
{
	Compare com;
	size_t child = pos;
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		//if (_data[parent] < _data[child])
		if (com(_data[parent],_data[child])) //仿函数  等会讲
		{
			std::swap(_data[parent], _data[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

向下调整

void adjust_down(size_t pos)    //向下调整
{
	Compare com;
	size_t parent = pos;
	size_t child = parent * 2 + 1;
	while (child < _data.size())
	{
		if (child + 1 < size() && com(_data[child], _data[child + 1]))
		{
			child = child + 1;
		}
		if (com(_data[parent], _data[child]))  //仿函数
		{
			std::swap(_data[parent], _data[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

这里判断是否向上（下）调整的if判断语句中，用了仿函数的知识，这里暂时不讲，后面再讲，只需要知道这是用来判断是否需要调整。

push

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

当插入数据之后，对新插入的元素进行向上调整，使得保持堆结构。

pop

void pop()     //头部删除
{
	assert(!empty());
	std::swap(_data.front(), _data.back());   
	_data.pop_back();
	adjust_down(0);
}

为什么是采用先交换再尾删的方法呢？因为如果要进行堆排序，使用向上调整的时间复杂度为O(),而如果使用向下调整它的复杂度为O(N)。

其他函数

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


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


const T& top() const 
{
	assert(!empty());
	return _data.front();
}

仿函数

template<typename T , class Container = vector<T>, class Compare = less<T> >
class priority_queue
{
private:
	Container _data;
};

template<typename T>
struct greater
{
public:
	bool operator()(const T& t1, const T& t2) const
	{
		return t1 > t2;
	}
};

在实现priority_queue中，它的模版函数是这样的

template<typename T , class Container = vector<T>, class Compare = less<T> >

前两个不难理解，作为适配器，需要传入容器，那么第三个是什么呢？

在实现刚刚的priority_queue中，既然是堆的方式实现，那么有时候我们就可能需要大堆或者是小堆，这时候，就可以使用仿函数来实现，可为什么叫做仿函数？

仿函数也是一个类，但是你看我们使用它的时候，是不是就像一个函数的调用？

void adjust_up(size_t pos)    //向上调整
{
	Compare com;
	size_t child = pos;
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		//if (_data[parent] < _data[child])
		if (com(_data[parent],_data[child])) //仿函数
		{
			std::swap(_data[parent], _data[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

而它在类中是如何实现的？-> 是通过重载()达到这种效果。

template<typename T>
struct greater
{
public:
	bool operator()(const T& t1, const T& t2) const
	{
		return t1 > t2;
	}
};

这就是仿函数类 greater

如果你想实现 仿函数类 less，就是这样写

template<typename T>
struct less
{
public:
	bool operator()(const T& t1, const T& t2) const
	{
		return t1 < t2;
	}
};