【C++】stack和queue的使用及模拟实现（含deque的简单介绍）

---

前言

一、deque的简单介绍（引入deque的初衷、deque的结构 以及 选择deque作为stack和queue的底层默认容器的原因）
二、stack和queue的使用及模拟实现

---

一、deque的简单介绍

1.引入deque的初衷

vector的优点是支持随机访问，缺点是插入删除元素的效率很低（除了尾插尾删）；list的优点是在任意位置插入和删除元素的效率级高，缺点是不支持随机访问。
deque想要融合vector和list的优点弥补它们各自的缺陷，但是融合的并不完美。deque支持随机访问，但访问效率不如vector；而且还有一个致命缺陷：在中间位置的插入和删除效率极低，甚至低于vector；但deque在头尾插入和删除的效率特别高，优于vector，跟list效率同级别

2.deque的结构

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

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

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

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. 高效的头尾操作 deque支持在两端以$O(1)$时间复杂度进行插入和删除操作，这完美适配：

   • stack（后进先出）：仅需尾部操作（push_back/pop_back）。
   • queue（先进先出）：需要头部删除（pop_front）和尾部插入（push_back）。

2. 内存管理的灵活性

   • 分段连续存储：deque由多个固定大小的块组成，扩容时只需分配新块，不需要像vector那样复制整个数组到新位置，deque的扩容成本更低。
   • 避免内存浪费：与list的节点式存储相比，deque的分块结构更紧凑，空间利用率更好。
     （list的底层节点不连续，小节点容易造成内存碎片，空间利用率低，缓存利用率低）

总结
虽然vector尾部操作高效，但头部操作低效，而且deque的扩容成本更低。 deque头尾操作性能跟list同级别，但综合性能优于list（缓存友好）。所以最终选择了queue作为stack和queue的底层默认容器。

二、stack

1.stack的介绍

栈是⼀种特殊的线性表，其只允许在固定的⼀端进行插入和删除元素操作。进行数据插入和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出的原则。

压栈（push）：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈（pop）：栈的删除操作叫做出栈。出数据也在栈顶。

stake作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，stake提供一组特定的成员函数来访问其元素。
stack是一种后进先出的特殊线性数据结构，因此只要具push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector、list 和 deque都可以。默认情况下，如果没有为stake实例化指定容器类，则使用标准容器deque。

适配器是一种设计模式，该种模式是将一个类的接口转换成客户希望的另外一个接口。
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque作为其底层容器类。

2.stack的使用

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

#include <iostream>
#include <stack>
using namespace std;int main()
{stack<int> sta;sta.push(9);sta.push(9);sta.push(6);sta.push(5);sta.push(2);sta.push(0);while (!sta.empty()){cout << sta.top() << ' ';sta.pop();}cout << endl;return 0;
}

3.stack的模拟实现

#include <deque>
using namespace std;
namespace zh
{template <class T, class Container = deque<T> >class stack{public:stack(){ }bool empty() const{return con.empty();}size_t size() const{return con.size();}T& top(){return con.back();}const T& top() const{return con.back();}void push(const T& val){con.push_back(val);}void pop(){con.pop_back();}void swap(stack& x){con.swap(x.con);}private:Container con;};
}

三、queue

1.queue的介绍

队列只允许在⼀端进行插入数据操作，在另⼀端进行删除数据操作的特殊线性表，队列具有先进先出的特性。

入队列：进行插入操作的⼀端称为队尾
出队列：进行删除操作的⼀端称为队头


queue作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。
queue是一种先进先出的特殊线性数据结构，因此只要具push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list 和 deque都可以。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

2.queue的使用

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

#include <iostream>
#include <queue>
using namespace std;int main()
{queue<int> que;que.push(9);que.push(9);que.push(6);que.push(5);que.push(2);que.push(0);while (!que.empty()){cout << que.front() << ' ';que.pop();}cout << endl;return 0;
}

3.queue的模拟实现

#include <deque>
using namespace std;
namespace zh
{template <class T, class Container = deque<T> >class queue{public:queue(){ }bool empty() const{return con.empty();}size_t size() const{return con.size();}T& front(){return con.front();}const T& front() const{return con.front();}T& back(){return con.back();}const T& back() const{return con.back();}void push(const T& val){con.push_back(val);}void pop(){con.pop_front();}void swap(queue& x){con.swap(x.con);}private:Container con;};
}

---