【玩转c++】stack和queue的介绍和模拟实现

本期主题：list的讲解和模拟实现

博客主页： 小峰同学

分享小编的在Linux中学习到的知识和遇到的问题

小编的能力有限，出现错误希望大家不吝赐

1. stack的介绍和使用

1.1.stack的介绍

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行 元素的插入与提取操作。
2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定 的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下 操作： empty：判空操作 back：获取尾部元素操作 push_back：尾部插入元素操作 pop_back：尾部删除元素操作
4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器， 默认情况下使用deque。

1.2.stack的使用

stack的接口很少，就下面的几个，主要的是结构很好。学习这种结构和，怎么模拟实现。

2. queue的介绍和使用

2.1.queue的介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端 提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操 作: empty：检测队列是否为空 size：返回队列中有效元素的个数 front：返回队头元素的引用 back：返回队尾元素的引用 push_back：在队列尾部入队列 pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标 准容器deque。

2.2. queue的使用

这里就很简单啦

3.stack和queue的模拟实现

3.1.stack模拟实现

直接上源码

namespace zxf
{//以前我们在实现栈的时候//往往回去直接一个动态数组，手动来控制元素。//template<class T>//class stack//{//private://    T* _parr;//    size_t _top;//    size_t capacity;//};//c++这样写就很麻烦。//所以就会有一种很简单的设计模式。//就是：适配器模式//适配器模式： 就是使用已经存在的东西去封装转换出自己想要的东西，不需要我们自己去实现。template<class T, class container = deque<T>>class stack{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_back();}bool empty(){return _con.empty();}T& top(){//return *(_con.end()-1);return _con.back();//vector 和 list 都支持 back（） 这个接口。}size_t size(){return _con.size();}private://这里可以写死是 vector  ，或者 list //vector<T> _vt;//list<T> _lt;//也可以不写死，在来一个模板参数container _con;//调用的时候传入两个类型参数即可。//stack<int , vector<int>> st1;//stack<int , list<int>> st1;};
}

知识点：
1.这里使用了一种设计模式叫适配器模式。
2.适配器模式就是使用就是使用已经存在的东西去封装转换出自己想要的东西，不需要我们自己去实现
3.这里用vector 或者 list 去实现 stack的类型。

3.2.queue模拟实现

直接上源码

namespace zxf
{//也是使用是适配器模式来实现的啦。//stl 库中实现的时候 给第二个参数container一个缺省参数 deque<T>template<class T ,class container = deque<T>>class queue{public:void pop(){_con.pop_front();//注意 vector 没有实现 pop_front()接口 。}void push(const T& val){_con.push_back(val);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& back(){return _con.back();}        const T& front(){return _con.front();}private:container _con;//调用的时候传入两个类型参数即可。//queue<int , vector<int>> st1;//queue<int , list<int>> st1;};
}

1.也是适配器模式的实现,适配器的好处,就是使用简单,方便, 上面我们给模板的第二个参数 可以是 stl中已经存在的,也可以是我们自己写一个只要含有哪些接口 都可以 ,适配成这样的.

2.stl库中的queue 和stack 都是适配器实现的.

4.简单介绍deque

4.1.deque的原理介绍

1.deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，

2.与vector比较，头插效率高，不需要搬移元素；
与list比较，空间利用率比 较高.

3.感觉兼具 list 和 vector的优点于一身.

接口我就不一一讲解了. 经给stl的学习,肯定看一眼就可以懂了.

deque文本介绍

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

1,要尾部插入直接就插入了,但是想头部插入的时候,需要在首节点的的前面再开一个常数大小的数组,插入数据.空间浪费也解决了.

2.双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落 在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

那deque是如何借助其迭代器维护其假想连续的结构呢？

4.2.deque的缺陷

1.deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到 某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历.

2.因此在实际中，需要线性结构 时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作 为stack和queue的底层数据结构。

3.中间插入删除也不好做,需要挪动数据.

4.deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不 需要搬移大量的元素，因此其效率是比vector高的。 与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

5.中间插入删除少,头部尾部插入删除多,偶尔随机访问,甚至不随机访问,的适合使用 deque.常见的就是作为stack和queue的底层数据结构.

4.3.为什么选择deque作为stack和queue的底层默认容器

1,stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可 以作为stack的底层容器，比如vector和list都可以；

2,queue是先进先出的特殊线性数据结构，只要具有 push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。

但是STL中对stack和 queue默认选择deque作为其底层容器，主要是因为：
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长 时，deque不仅效率高，而且内存使用率高。