C++算法
C++ 适配器模式实现 STL 的 stack 和 queue
讲解 C++ STL 中 stack 和 queue 的适配器模式原理。通过封装底层容器（如 deque），实现后进先出和先进先出特性。文章包含 stack 和 queue 的手写实现代码，分析 deque 作为默认底层容器的优势及迭代器机制，展示组合优于继承的设计思想。
讲解 C++ STL 中 stack 和 queue 的适配器模式原理。通过封装底层容器（如 deque），实现后进先出和先进先出特性。文章包含 stack 和 queue 的手写实现代码，分析 deque 作为默认底层容器的优势及迭代器机制，展示组合优于继承的设计思想。
关于这两个容器的更多介绍，请移步该网站。https://cplusplus.com/reference/
栈和队列算是我们的老朋友了，之前数据结构的学习中，我们对他们的性质十分熟悉。我们来看 C++STL 中 stack 和 queue 是如何实现的
stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的。元素在特定容器的尾部 (即栈顶) 被压入和弹出。stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，但这些容器类应该支持以下操作：
empty：判空操作size：返回栈中有效元素的个数back：获返回尾部元素的引用push_back：尾部插入元素pop_back：尾部删除元素vector、deque、list 均符合这些需求，默认情况下，如果没有为 stack 指定特定的底层容器，默认情况下使用 deque。deque 是什么，我们在后文介绍std::stack 的成员函数queue 是作为容器适配器实现的，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。empty：检测队列是否为空size：返回队列中有效元素的个数front：返回队头元素的引用back：返回队尾元素的引用push_back：在队列尾部入队列pop_front：在队列头部出队列deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 dequestd::queue 的成员函数有了前面 STL 的基础，
queue和stack的函数功能我们一看便知。
适配器模式是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口
STL 中，适配器通常是对已有容器的封装与限制，通过限制接口、修改行为等方式，让一个已有的类表现出不同的'外观'或'用途'。虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为 stack 和 queue 只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque 作为实现
在 STL 中，stack 和 queue 就是对底层容器的适配器。它们不是自己实现底层的数据结构，而是使用已有容器（如 deque、vector、list）进行封装，只暴露特定的接口。
我们依旧将实现的 stack 封装在命名空间 m_stack 中
namespace m_stack {
template<typename T, typename Container = deque<T>>
class stack {
private:
Container _con; // 这是自定义类型，该类内无需实现构造函数和析构函数
public:
// ... 成员函数
};
}
Container 是我们添加模版参数，用于接收容器。默认使用 deque<T> 进行适配，构造 stack 时也可以选择其他的支持相应操作的容器进行适配。Container _con：将用于适配的其他容器定义在 stack 中，通过相应的接口适配出 stack 所需的的功能Container _con 为自定义类型，该 stack 类默认生成的构造函数会自动调用 Container 类型的构造函数，默认生成的析构函数会自动调用 Container 类型的析构函数。因此我们的 stack 无需手动实现构造和析构函数// 类内是 自定义类型时，构造函数和析构函数无需实现
// 编译器默认生成的 会自动调用 自定义类型的构造函数和析构函数
// stack(){}
// ~stack(){}
public:
void push(const T& val) { _con.push_back(val); }
void pop() { _con.pop_back(); }
push，尾插，直接调用相应容器 push_back 即可pop，尾删，直接调用相应容器 pop_back 即可push_back 和 pop_back使其满足后进先出的特性public:
// top 应该同时实现 const 和 非 const 版本 保证只读 stack 和可修改 stack 的使用
const T& top() const {
return _con.back();
// return _con[size-1]; //这是错误写法 不能用 [] 因为当适配器是 list 时，没有 [] 重载
}
T& top() {
return _con.back();
}
_con.back() 接口T& top()): 允许通过返回的引用直接修改栈顶元素（例如 stack.top() = 10;），适用于需要修改栈顶元素的场景const T& top() const): 返回常量引用，禁止修改栈顶元素，适用于只读访问（如打印栈顶值），且可在 const 对象上调用public:
size_t size() const {
return _con.size();
}
bool empty() const {
return _con.empty();
}
const 成员函数
// 适配器模式
// 没必要再从 0 实现一个栈，数据的存储可以用其他容器实现。栈由其他容器适配出来
// 可以增加一个模板参数来接受容器，然后
// 容器适配器就是 将已有的容器封装改造，设计出想要的容器
// STL 中给的默认适配容器是 deque
namespace m_stack {
template<typename T, typename Container = deque<T>>
class stack {
private:
Container _con;
public:
void push(const T& val) { _con.push_back(val); }
void pop() { _con.pop_back(); }
const T& top() const { return _con.back(); }
T& top() { return _con.back(); }
size_t size() const { return _con.size(); }
bool empty() const { return _con.empty(); }
};
}
queue的适配实现与stack的方法类似，这里就不在过多赘述。
namespace m_queue {
template<typename T, typename Container = deque<T>>
class queue {
private:
Container _con;
public:
// ... 成员函数
};
}
public:
void push(const T& val) { _con.push_back(val); }
void pop() { _con.pop_front(); }
//_con.erase(_con.begin()); // 可以调用 erase, 强制使用 vector 适配
// 但是不合适，因为 vector 头删效率更低
push_back 即可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();
}
public:
size_t size() const {
return _con.size();
}
bool empty() const {
return _con.empty();
}
const 成员函数
namespace m_queue {
template<typename T, typename Container = deque<T>>
class queue {
private:
Container _con;
public:
void push(const T& val) { _con.push_back(val); }
void pop() { _con.pop_front(); }
const T& front() const { return _con.front(); }
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(); }
};
}
deque(双端队列)：是一种双开口的连续空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)。
vector 相比：头插效率更高，不需要搬移元素list 相比：空间利用率比较高。deque 的接口很神奇，可以同时支持 operator[] 即随机访问（vector 的性质）和头插头删（list 的性质）尾插尾删。但他它实际上并没有撼动 vector 和 list 的地位，并不能达到替代 vector 和 list 的目的deque 类似于一个动态的二维数组，其底层结构与 vector 和 list 的对比如下图所示：deque 内部的空间实现：
deque 相比于 vector：
vector 高的deque 中 operator[] 实现的不够极致，取数据时，需要计算数据在哪一段空间 (buff) 中，在哪段空间 (buff) 的第几个。基于这个原因，在需要进行频繁的进行下标访问的情况下，其效率和性能不及 vector，所以无法替代 vectordeque 中 operator[] 的计算过程：
[] 访问的位置 是否在第一个用于头插的空间（buff）中，如果在，使用位置进行访问deque 相比于 list：
deque 支持下标的随机访问deque 的CPU 缓存命中率较高，不需要频繁的去堆上申请空间operator[] 的计算就没有办法确定具体是在哪一个空间（buff），哪个空间的第几个位置了，只能从头开始依次遍历空间（buff）去寻找所在位置了。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 的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下。而序列式场景中，可能需要经常遍历，因此在实际中需要线性结构时，大多数情况下优先考虑 vector 和 list，deque 的应用并不多。
目前能看到的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构
deque 的迭代器：
双端队列 deque 底层是一段假象的连续空间，实际是分段连续的。为了维护其'整体连续'以及随机访问的假象，重任落在了 deque 的迭代器身上，因此 deque 的迭代器设计就比较复杂，如下图所示：
_Tp* _M_cur;
_Tp* _M_first;
_Tp* _M_last;
_Map_pointer _M_node;
cur：指向当前所处的位置first：指向当前所处空间的起始位置end：指向当前所处空间的结束位置node：指向中控指针数组的位置*(node+1) 就可以找到下一个空间的指针，进而进行空间（buff）的的跳转begin 返回的迭代器指向的空间（buff）的 cur 位置处开始进行访问遍历，当遍历到当前空间（buff）的 last 指针位置处的时候通过node 指针使用 *(node+1) 进行跳转空间（buff），跳转空间继续执行遍历操作，再跳转进行遍历，直到跳转遍历到 end 迭代器指向的空间（buff）的 cur 指针指向的位置处结束遍历适配器模式让我们意识到，编程不一定要从零开始，借力也能打出精彩。STL 中 stack 和 queue 的实现，不是另起炉灶，而是通过适配已有容器，封装出特定功能的接口。这种思路不仅提升了开发效率，更展示了面向对象设计中'组合优于继承'的智慧。
通过本文的学习，我们从 stack 和 queue 的接口设计讲起，到手搓自定义容器适配器，再深入了解了 deque 作为底层实现的优势与限制。希望你不仅学会了如何实现这两个容器，更领悟到设计模式在 STL 中的实际运用。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online