禁止网站采集,网站开发哪一种语言好,云开发教程,杭州市建设工程管理集团有限公司deque文档 stack文档 deque文档 文章目录 #x1f345;1. deque容器#x1f352;deque底层#x1f352;deque的优势#x1f352;deque的劣势 #x1fad0;2. stack模拟实现#x1f95d;3. queue模拟实现 #x1f345;1. deque容器
查看文档可发现#xff0c;栈和队列都… deque文档 stack文档 deque文档 文章目录 1. deque容器deque底层deque的优势deque的劣势 2. stack模拟实现3. queue模拟实现 1. deque容器
查看文档可发现栈和队列都采用的是容器适配器如果不指定则默认为deque这个容器 deque底层
我们来看一下deque容器的配置 这个deque的功能十分齐全相比vector支持头插头删相比list它可以用[]访问看起来是一个非常棒的结构那为何在平时不常见呢
我们先来看一下deque的底层结构 deque底层类似一个动态的二维数组定义一个中控器从中间开始指向对于的内存空间这样就十分便于头插头删、尾插尾删但这对于迭代器设计也就比较复杂。 deque的优势
deque这样的设计十分适用于需要频繁头插头删、尾插尾删的地方。
所以库里面就采用了deque作为了stack和queue的适配器stack和queue不需要遍历(没有迭代器)所以使用deque作为适配器效率高、内存效率也高
deque的劣势
deque有一个致命的缺陷就是不便于遍历每次遍历都十分麻烦需要频繁检查某段空间的边界这导致访问的开销十分之大。
如果在指定位置插入数据计算十分繁琐相当的头疼。 一百万个随机数据排序速度对比 这里发现vector的效率是明显高于list和deque的因为vector的存储空间是连续的缓存命中率高于list和deque 2. stack模拟实现
STL库里面采用的容器适配器那就不需要手搓轮子了
namespace mystack
{templateclass T, class Container dequeTclass stack{public:bool empty() const{return _con.empty();}size_t size() const{return _con.size();}T top(){return _con.back();}void push(const T val){_con.push_back(val);}void pop(){_con.pop_back();}private:Container _con;};
}3. queue模拟实现
namespace myqueue
{templateclass T,class Container dequeTclass queue{public:bool empty() const{return _con.empty();}size_t size() const{return _con.size();}T front(){return _con.front();}T back(){return _con.back();}void push(const T val){_con.push_back(val);}void pop(){_con.pop_front();}private:Container _con;};
}Tips stack是LIFO(后进先出)可以采用vector或者是list因为vector和list都有头尾插入删除操作 而对于queue是FIFO(先进先出)vector不支持头插头删操作所以并不适配queueSTL库里面也没有这样支持 那本期分享就到这里咯我们下期再见如果还有下期的话。
