【C++】stack 和 queue 的适配器模式与实现
> 🍃 本系列为初阶C++的内容，如果感兴趣，欢迎订阅🚩
> 🎊个人主页:[小编的个人主页])小编的个人主页
> 🎀 🎉欢迎大家点赞👍收藏⭐文章
> ✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍
目录
🐼前言
🐼栈和队列的认识和使用
🐼栈和队列的模拟实现
🐼适配器
🐼stack的模拟实现
🐼queue的模拟实现
🐼总结
🐼前言
在C语言中，不管是实现一个栈还是实现队列，我们都需要从底层开始造轮子😩；在C++中，我们一直强调不暴露底层结构，讲究提供一组特定的接口，来隐藏容器的底层实现细节，从而实现特定的数据结构行为。我们能否提供一种高效、灵活且易于扩展的方式来实现栈和队列，同时也保持了代码的简洁性和可维护性的方式😜？
🐼栈和队列的认识和使用
我们可以借助Cplusplus来查看<stack>和<queue>类的一些常用接口(类中的其它接口小伙伴们可以根据我给的链接在需要时进行查询)。
🌻<stack>的一些常见接口
🌻<queue>的一些常见接口
- empty：检测队列是否为空
- size：返回队列中有效元素的个数
- front：返回队头元素的引用
- back：返回队尾元素的引用
- push_back：在队列尾部入队列
- pop_front：在队列头部出队列
🍁我们发现，栈和队列的接口基本一样。他们之间的区别是栈遵循后进先出原则，栈顶入数据且出数据，而队列讲究先进先出原则，队尾入数据，队头出数据。
正是因为栈和队列只能在数据的一端进行操作，增加了限制，才诞生了两个这样独一无二的数据结构。好比程序员的“叠叠乐”与“排队游戏”
🐼栈和队列的模拟实现
🍁在C语言中，我们实现栈时，最优是底层使用的是一片连续空间的数组。而实现队列，最优我们使用链表来封装。而现在，我们已经有了<vector>和<list>容器，栈和队列无非就是在<vector>和<list>中对一端进行操作限制，我们能否想到一种方式，借助已有的类/容器，来帮助我们完成所需的类。
答案是可以的，采用适配器的方式。在C++ STL中，<stack>和<queue>就是适配器的典型应用。它们通过封装一个底层容器（如
<vector>或<deque(双端队列)），并提供栈或队列的接口，从而隐藏了底层容器的具体实现。
🐼适配器
🌈在上一节，我们在list的反向迭代器中提到了适配器的概念，使用正向迭代器来适配出反向迭代器。这一节我们再理解适配器这个概念。
适配器模式是一种结构型设计模式，它允许将一个类的接口转换为另一个接口，就像我们的手机充电器一样。适配器模式的核心是通过封装一个已有的类（或对象），并提供一个新的接口，进行类之间的复用，使得原本不兼容的接口能够协同工作。
🍁由于栈和队列本质上是对容器的一种特殊操作限制：
栈（Stack）：后进先出（LIFO），只允许在容器的一端进行插入和删除操作。
队列（Queue）：先进先出（FIFO），只允许在一端插入，在另一端删除。
🔍因此通过适配器模式，
std::stack和std::queue封装了一个底层容器（如std::vector、std::deque或std::list），并限制了对容器的操作，从而实现栈和队列的行为。本质上还是对类的复用，我们只关注接口操作，比如
std::stack只暴露了push()、pop()、top()、empty()等接口，用户无法直接访问底层容器的其他操作。这种封装保证了数据结构的正确性和安全性，我们也只关注push()、pop()、top()、empty()，不需要了解底层push()是如何实现的。下面我们通过实现来感受适配器的魅力！
🐼stack的模拟实现
#pragma once #include<iostream> #include<deque> #include<stack> #include<queue> #include<vector> #include<list> using namespace std; namespace lsg { template<class T,class Container = deque<T>> class stack { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_back(); } T& top() { return _con.back(); } const T& top()const { return _con.back(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; }; }🍁由于<stack>和<list>没有遍历操作，没有迭代器，这时，我们使用双端队列来完成尾部头部操作效率很高，因此，我们采用双端队列<deque>作为默认的适配器，如果显示传，也可以传<vector>,<list>作为适配器。
🔍对于双端队列，小伙伴们可以自行去了解，这里知道
双端队列支持
push_front（头部插入）、push_back（尾部插入）、pop_front（头部删除）、pop_back（尾部删除）等操作效率很高，都为O(1)。✅代码解析:
具体实现操作即栈在只允许在栈顶一端操作，对适配器数据一端比如<vector>做限制即可,调用<vector>类的接口。
🐼queue的模拟实现
#pragma once #include"stack.h" namespace lsg { template<class T,class Container = deque<T>> class queue { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_front(); } T& front() { return _con.front(); } T& back() { return _con.back(); } //只读 const T& front()const { return _con.front(); } const T& back()const { return _con.back(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; } ; }✅代码解析:
我们仅需要完成队列的接口，实现我们想要的接口。用适配器适配出队列。而适配器底层是如何实现的，不需要我们关心。这里适配器不能用<vector>，因为<vector>不支持头删操作，效率太低。这里标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。
为什么选择deque作为stack和queue的底层默认容器？
🔍stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如 list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为： 1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进 行操作。 2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。 结合了deque的优点，而完美的避开了其缺陷。不过在有些场景，比如说容器如果牵扯遍历，deque就显得很不足了。
🐼总结
⌛️通过适配器模式，C++ STL提供了一种高效、灵活且易于扩展的方式来实现栈和队列，同时也保持了代码的简洁性和可维护性。让底层隐藏实现细节，只暴露特定的接口。
通过适配器，支持我们可以自定义容器。甚至我们可以自定义底层容器，甚至可以实现自己的容器类，只要满足适配器的要求。这正是C++设计STL的强大之处。也实现了数据结构的行为（栈或队列）与底层容器的实现解耦。实现了低耦合，高内聚的思想。
感谢你耐心地阅读到这里，你的支持是我不断前行的最大动力。如果你觉得这篇文章对你有所启发，哪怕只是一点点，那就请不吝点赞👍，收藏⭐️，关注🚩吧！你的每一个点赞都是对我最大的鼓励，每一次收藏都是对我努力的认可，每一次关注都是对我持续创作的鞭策。希望我的文字能为你带来更多的价值，也希望我们能在这个充满知识与灵感的旅程中，共同成长，一起进步。再次感谢你的陪伴，期待与你在未来的文章中再次相遇！⛅️🌈 ☀️