C++——stack和queue的模拟实现
栈和队列是我们在学习过的两种基础数据结果，这两种数据结构的实现在以前的博客里都有，这里的stack和queue是作为两种容器出现，但是在实现的逻辑和使用c语言实现的时候的逻辑是一样的。
在已经学习过一下stl容器的情况下，这里介绍另外一种stl容器的实现方式——容器适配器模式。也就是用一个已经存在的容器来实现另外一个具有特殊功能的容器。stack和queue是在容器的一端或者两端对数据进行操作，不能对中间部分的数据进行任何操作，所以这里我们可以用deque这个容器来进行适配，因为deque也仅支持在两端进行操作。
一、stack
作为一种适配器，我们默认是使用deque来进行适配的，但是如果用户强制想要使用其他的容易来实现，这样通过模版的形式也是能够改变的。当用户指定的容器没有对应的功能能，运行时就会发生错误了。因为我们是要用deque来视频stack，所以这个类里面只需要有一个默认的容器对象就行，实际上的数据并不是存放在stack里，而是存放在_con这个成员对象里。
template<class T,class Con= deque<T>>
class stack
{
private:Con _con;
};stack的入栈、出栈、判空等操作其实在deque里就已经把我们实现好了，我们这里要做就是去调用已经实现好的函数就好了。
void push(const T& x)
{_con.push_back(x);
}
void pop()
{_con.pop_back();
}
T& top()
{return _con.back();
}const T& top() const
{return _con.back();
}size_t size() const
{return _con.size();
}bool empty()const
{return _con.empty();
}二、queue
队列的实现和栈是一样的，也是运用容器适配器的模式，利用已经实现好的deque来实现我们想要的队列
template<class T,class Con = deque<T>>class queue{public:queue(){}void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}T& front(){return _con.front();}const T& front() const{return _con.front();}T& back(){return _con.back();}const T& back() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Con _con;};三、优先级队列
优先级队列是一种特殊的队列，它只支持在队列的一端进行操作，并且它出队的顺序并不是按照入队顺序进行的，它是按照入队数据的大小进行的，默认是队列中保存的数据越大，它出队列的优先级越高。
在优先级队列它是按照数据的大小进行出栈的，所以可能是会对中间数据进行操作的，这里使用deque来实现就不太合适了，在每次出栈的时候，我们都只需要确定整个队列里唯一一个最值就可以，这样就不难联想到之前实现过的堆了。我们把一个堆建立起来以后，这样我们就能保证在堆顶的位置一定是那个要出队的数据。所以这里用到的容器应该是vector。
它的结构也很简单，只需要有一个来存储数据的对象即可，其他的操作我们都可以调用已经实现好的vector来完成。
template<class T,class Con=vector<T>>class priority_queue{public:priority_queue(){}private:Con _con;};这里的入队操作其实和我们之前学习建堆的过程是一样的，只不过之前我们是在所有的数据都是在数组内的时候建立这个堆，而且优先级队列这里是当一个数据进入队列以后，先把这个数据插入到数组的最后一个位置，再使用向上调整算法来建堆。
void AdujstUp(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;}elsebreak;}}void push(const T& x){_con.push_back(x);AdujstUp(_con.size() - 1);}出队列的操作也是相同的，因为在堆里，我们能保证的只有堆顶的数据是我们想要的最大值或者最小值，如果我们之间把堆顶的元素进行删除的话，这样不仅所有数据都要向前移动一位的时间消耗很大，而且还会破坏这个堆的结构。所以我们要先把这个要删除的数据和最后一个位置的数据进行交换，这样就可以就轻松的删除这个数据，然后再通过向下调整算法，恢复这个堆的性质，这样能大大降低消耗。
void AdujstDown(int parent){int child = parent * 2 + 1;while (child < _con.size()){if (child+1 < _con.size() && com(_con[child + 1], _con[child]))++child;if (_con[parent]<_con[child]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdujstDown(0);}剩下的一些操作就是很简单的去调用vector里已经实现好的函数就行了。
const T& top(){return _con[0];}const size_t size() const{return _con.size();}const bool empty() const{return _con.empty();}实现到这里其实一个优先级队列的基本功能就完成了，这个优先级队列不仅能存储基本数据类型，只要自定义类型也进行了比较运算符的重载也是能够存储的。但是这样实现的话，这个优先级队列就只能从大到小的输出，并不能实现从小到大的一个输出。
为了让用户能够自定义我们输出的顺序，所以我们要给priority_queue加上一个仿函数
class Compare=Less<T>，通过改变这个模版参数，来达到实现控制输出顺序的目的。
所谓的仿函数就是用一个类来重载()这个操作符，当用这个类实例化出的对象来调用operator()这个函数的时候，就能像实现类似于函数调用的形式，但是本质上是这个类的对象调用了operator()函数。
我们还需要再优先级队列之前实现这两个类。
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;}};其次向上调整算法和向下调整算法也要调整成如下的形式，下面com就是我们用来比较的类，这个类重载了operator()，所以这个类的对象com可以直接用com(_con[parent],_con[child])的方式来直接调用operator()这个函数，编译器会自动识别成com.operator(_con[parent],_con[child])这样形式就被称为仿函数。
void AdujstUp(int child){int parent = (child - 1) / 2;Compare com;while (child > 0){if (com(_con[parent],_con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}}void AdujstDown(int parent){int child = parent * 2 + 1;Compare com;while (child < _con.size()){if (child+1 < _con.size() && com(_con[child + 1], _con[child]))++child;if (com(_con[parent],_con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}