网站设计与网页制作正文,神华集团两学一做网站,做婚纱摄影网站多少钱,wordpress 4.9.3目录
前言
一、deque 1、deque 的原理介绍 2、deque 的底层结构 3、deque 的迭代器 4、deque 的优缺点 4.1、优点 4.2、缺点
二、stack 的介绍和使用 1、stack 的介绍 2、stack 的使用 3、stack 的模拟实现
三、queue 的介绍和使用 1、queue 的介绍 2、queue 的使用 3、qu…目录
前言
一、deque 1、deque 的原理介绍 2、deque 的底层结构 3、deque 的迭代器 4、deque 的优缺点 4.1、优点 4.2、缺点
二、stack 的介绍和使用 1、stack 的介绍 2、stack 的使用 3、stack 的模拟实现
三、queue 的介绍和使用 1、queue 的介绍 2、queue 的使用 3、queue 的模拟实现 前言 容器适配器按字面意思理解的话就是用来对一个容器进行匹配的。在CSTL中容器有vectorlistdequemapset等。而在CSTL中不把stack和queue纳入容器的范围而是纳入容器适配器的范围是因为 stack和queue没有下标随机访问等操作只有普通的pop_front,push_back,pop_back()等操作而这些函数在其他容器中完全可以有栈和队列的实现完全可以将其他容器的操作进行复用这就是stack和queue作为容器适配器的原因。 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结)该种模式是将一个类的接口转换成客户希望的另外一个接口。
一、deque 1、deque 的原理介绍 deque (双端队列)是一种双开口的 “连续” 空间的数据结构双开口的含义是 deque 可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与 list 比较空间利用率比较高“随机访问” 效率较高。 2、deque 的底层结构 deque 的底层结构其实并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际 deque 类似于一个动态的二维数组其结构示意图如下 3、deque 的迭代器 双端队列底层是一段假象的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问的假象落 在了deque的迭代器身上因此 deque 的迭代器设计就比较复杂如下图所示 4、deque 的优缺点 4.1、优点 具有 vector 的优点 ---支持随机访问、缓存命中率较高、尾部插入删除数据效率高同时具有 list 的优点 --- 空间浪费少、头部插入插入数据效率高 4.2、缺点 deque 的随机访问效率较低 --- 需要先通过中控数据找到对应的buffer数组再找到具体的位置 (假设偏移量为 i需先 i/10 得到位于第几个buffer数组再 i%10 得到 buffer 数组中的具体位置)即 deque 随机访问时一次跳过一个buffer数组需要跳多次才能准确定位其效率比 list 高了不少但比 vector 也低了不少deque 在中部插入删除数据的效率是比较低的 --- 需要挪动数据但不一定后续 buffe 数组中的数据全部挪动可以控制只挪一部分即中间插入删除数据的效率高于 vector但是低于 list。 所以综上分析 deque 结合了 vector 和 list 的优缺点看似很完美但是它单方面的性能是不如 vector 或者 list 的因此 deque 在实际应用中使用的非常少。
STL 中选择 deque 作为 stack 和 queue 默认适配容器的原因 stack 和 queue 不需要遍历(因此stack和queue没有迭代器)只需要在固定的一端或者两端进行操作。在 stack 中元素增长时deque 比 vector 的效率高(扩容时不需要搬移大量数据)queue 中的元素增长时deque不仅效率高而且内存使用率高。 结合了deque的优点而完美的避开了其缺陷。 deque 特别适合需要大量进行头插和尾部数据的插入删除、偶尔随机访问、偶尔中部插入删除的场景不太适合需要大量进行随机访问与中部数据插入删除的场景特别是排序。
二、stack 的介绍和使用 1、stack 的介绍
stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行元素的插入与提取操作。stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定 的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出。stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类这些容器类应该支持以下操作empty判空操作 back获取尾部元素操作 push_back尾部插入元素操作 pop_back尾部删除元素操作标准容器vector、deque、list均符合这些需求默认情况下如果没有为stack指定特定的底层容器 默认情况下使用deque。 2、stack 的使用
函数说明接口说明stack()构造空的栈empty()检测 stack 是否为空size()返回 stack 中元素的个数top()返回栈顶元素的引用push()将元素 val 压入 stack 中pop()将 stack 中尾部的元素弹出
下面是栈的使用操作
int main()
{//构造空栈stackint s;//元素入栈s.push(1);s.push(2);//获取栈中元素个数int Size s.size();cout Size endl;//获取栈顶元素的引用int sTop s.top();cout sTop endl;//元素出栈s.pop();sTop s.top();cout sTop endl;//判断栈是否为空cout s.empty();return 0;
} 3、stack 的模拟实现 我们在这里为栈模板定义了两个模板参数T 是栈中存储的元素的类型Container 是栈模板使用的底层结构Container 的默认值是 vector如果你想要用别的可以在这里进行设置。我就可以将适配器作为类的第二个模板参数然后通过传递不同的适配容器来实现栈了
//stack.h
templateclass T, class Container
class stack
{//...
};
//test.cpp
void test_stack()
{stackint, vectorint st1;stackint, listint st2;
} vector 和 list 都可以作为 stack 的适配容器我们可以通过给定不同的第二个模板参数来使用不同的容器适配 stack 经过前期的学习显然更适合作为 stack 的适配容器那么我们可以还可以将 vector 设置为 stack 的默认适配容器
//stack.h
templateclass T, class Container vectorT
class stack
{//...
};
//test.cpp
void test_stack()
{//默认使用vector做适配容器stackint st1; //使用其他容器做适配容器需要显式指定stackint, listint st2;
} 有了适配容器之后我们就可以更容易的通过调用适配容器的接口来实现 stack 的接口了。
namespace xx
{//适配器模式/配接器template class T, class Container dequeTclass stack{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}const T top(){return _con.back();}bool size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_stack(){//stackint,vectorint st;//数组栈stackint, listint st;//链表栈st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout st.top() ;st.pop();}cout endl;}
} stack 可以使用 vector 或者 list 来实现效率相当。插入数据就相当于尾插删除栈顶元素就相当于尾删。 三、queue 的介绍和使用 1、queue 的介绍
队列是一种容器适配器专门用于在 FIFO 上下文(先进先出)中操作其中从容器一端插入元素另一端提取元素。队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue 提供一组特定的 成员函数来访问其元素。元素从队尾入队列从队头出队列。底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty检测队列是否为空 ; size返回队列中有效元素的个数; front返回队头元素的引用back返回队尾元素的引用push_back在队列尾部入队列pop_front在队列头部出队列标准容器类 deque 和 list 满足了这些要求。默认情况下如果没有为 queue 实例化指定容器类则使用标准容器 deque。 2、queue 的使用
函数声明接口说明queue()构造空的队列empty()检测队列是否为空是返回 true否则返回 falsesize()返回队列中有效元素的个数front()返回队头元素的引用back()返回队尾元素的引用push()在队尾将元素 val 入队列pop()将队头元素出队列
下面是队列的使用操作
int main()
{//构造空队列queueint q;//元素入队q.push(1);q.push(2);//返回有效元素个数int size q.size();cout size endl;//检查队列是否为空cout q.empty() endl;//获取队头元素的引用int front q.front();cout front endl;//获取队尾元素的引用 int back q.back();cout back endl;//队头元素出队q.pop();return 0;
} 3、queue 的模拟实现 它的模拟实现过程和 stack 类似vector 和 list 都可以作为 queue 的适配容器但是由于 queue 需要大量在头部删除数据所以使用 deque 作为 queue 的默认适配容器那么 queue 模拟实现的代码如下
namespace xx
{template class T, class Container dequeTclass queue{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_front();}const T front(){return _con.front();}const T back(){return _con.back();}bool size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_queue(){queueint q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout q.front() ;q.pop();}cout endl;}
} 本文要是有不足的地方欢迎大家在下面评论我会在第一时间更正。
