做网站全程指导,上海装饰公司10排名,移动端网站开发,赣州网上房地产信息网#x1f496;作者#xff1a;小树苗渴望变成参天大树#x1f388; #x1f389;作者宣言#xff1a;认真写好每一篇博客#x1f4a4; #x1f38a;作者gitee:gitee✨ #x1f49e;作者专栏#xff1a;C语言,数据结构初阶,Linux,C 动态规划算法#x1f384; 如 果 你 … 作者小树苗渴望变成参天大树 作者宣言认真写好每一篇博客 作者gitee:gitee✨ 作者专栏C语言,数据结构初阶,Linux,C 动态规划算法 如 果 你 喜 欢 作 者 的 文 章 就 给 作 者 点 点 关 注 吧 文章目录 前言一、stack二、queue三、哪种容器适配stack和queue四、容器适配器4.1deque的介绍4.2deque的优缺点4.3为什么选择deque作为stack和queue的底层默认容器 五、总结 前言
我们前面几篇介绍了两个常见容器的具体使用和模拟实现对底层应该是了解的七七八八了今天学的栈和队列就相对来说比较简单因为他是一个容器适配器使用前面两个中的一种来模拟实现就好了它的功能只是前面两个容器的特殊情况而栈和队列的接口也相对来说比较的少一会我会先通过库里面的接口来大家认识一下栈和队列有哪些接口并且让大家更好的知道什么是容器适配器 一、stack 传什么容器栈底层就使用什么容器进行实现这个到模拟实现的再说。 创建对象
stackint s;
stackint,vectorint s1;
stackint,listint s2;
//这样的都可以符合模板参数的就可以我们库里面的栈就实现了这几个接口因为根据栈的特性我们只需要这几个功能函数就够了
构造函数 用什么容器进行构造就要使用什么容器的适配器 vectorint v(4, 10);
stackint, vectorint s(v);
stackint s(v);//这样是错误的因为默认适配的容器是deque的。接下里看看各个功能 vectorint v(4, 10);stackint, vectorint s(v);s.push(1);s.push(2);s.push(3);s.push(4);//入栈cout s.size() endl;//计算栈里面多少个元素while (!s.empty())//判断栈为不为空{cout s.top() ;//取栈顶的元素s.pop();//出栈}强调一点的是我们的容器适配器要符合结构规则再数据结构初阶我们提到栈和队列都可以使用顺序表或者链表但是分析之后栈更合适用顺序表结构队列更适合用链表结构再库里面有的时候强制进行适配可能会出错就好比队列你要传vector容器就会报错因为底层实现用的是list和deque共同的接口而vector没有才会导致出错适配的本质就是传什么容器就用什么容器来模拟此容器你也不能传一个树形结构的容器这样肯定不行所以大家这点要注意。 通过看源码来分析 我们的c就是我们的容器因为我们的dequevector和list都有这些功能的接口而且函数功能都是一样的如果你传进来的容器没有此上面的函数接口就会报错。接下来看queue就明白了
二、queue 创建对象
queueint s;
queueint,listint s1;
queueint,vectorint s2;//上面两个都可以符合模板参数的就可以
//第三个就会出现问题因为vector没有对应的接口我们来看底层 我们看到这个pop_front再vector这个容器里面是没有这个接口的但是再deque和list容器都有这个pop_frint接口的,所以不会报错也明白我上面说的传的容器要适配此容器的功能特点
我们再来看看queue这个容器有哪些接口 对于使用来说都是非常的简单再数据结构初阶的时候就已经介绍过每个接口的含义了
三、哪种容器适配stack和queue
这就要通过stack和queue的特性做决定了。 栈 我们的栈是先进后出的操作都是再栈顶进行操作就是在一个结构尾部进行操作那我们的vector和list对于尾部的插入和删除的时间复杂度是一样的使用vector会更好一些因为vector是一段连续的内存空间空间利用率高空间碎片少。所以使用vector去适配栈结构会比较好一些 模拟实现
#includeiostream
#includevector
#includelist
using namespace std;
namespace xdh
{templateclass T, class Container vectorTclass stack{public:stack() {}//可以不用写因为成员变量是自定义类型stack默认生成的构造函数会去调用自定义类型的构造函数//之前说到六大默认成员函数都是一样的道理void push(const T val)//入栈{_c.push_back(val);}void pop()//出栈{_c.pop_back();}T top()//去栈顶元素{return _c.back();}const T top() const{return _c.back();}size_t size() const//计算栈里面有多少个元素{return _c.size();}bool empty() const//判断栈是否为空{return _c.empty();}private:Container _c;};
}xdh::stackint s;xdh::stackint,vectorint s;xdh::stackint, listint s;//这三种都是可以的队列 我们的队列是先进先出的操作我们的插入在队尾删除在队头对于这两个位置的插入和删除vector在开头删除数据的代价非常大虽然我们有时候需要取出队头队尾的数据对于vector支持随机访问所以这两个位置的数据非常好取出来但是对于list这两个位置也非常好取出来而list对于头部的删除操作效率非常高相比较而言我们的队列使用list去适配会更好而库里面直接是抹杀了vector这种适配可以见到vector的头删的效率是多么低的但是我们在模拟实现的时候可以改变接口函数强制适配一下看看 模拟实现
#includeiostream
#includevector
#includelist
using namespace std;
namespace xdh
{templateclass T,class ContainerlistTclass queue{public:queue(){}//可以不用写因为成员变量是自定义类型queue默认生成的构造函数会去调用自定义类型的构造函数//之前说到六大默认成员函数都是一样的道理void push(const T x)//入队列{_c.push_back(x);}void pop() //出队列{//代码1_c.erase(_c.begin());//为了强制和vector进行适配//代码2//_c.pop_front();//库里面是这样的}T back()//取队尾的数据{ return _c.back();}const T back()const{ return _c.back(); }T front() //取队头的数据{ return _c.front();}const T front()const { return _c.front();}size_t size()const //计算队列的大小{ return _c.size(); }bool empty()const //判断队列是否为空{ return _c.empty(); }private:Container _c;};
}我们将pop里面的代码换成代码1就可以强制适配vector容器了但是库里面实现的代码2的风格所以使用vector适配就会报错
四、容器适配器
前面提到好多次关于容器适配器它具体是什么呢
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)该种模式是将一个类的接口转换成客户希望的另外一个接口。 虽然stack和queue中也可以存放元素但在STL中并没有将其划分在容器的行列而是将其称为容器适配器这是因为stack和队列只是对其他容器的接口进行了包装STL中stack和queue默认使用deque比如 我们发现从一开始我们的库里面实现的都不是像我们一开始默认使用的容器他是使用deque的容器当成栈和队列的默认容器deque是什么为什么选择它做默认适配器我们来看看。
4.1deque的介绍
首先通过前面的的分析想要成为stack和queue的适配容器该有的优点不能少不然就直接选择我刚才说到两种容易作为默认的不就行了既然使用的deque那么它肯定是有很多的优点我们一起来看看
deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。 这么一看我们的deque好像是vector和list的结合体支持头插头删也支持随机访问看上去是非常好的但是当我们深入的去看的时候就发现也就那样不然不就可以直接替代vector和list了嘛
我们来看deque的具体结构是啥样的 我们在来画图分析怎么存放数据的 通过上面的图我们发现虽然可以随机访问数据但是要找到在哪个小的空间上并且找到在哪个位置才能进行访问而对于中间的插入是不友好的是往满的空间进行扩容插入还是想你开一个小的空间那么指针数组的位置的值就要挪动总之这样办法都是不好的。但是对于头插头删或者尾插尾删是优化的 通过画图我们发现一小段的空间并不是连在一起的按照STL的原则遍历都可以使用迭代器而且每个容器的用法都是一样的那么那deque是如何借助其迭代器维护其假想连续的结构呢 他的迭代器有四个指针所以内部是非常的复杂而且遍历的时候需要检查是否到达边界 通过源码我们需要检查小空间的边界条件这样就导致效率低下 4.2deque的优缺点
与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是必vector高的。
与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。 但是deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作为stack和queue的底层数据结构 4.3为什么选择deque作为stack和queue的底层默认容器
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不仅效率高而且内存使用率高。
结合了deque的优点而完美的避开了其缺陷 对于库里面的模拟是西安给的默认容器就是deque 五、总结
对于栈和队列的底层原理大家应该都清楚了吧deque作为了解就可以不需要深究下一篇我将通过几个题目来让大家更好的使用栈和队列我们下篇再见
