画室网站模板,北京小程序开发电话,dede建设网站教程,做收集信息的网站一、stack及其模拟实现
1.1 stack介绍
stack是一种容器适配器#xff0c;专门用在具有后进先出操作的上下文环境中#xff0c;其删除只能从容器的一端进行 元素的插入与提取操作。stack是作为容器适配器被实现的#xff0c;容器适配器即是对特定类封装作为其底层的容器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行 元素的插入与提取操作。stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定 的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出。stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类这些容器类应该支持以下操作empty判空操作、 back获取尾部元素操作 、push_back尾部插入元素操作、 pop_back尾部删除元素操作标准容器vector、deque、list均符合这些需求默认情况下如果没有为stack指定特定的底层容器 默认情况下使用deque。 1.2 stack的使用
函数说明函数说明stack()构造空的栈empty()检测stack是否为空size()检测stack是否为空top()返回栈顶元素的引用push()将元素val压入stack中pop将元素val压入stack中 1.3 stack模拟实现
栈的实现通常有两种方式数组实现和链表实现。在此处我们使用vector作为底层容器实现一个栈
#includevector
#includelist
#includedequenamespace odoaobo
{templateclass T, class Container dequeTclass stack{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}T top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};}
二、queue及其模拟实现
2.1 queue的介绍
队列是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端 提取元素。队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列从队头出队列。底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty检测队列是否为空size返回队列中有效元素的个数、front返回队头元素的引用back返回队尾元素的引用push_back在队列尾部入队列pop_front在队列头部出队列 4.标准容器类deque和list满足了这些要求。默认情况下如果没有为queue实例化指定容器类则使用标 准容器deque。 2.2 queue的使用
函数声明接口说明queue()构造空的队列empty()检测队列是否为空是返回true否则返回falsesize()返回队列中有效元素的个数front()返回队头元素的引用back()返回队尾元素的引用push()在队尾将元素val入队列pop()将队头元素出队列 2.3 queue模拟实现
由于queue需要头部删除vector头部删除的代价很大要移动整个数据而list不需要所以queue适合用list作为底层
#includevector
#includelist
#includedequenamespace odoaobo
{// templateclass T, class Container dequeTclass queue{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_front();//_con.erase(_con.begin());}T front(){return _con.front();}T back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};}
三、priority_queue的介绍和使用
3.1 priority_queue的介绍
优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元 素)。优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特 定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问并支持以下操作 empty()检测容器是否为空size()返回容器中有效元素个数front()返回容器中第一个元素的引用push_back()在容器尾部插入元素pop_back()删除容器尾部元素 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指 定容器类则使用vector。 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作。
3.2 priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意 默认情况下priority_queue是大堆。
函数声明接口说明priority_queue()/priority_queue(first,last)构造一个空的优先级队列empty()检测优先级队列是否为空是返回true否则返回 falsetop()返回优先级队列中最大(最小元素)即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素即堆顶元素 【注意】
1. 默认情况下priority_queue是大堆。
2. 如果在priority_queue中放自定义类型的数据用户需要在自定义类型中提供 或者 的重载。 3.3 priority_queue的模拟实现
通过对priority_queue的底层结构就是堆因此此处只需对对进行通用的封装即可。
#include iostream
using namespace std;#include vector
// priority_queue---堆
namespace bite
{templateclass Tstruct less{bool operator()(const T left, const T right){return left right;}};templateclass Tstruct greater{bool operator()(const T left, const T right){return left right;}};templateclass T, class Container std::vectorT, class Compare lessTclass priority_queue{public:// 创造空的优先级队列priority_queue() : c() {}templateclass Iteratorpriority_queue(Iterator first, Iterator last): c(first, last){// 将c中的元素调整成堆的结构int count c.size();int root ((count - 2) 1);for (; root 0; root--)AdjustDown(root);}void push(const T data){c.push_back(data);AdjustUP(c.size() - 1);}void pop(){if (empty())return;swap(c.front(), c.back());c.pop_back();AdjustDown(0);}size_t size()const{return c.size();}bool empty()const{return c.empty();}// 堆顶元素不允许修改因为堆顶元素修改可以会破坏堆的特性const T top()const{return c.front();}private:// 向上调整void AdjustUP(int child){int parent ((child - 1) 1);while (child){if (Compare()(c[parent], c[child])){swap(c[child], c[parent]);child parent;parent ((child - 1) 1);}else{return;}}}// 向下调整void AdjustDown(int parent){size_t child parent * 2 1;while (child c.size()){// 找以parent为根的较大的孩子if (child 1 c.size() Compare()(c[child], c[child 1]))child 1;// 检测双亲是否满足情况if (Compare()(c[parent], c[child])){swap(c[child], c[parent]);parent child;child parent * 2 1;}elsereturn;}}private:Container c;};
}
}
四、容器适配器
容器适配器是在C标准库中提供的一种容器的封装。它们提供了一种统一的接口使得不同类型的容器可以以相似的方式被使用。容器适配器有三种类型stack、queue以及priority_queue。其中优先队列其实就是数据结构中的堆。它们可以将原本的容器进行封装改变容器的出入规则但是底层的数据存储依然使用其它的容器。这种模式叫做容器适配器。 五、deque
5.1 deque的简单介绍
deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。
deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组。
双端队列底层是一段假象的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问的假象落在了deque的迭代器身上。
5.2 deque的优势于劣势
优势
与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是必vector高的。与list比较其底层是连续空间空间利用率比较高不需要存储额外字段
劣势不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下
