C++ stack和queue-平芜编程栈

文章目录

C++ stack和queue
- stack的介绍和使用
- - stack的介绍
  - stack的使用
  - stack的模拟实现
- queue的介绍和使用
- - queue的介绍
  - queue的使用
  - queue的模拟实现
- 容器适配器
- - 什么是适配器
  - deque的简单介绍
  - - deque的原理介绍
    - deque的缺陷
  - 为什么选择deque作为stack和queue的底层默认容器

C++ stack和queue

stack的介绍和使用

stack的介绍

stack介绍文档

本质：stack是一种容器适配器，专门用于后进先出（LIFO）的上下文环境。
操作限制：只能从容器的一端（栈顶）进行插入和删除。
底层结构：作为容器适配器实现，是对特定容器类的封装，提供一组特定成员函数访问元素。元素从底层容器的尾部（栈顶）压入和弹出。
底层容器要求，必须支持以下操作：
- empty()：判空
- back()：获取尾部元素
- push_back()：尾部插入
- pop_back()：尾部删除
可用底层容器：vector、deque、list均满足要求。
默认底层容器：deque。

stack的使用

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部的元素弹出

voidtest1(){stack<int>stk;vector<int>vec={4,5,6};stack<int,vector<int>>stv(vec);list<int>lt={1,2,3};stack<int,list<int>>stl(lt);stk.push(1);stk.push(2);cout<<stk.top()<<endl;stk.pop();cout<<stk.size()<<endl;if(stk.empty()){cout<<"栈为空"<<endl;}else{cout<<"栈不为空"<<endl;}}

stack初始化不写第二参数默认就是deque，这里我们可以去官方文档上确认，stack不能像数组那样初始化因为stack不是序列容器，但可以通过底层容器间接实现。

stack的模拟实现

stack操作仅限于 push、pop、top、empty、size 等。所以我们只需要手动去实现这些函数接口即可。
那么为什么stack不需要去实现迭代器呢？

因为stack是容器适配器而非容器并且stack和其他的容器不同他并不需要++、–、随机访问和删除等操作，如果stack有迭代器那么我们就可以通过迭代器去遍历stack，这就破坏了stack本来的意思。

我们在使用stack的初始化时说到过不指定vector和list容器时默认使用deque，那么这是怎么做到的呢？我们去看一下官方文档吧。

这里第二个参数是什么意思？

class Container：表示指定用哪个容器来存放这些 T 类型的元素
deque<T>：默认值。如果不写第二个参数，编译器就会自动使用 std::deque 作为底层容器。

经过上述对stack的了解，我们现在开始模拟实现一个属于我们自己的栈吧，这里和官方一致都使用deque。

namespacexhs{template<classT,classCon=deque<T>>classstack{public:stack(){}voidpush(T x){_con.push_back(x);}voidpop(){_con.pop_back();}T&top(){return_con.back();}constT&top()const{return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Con _con;};}

queue的介绍和使用

queue的介绍

queue的介绍文档

本质：queue 是一种容器适配器，专门用于FIFO（先进先出）上下文。
操作限制：从容器一端插入元素，另一端提取元素。元素从队尾入队列，从队头出队列。
底层容器要求，必须支持以下操作：
- empty()：检测队列是否为空
- size()：返回有效元素个数
- front()：返回队头元素的引用
- back()：返回队尾元素的引用
- push_back()：在队列尾部入队列
  -pop_front()：在队列头部出队列
可用底层容器：deque、list满足要求。
默认底层容器：deque。

queue的使用

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

voidtest2(){queue<int>q;q.push(1);q.push(2);cout<<q.front()<<endl;cout<<q.back()<<endl;q.pop();cout<<q.size()<<endl;if(q.empty()){cout<<"队列为空"<<endl;}else{cout<<"队列不为空"<<endl;}}

和stack一样，不写第二参数默认为deque，因为vector来封装效率太低，所以一般都为deque、list。

queue的模拟实现

namespacexhs{template<classT,classCon=deque<T>>classqueue{public:queue(){}voidpush(constT&x){_con.push_back(x);}voidpop(){_con.pop_front();}T&back(){return_con.back();}constT&back()const{return_con.back();}T&front(){return_con.front();}constT&front()const{return_con.front();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Con _con;};}

容器适配器

什么是适配器

通过对栈和队列的了解，我们知道栈和队列是容器适配器，我们最开始了解STL时就说到过6大组件，其中的配接器也叫适配器，通常叫适配器。

那么什么是适配器呢？

适配器是一种设计模式（设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结），该种模式是将一个类的接口转换成客户希望的另外一个接口。

为什么stack和queue明明可以存放元素但是stack和queue不是容器而是容器适配器呢？

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque。

deque的简单介绍

deque的原理介绍

deque（双端队列）：是一种双开口的"连续"空间的数据结构。双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)。
与 vector 比较：头插效率高，不需要搬移元素
与 list 比较：空间利用率比较高

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

实际实现起来就十分复杂，因为双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，所以实际学习C++中很少出现模拟实现deque，因为stack和queue本身可以封装vector和list来达成同样的效果。

deque的缺陷

优点：
- 与 vector 比较：头部插入和删除时不需要搬移元素，效率特别高；扩容时也不需要搬移大量元素，效率比 vector 高
- 与 list 比较：底层是连续空间，空间利用率比较高，不需要存储额外字段
致命缺陷：
- 不适合遍历。遍历时，deque 的迭代器要频繁地去检测是否移动到某段小空间的边界，导致效率低下
- 序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list
- deque 的应用并不多，目前能看到的一个应用就是STL 用其作为 stack 和 queue 的底层数据结构

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

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

主要原因：