手机制作购物网站,广告投放收费标准,网页设计总结报告500字,长沙百度seo排名本期主题#xff1a;list的讲解和模拟实现博客主页#xff1a; 小峰同学分享小编的在Linux中学习到的知识和遇到的问题小编的能力有限#xff0c;出现错误希望大家不吝赐stack的介绍和使用1.1.stack的介绍1. stack是一种容器适配器#xff0c;专门用在具有后进先出操作的上…本期主题list的讲解和模拟实现博客主页 小峰同学分享小编的在Linux中学习到的知识和遇到的问题小编的能力有限出现错误希望大家不吝赐stack的介绍和使用1.1.stack的介绍1. stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行 元素的插入与提取操作。 2. stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定 的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出。 3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类这些容器类应该支持以下 操作 empty判空操作 back获取尾部元素操作 push_back尾部插入元素操作 pop_back尾部删除元素操作 4. 标准容器vector、deque、list均符合这些需求默认情况下如果没有为stack指定特定的底层容器 默认情况下使用deque。 1.2.stack的使用stack的接口很少就下面的几个主要的是结构很好。学习这种结构和怎么模拟实现。2. queue的介绍和使用 2.1.queue的介绍1. 队列是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端 提取元素。 2. 队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列从队头出队列。 3. 底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操 作: empty检测队列是否为空 size返回队列中有效元素的个数 front返回队头元素的引用 back返回队尾元素的引用 push_back在队列尾部入队列 pop_front在队列头部出队列 4. 标准容器类deque和list满足了这些要求。默认情况下如果没有为queue实例化指定容器类则使用标 准容器deque。 2.2. queue的使用 这里就很简单啦3.stack和queue的模拟实现3.1.stack模拟实现直接上源码
namespace zxf
{//以前我们在实现栈的时候//往往回去直接一个动态数组手动来控制元素。//templateclass T//class stack//{//private:// T* _parr;// size_t _top;// size_t capacity;//};//c这样写就很麻烦。//所以就会有一种很简单的设计模式。//就是适配器模式//适配器模式 就是使用已经存在的东西去封装转换出自己想要的东西不需要我们自己去实现。templateclass T, class container dequeTclass stack{public:void push(const T val){_con.push_back(val);}void pop(){_con.pop_back();}bool empty(){return _con.empty();}T top(){//return *(_con.end()-1);return _con.back();//vector 和 list 都支持 back 这个接口。}size_t size(){return _con.size();}private://这里可以写死是 vector 或者 list //vectorT _vt;//listT _lt;//也可以不写死在来一个模板参数container _con;//调用的时候传入两个类型参数即可。//stackint , vectorint st1;//stackint , listint st1;};
}
知识点1.这里使用了一种设计模式叫适配器模式。2.适配器模式就是使用就是使用已经存在的东西去封装转换出自己想要的东西不需要我们自己去实现3.这里用vector 或者 list 去实现 stack的类型。3.2.queue模拟实现直接上源码namespace zxf
{//也是使用是适配器模式来实现的啦。//stl 库中实现的时候 给第二个参数container一个缺省参数 dequeTtemplateclass T ,class container dequeTclass queue{public:void pop(){_con.pop_front();//注意 vector 没有实现 pop_front()接口 。}void push(const T val){_con.push_back(val);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T back(){return _con.back();} const T front(){return _con.front();}private:container _con;//调用的时候传入两个类型参数即可。//queueint , vectorint st1;//queueint , listint st1;};
}1.也是适配器模式的实现,适配器的好处,就是使用简单,方便, 上面我们给模板的第二个参数 可以是 stl中已经存在的,也可以是我们自己写一个只要含有哪些接口 都可以 ,适配成这样的.2.stl库中的queue 和stack 都是适配器实现的.4.简单介绍deque4.1.deque的原理介绍1.deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)2.与vector比较头插效率高不需要搬移元素与list比较空间利用率比 较高.3.感觉兼具 list 和 vector的优点于一身.接口我就不一一讲解了. 经给stl的学习,肯定看一眼就可以懂了.deque文本介绍deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组其底层结构如下图所示1,要尾部插入直接就插入了,但是想头部插入的时候,需要在首节点的的前面再开一个常数大小的数组,插入数据.空间浪费也解决了.2.双端队列底层是一段假象的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问的假象落 在了deque的迭代器身上因此deque的迭代器设计就比较复杂如下图所示 那deque是如何借助其迭代器维护其假想连续的结构呢 4.2.deque的缺陷 1.deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到 某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历.2.因此在实际中需要线性结构 时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作 为stack和queue的底层数据结构。 3.中间插入删除也不好做,需要挪动数据.4.deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不 需要搬移大量的元素因此其效率是比vector高的。 与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。5.中间插入删除少,头部尾部插入删除多,偶尔随机访问,甚至不随机访问,的适合使用 deque.常见的就是作为stack和queue的底层数据结构.4.3.为什么选择deque作为stack和queue的底层默认容器 1,stack是一种后进先出的特殊线性数据结构因此只要具有push_back()和pop_back()操作的线性结构都可 以作为stack的底层容器比如vector和list都可以2,queue是先进先出的特殊线性数据结构只要具有 push_back和pop_front操作的线性结构都可以作为queue的底层容器比如list。但是STL中对stack和 queue默认选择deque作为其底层容器主要是因为 1. stack和queue不需要遍历(因此stack和queue没有迭代器)只需要在固定的一端或者两端进行操作。 2. 在stack中元素增长时deque比vector的效率高(扩容时不需要搬移大量数据)queue中的元素增长 时deque不仅效率高而且内存使用率高。
