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;
}
else
break;
}
}
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;
}
else
break;
}
}
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;
}
else
break;
}
}
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;
}
else
break;
}
}