【C++】stack 和 queue 的适配器模式与实现

 
> 🍃 本系列为初阶C++的内容，如果感兴趣，欢迎订阅🚩
> 🎊个人主页:[小编的个人主页])小编的个人主页
>  🎀   🎉欢迎大家点赞👍收藏⭐文章
> ✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍

---

目录

 

 🐼前言

 🐼栈和队列的认识和使用 

  🐼栈和队列的模拟实现

 🐼适配器

  🐼stack的模拟实现

  🐼queue的模拟实现 

  🐼总结 

---

 🐼前言

 在C语言中，不管是实现一个栈还是实现队列，我们都需要从底层开始造轮子😩；在C++中，我们一直强调不暴露底层结构，讲究提供一组特定的接口，来隐藏容器的底层实现细节，从而实现特定的数据结构行为。我们能否提供一种高效、灵活且易于扩展的方式来实现栈和队列，同时也保持了代码的简洁性和可维护性的方式😜？

 🐼栈和队列的认识和使用 

我们可以借助Cplusplus来查看<stack>和<queue>类的一些常用接口(类中的其它接口小伙伴们可以根据我给的链接在需要时进行查询)。 

🌻<stack>的一些常见接口

🌻<queue>的一些常见接口

1. empty：检测队列是否为空 
2. size：返回队列中有效元素的个数
3. front：返回队头元素的引用
4. back：返回队尾元素的引用
5. push_back：在队列尾部入队列
6. 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的强大之处。也实现了数据结构的行为（栈或队列）与底层容器的实现解耦。实现了低耦合，高内聚的思想。

 感谢你耐心地阅读到这里，你的支持是我不断前行的最大动力。如果你觉得这篇文章对你有所启发，哪怕只是一点点，那就请不吝点赞👍，收藏⭐️，关注🚩吧！你的每一个点赞都是对我最大的鼓励，每一次收藏都是对我努力的认可，每一次关注都是对我持续创作的鞭策。希望我的文字能为你带来更多的价值，也希望我们能在这个充满知识与灵感的旅程中，共同成长，一起进步。再次感谢你的陪伴，期待与你在未来的文章中再次相遇！⛅️🌈 ☀️