本文主要是介绍satck和queue以及priority_queue，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、stack的介绍和使用
stack具有后进先出的特性，，stack是被作为容器适配器实现的，容器适配器是利用现有的容器类型作为基础，来创建新的容器类型，容器适配器通常与普通容器提供相同的接口，但可能添加了一些特定的功能和限制；
标准容器vector list deque都可以作为底层容器来构建stack，默认情况下，使用deque作为底层容器；
satck的模拟实现
//容器适配器模式
template<class T,class Container=vector<T>>
class stack
{
public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& top(){return _con.back();}
private:Container _con;
};2、queue的使用和介绍
队列是一种容器适配器，具有先进先出的特点，标准容器deque和list可以作为底层容器构建queue，为什么不用vector呢？ 因为vectoe进行头删时比较麻烦，代价比较大，
queue的模拟实现
template<class T,class Container=deque<T>>
class queue
{
public:void push(const T& x){_qt.push_back(x);}void pop(){_qt.pop_front();}size_t size(){return _qt.size();}bool empty(){return _qt.empty();}const T& front(){return _qt.front();}const T& back(){return _qt.back();}private:Container _qt;
};3、priority_queue的介绍和使用
优先队列是一种容器适配器，按照降序排序，不管你是怎么插入的，他的第一个元素总是他所包含的元素中最大的那一个，优先队列底层类似于堆，默认按照大堆实现，排降序；
标准容器vector 和deque可以作为底层实现容器，默认情况下使用vector作为底层实现容器
需要支持随机访问迭代器，以便在内部保持堆结构，容器适配器通过调用算法函数make_heap push_heap pop_heap 来保持堆结构，
优先队列底层是堆的结构，所以不能用list实现
priority_queue的使用
优先队列默认使用vector作为底层容器，在vector上又使用了堆算法将vector中元素构成堆的结构
默认情况下priority_queue是大堆；
priority_queue的模拟实现
仿函数，向上调整和向下调整
仿函数其实就是一个类，类里面对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;}};template<class T,class Container=vector<T>,class Compare= greater<T>>class priority_queue{public:void adjust_up(size_t child){size_t parent = (child - 1) / 2;Compare com;while (child > 0){//if (_con[child] > _con[parent])if (com(_con[child] , _con[parent])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(size_t parent){size_t child = parent * 2 + 1;Compare com;while (child< _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])if (child + 1 < _con.size() && com(_con[child + 1],_con[child])){child++;}//if (_con[child] > _con[parent])if (com(_con[child],_con[parent])){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();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con[0];}private:Container _con;};
}4、容器适配器
容器适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的，代码设计经验的总结)，该种模式是将一个类的接口转换成我们希望的另外一个接口。
STL标准库中sack和queue的底层结构
他们的底层都是用deque和vector实现的；
5、deque的介绍
deque(双端队列)：
是一种双开口的“ 连续 ”空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector相比，头插效率高，不用移动元素，与list相比较，空间利用率比较高。
deque并不是真正的连续空间，而是由一段段连续的小空间拼接起来的，实际的deque类似于一个动态的二维数组
deque的迭代器设计比较复杂：
deque的优点：
头插、尾插效率高
缺点：
中间插入删除会很麻烦
[]的效率不够极致，比如说用sort排序deque效率很慢，
deque不适合遍历，因为在遍历时，deque的迭代器需要频繁的检测是否移动到某段小空间的边界，导致效率低下
为什么选择deque作为stack和queue的底层默认容器
stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。
这篇关于satck和queue以及priority_queue的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
