适配器模式手搓STL的stack和queue
适配器模式实现STL的stack和queue
github地址
0. 前言
在数据结构的学习中，stack栈和queue队列早已是我们耳熟能详的“老朋友”。它们一个主打“后进先出”，一个强调“先进先出”，在算法题和工程开发中都有极高的使用频率。而在C++ STL中，stack和queue的实现却并不是独立构建底层结构，而是借助适配器模式对现有容器进行封装，从而“换个壳”，完成其功能目标。
本篇文章将带你一探STL适配器的设计奥秘，从底层容器的选择，到接口的适配与封装，再到自定义实现stack与queue的全过程，带你深刻理解“不造轮子，也能优雅造车”的精髓。同时，我们还将剖析deque这一“幕后英雄”，理解为何它能胜任stack和queue的底层容器角色。
1. stack和queue的简单介绍
关于这两个容器的更多介绍，请移步该网站。https://cplusplus.com/reference/
栈和队列算是我们的老朋友了，之前数据结构的学习中，我们对他们的性质十分熟悉。我们来看C++STL中stack和queue是如何实现的
1.1 stack
- stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的。元素在特定容器的尾部(即栈顶)被压入和弹出。stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，但这些容器类应该支持以下操作：
empty：判空操作size：返回栈中有效元素的个数back：获返回尾部元素的引用push_back：尾部插入元素pop_back：尾部删除元素
- 标准容器
vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。 - 关于适配器模式和
deque是什么，我们在后文介绍
std::stack的成员函数
1.2 queue
- 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
queue是作为容器适配器实现的，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。- queue底层容器可以是任意标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty：检测队列是否为空size：返回队列中有效元素的个数front：返回队头元素的引用back：返回队尾元素的引用push_back：在队列尾部入队列pop_front：在队列头部出队列
- 标准容器类
deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque
std::queue的成员函数
有了前面STL的基础，
queue和stack的函数功能我们一看便知。
2. 容器适配器
2.1 什么是适配器
适配器模式是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口
2.2 C++中的适配器
- 在C++中适配器，顾名思义，是一个中间“转换器”，它可以把一种接口“适配”为另一种接口，使得原本不兼容的类可以协同工作。
- 在
STL中，适配器通常是对已有容器的封装与限制，通过限制接口、修改行为等方式，让一个已有的类表现出不同的“外观”或“用途”。
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque作为实现
3. 手搓stack和queue
在 STL 中，stack 和 queue 就是对底层容器的适配器。它们不是自己实现底层的数据结构，而是使用已有容器（如 deque、vector、list）进行封装，只暴露特定的接口。
3.1 实现stack
我们依旧将实现的stack封装在命名空间m_stack中
基础架构
namespace m_stack {
template<typename T, typename Container = deque<T>>
class stack {
private:
Container _con; // 这是自定义类型，该类内无需实现构造函数和析构函数
public:
// ... 成员函数
};
模板参数：
- T为stack中存放的数据类型，
Container是我们添加模版参数，用于接收容器。默认使用deque<T>进行适配，构造stack时也可以选择其他的支持相应操作的容器进行适配。
- T为stack中存放的数据类型，
成员变量：
Container _con：将用于适配的其他容器定义在stack中，通过相应的接口适配出stack所需的的功能
构造函数与析构函数：
由于成员Container _con为自定义类型，该
stack类默认生成的构造函数会自动调用Container类型的构造函数，默认生成的析构函数会自动调用Container类型的析构函数。因此我们的stack无需手动实现构造和析构函数// 类内是 自定义类型时，构造函数和析构函数无需实现 // 编译器默认生成的 会自动调用 自定义类型的构造函数和析构函数 // stack(){} // ~stack(){}
push和pop
public:
void push(const T& val) {
_con.push_back(T);
}
void pop() {
_con.pop_back();
}
push：栈的
push，尾插，直接调用相应容器push_back即可pop：栈的
pop，尾删，直接调用相应容器pop_back即可调用容器的
push_back和pop_back使其满足后进先出的特性
数据访问
public:
// top 应该同时实现 const 和 非const 版本 保证只读stack和可修改stack的使用
const T& top() const {
// return _con[size-1]; //这是错误写法 不能用[] 因为当适配器是list时，没有[]重载
return _con.back();
}
T& top() {
return _con.back();
}
- top：top访问栈顶的元素，应当返回容器的最后一个元素，应当调用
_con.back()接口 - top函数需要实现两个版本：
- 非 const 版本 (
T& top()):- 允许通过返回的引用直接修改栈顶元素（例如
stack.top() = 10;），适用于需要修改栈顶元素的场景
- 允许通过返回的引用直接修改栈顶元素（例如
- const 版本 (
const T& top() const):- 返回常量引用，禁止修改栈顶元素，适用于只读访问（如打印栈顶值），且可在 const 对象上调用
- 非 const 版本 (
容量访问
public:
size_t size() const {
return _con.size();
}
bool empty() const {
return _con.empty();
}
- 不对成员做修改的函数应当定义为
const成员函数- size：直接返回容器相应的size()函数的返回值，获取栈中的元素个数。
- empty：直接返回容器相应的empty()函数的返回值，判断栈是否为空。
完整实现
// 适配器模式
// 没必要再从0实现一个栈， 数据的存储可以用其他容器实现。栈由其他容器适配出来
// 可以增加一个模板参数来接受容器，然后
// 容器适配器就是 将已有的容器封装改造，设计出想要的容器
// STL中给的默认适配容器是deque
namespace m_stack {
template<typename T, typename Container = deque<T>>
class stack {
private:
Container _con; // 这是自定义类型，该类内无需实现构造函数和析构函数
public:
// 类内是 自定义类型，构造函数和析构函数无需实现
// 编译器默认生成的 会自动调用 自定义类型的构造函数和析构函数
// stack(){}
// ~stack(){}
void push(const T& val) {
_con.push_back(val);
}
void pop() {
_con.pop_back();
}
// top 应该同时实现 const 和 非const 版本 保证只读stack和可修改stack的使用
const T& top() const {
return _con.back();
// return _con[size-1]; //这是错误写法 不能用[] 因为适配器是list时，没有[]重载
}
T& top() {
return _con.back();
}
size_t size() const {
return _con.size();
}
bool empty() const {
return _con.empty();
}
};
3.2 实现queue
queue的适配实现与stack的方法类似，这里就不在过多赘述。
基础架构
- 设计原理同上文的stack
namespace m_queue {
template<typename T, typename Container = deque<T>>
class queue {
private:
Container _con; // 这是自定义类型，该类内无需实现构造函数和析构函数
public:
// ... 成员函数
};
push和pop
public:
void push(const T& val) {
_con.push_back(val);
}
void pop() {
_con.pop_front();
//_con.erase(_con.begin()); // 可以调用erase, 强制使用vector适配
// 但是不合适，因为vector头删效率更低
}
push：尾插，直接调用相应容器
push_back即可pop：头删，直接调用相应容器
pop_front即可调用容器的
push_back和pop_front使其满足先进先出的特性
数据访问
public:
const T& front() const {
return _con.front();
// return _con[size-1]; //这是错误写法 不能用[] 因为适配器是list时，没有[]重载
}
T& front() {
return _con.front();
}
const T& back() const {
return _con.back();
}
T& back() {
return _con.back();
}
- front和back函数分别需要实现两个版本：
- 非 const 版本 :
- 允许通过返回的引用直接修改队头或队尾元素，适用于需要修改队头或队尾元素的场景
- const 版本:
- 返回常量引用，禁止修改队头或队尾元素，适用于只读访问，且可在 const 对象上调用
- 非 const 版本 :
容量访问
public:
size_t size() const {
return _con.size();
}
bool empty() const {
return _con.empty();
}
- 不对成员做修改的函数应当定义为
const成员函数- size：直接返回容器相应的size()函数的返回值，获取队列中的元素个数。
- empty：直接返回容器相应的empty()函数的返回值，判断队列是否为空。
完整实现
namespace m_queue {
template<typename T, typename Container = deque<T>>
class queue {
private:
Container _con; // 这是自定义类型，该类内无需实现构造函数和析构函数
public:
// 类内是 自定义类型，构造函数和析构函数无需实现
// 编译器默认生成的 会自动调用 自定义类型的构造函数和析构函数
// queue(){}
// ~queue(){}
void push(const T& val) {
_con.push_back(val);
}
void pop() {
_con.pop_front();
//_con.erase(_con.begin()); // 可以强制使用vector适配
// 但是不合适，因为vector头删效率更低
}
// front 和 back 应该同时实现 const 和 非const 版本 保证只读queue和可修改queue的使用
const T& front() const {
return _con.front();
// return _con[size-1]; //这是错误写法 不能用[] 因为适配器是list时，没有[]重载
}
T& front() {
return _con.front();
}
const T& back() const {
return _con.back();
}
T& back() {
return _con.back();
}
size_t size() const {
return _con.size();
}
bool empty() const {
return _con.empty();
}
};
4. deque简单剖析
简介
deque(双端队列)：是一种双开口的**“连续”**空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)。
- 与
vector相比：头插效率更高，不需要搬移元素 - 与
list相比：空间利用率比较高。
- 观察，
deque的接口很神奇，可以同时支持operator[]即随机访问（vector的性质）和头插头删（list的性质）尾插尾删。但他它实际上并没有撼动vector和list的地位，并不能达到替代vector和list的目的
deque无法替代vector和list
- deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的。实际
deque类似于一个动态的二维数组，其底层结构与vector和list的对比如下图所示：
deque内部的空间实现：
deque相比于vector：
- 头部插入和删除时，不需要搬移元素，效率特别高。在扩容时，也不需要搬移大量的元素，因此头插头删时效率是比
vector高的 deque中operator[]实现的不够极致，取数据时，需要计算数据在哪一段空间(buff)中，在哪段空间(buff)的第几个。基于这个原因，在需要进行频繁的进行下标访问的情况下，其效率和性能不及vector，所以无法替代vector
deque中operator[]的计算过程：
- 先看
[]访问的位置是否在第一个用于头插的空间（buff）中，如果在，使用位置进行访问 - 如果不在，将下标 i 减去第一段空间（buff）的元素个数大小sz，得出新的下标i
- 再将下标 i / 空间中的数据个数——>得出是在第几个空间（buff）
- 再将下标 i % 空间中的数据个数——>得出是在空间中的第几个位置
deque相比于list：
deque支持下标的随机访问deque的CPU缓存命中率较高，不需要频繁的去堆上申请空间- 头尾的插入和删除效率高，为O(1)时间复杂度。但是中间位置插入删除需要进行挪动数据。
- 因为不能将插入位置所在的空间进行扩容，一旦扩容，那么
operator[]的计算就没有办法确定具体是在哪一个空间（buff），哪个空间的第几个位置了，只能从头开始依次遍历空间（buff）去寻找所在位置了。 - 所以一旦进行扩容之后deque的operator[]的效率会变差很多，所以这里不能进行对插入位置所在空间进行扩容，针对插入和删除，只能进行挪动数据
- 因为不能将插入位置所在的空间进行扩容，一旦扩容，那么
作为容器适配器
stack是后进先出的特殊线性数据结构。只要具有push_back()和pop_back()操作(尾插尾删)的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构。只要具有push_back()和pop_front()操作(尾插头删)的线性结构，都可以作为queue的底层容器，比如list。
但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：
stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。- 在
stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)； queue中的元素增长时，deque不仅效率高，而且内存使用率高。stack中进行了高频的尾插尾删，queue中进行了高频的尾插头删。头插头删，尾插尾删对于deque来讲时间复杂度是O(1)，所以作为stack和queue的容器适配器完美契合
STL使用deque作为stack和queue的实现，结合了deque的优点，而完美的避开了其缺陷
deque的迭代器
deque的缺陷：
deque有一个致命缺陷：不适合遍历。
- 在遍历时，
deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下。
而序列式场景中，可能需要经常遍历，因此在实际中需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多。
目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构
deque的迭代器：
双端队列deque底层是一段假象的连续空间，实际是分段连续的。为了维护其“整体连续”以及随机访问的假象，重任落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：
_Tp* _M_cur;
_Tp* _M_first;
_Tp* _M_last;
_Map_pointer _M_node;
- deque的迭代器同样也是一个模板类，其成员变量包括四个指针：
cur：指向当前所处的位置first：指向当前所处空间的起始位置end：指向当前所处空间的结束位置node：指向中控指针数组的位置- 由于中控指针数组的物理空间是连续的，所以使用
*(node+1)就可以找到下一个空间的指针，进而进行空间（buff）的的跳转
- 访问元素时：便可以从
begin返回的迭代器指向的空间（buff）的cur位置处开始进行访问遍历，当遍历到当前空间（buff）的last指针位置处的时候通过node指针使用*(node+1)进行跳转空间（buff），跳转空间继续执行遍历操作，再跳转进行遍历，直到跳转遍历到end迭代器指向的空间（buff）的cur指针指向的位置处结束遍历
5. 结语
适配器模式让我们意识到，编程不一定要从零开始，借力也能打出精彩。STL中stack和queue的实现，不是另起炉灶，而是通过适配已有容器，封装出特定功能的接口。这种思路不仅提升了开发效率，更展示了面向对象设计中“组合优于继承”的智慧。
通过本文的学习，我们从stack和queue的接口设计讲起，到手搓自定义容器适配器，再深入了解了deque作为底层实现的优势与限制。希望你不仅学会了如何实现这两个容器，更领悟到设计模式在STL中的实际运用。
以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步
分享到此结束啦
一键三连，好运连连！你的每一次互动，都是对作者最大的鼓励！
征程尚未结束，让我们在广阔的世界里继续前行！🚀