手机网站建设网站,好的门户网站,网站设计与建设课程,七牛云 wordpress#x1f307;个人主页#xff1a;平凡的小苏 #x1f4da;学习格言#xff1a;命运给你一个低的起点#xff0c;是想看你精彩的翻盘#xff0c;而不是让你自甘堕落#xff0c;脚下的路虽然难走#xff0c;但我还能走#xff0c;比起向阳而生#xff0c;我更想尝试逆风… 个人主页平凡的小苏 学习格言命运给你一个低的起点是想看你精彩的翻盘而不是让你自甘堕落脚下的路虽然难走但我还能走比起向阳而生我更想尝试逆风翻盘。 C专栏C内功修炼基地 家人们更新不易你们的点赞和⭐关注⭐真的对我真重要各位路 过的友友麻烦多多点赞关注。 欢迎你们的私信提问感谢你们的转发 关注我关注我关注我你们将会看到更多的优质内容 一、栈和队列的介绍
栈 stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行元素的插入与提取操作。 stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出。 stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类这些容器类应该支持以下
操作
empty判空操作
back获取尾部元素操作
push_back尾部插入元素操作
pop_back尾部删除元素操作
标准容器vector、deque、list均符合这些需求默认情况下如果没有为stack指定特定的底层容器默认情况下使用deque。
队列 队列是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端提取元素。 队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定成员函数来访问其元素。元素从队尾入队列从队头出队列。 底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty检测队列是否为空
size返回队列中有效元素的个数
front返回队头元素的引用
back返回队尾元素的引用
push_back在队列尾部入队列
pop_front在队列头部出队列
标准容器类deque和list满足了这些要求。默认情况下如果没有为queue实例化指定容器类则使用标准容器deque。
二、栈的模拟实现
#pragma once
#include iostream
#include vector
#include deque
#include stacknamespace sqy
{template class T, class Container std::vectorTclass stack{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}T top(){return _con.back();}bool empty(){return size() 0;}size_t size(){return _con.size();}private:Container _con;};
}注意我们在模板上面添加对应栈结构的适配容器来支持栈的添加、删除、获取元素的操作。 并且我们将它设置为缺省参数我们传参时就可以不传适配器它就会使用自己默认的适配容器 三、队列的模拟实现
#pragma once
#include iostream
#include list
#include deque
#include queue
namespace sqy
{template class T, class Container std::listTclass queue{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_front();}T front(){return _con.front();}bool empty(){return size() 0;}size_t size(){return _con.size();}private:Container _con;};
}四、栈和队列使用不同的默认适配器的区别
栈使用的适配器 队列使用的适配器 1.栈使用vector作为适配器可以减少一直开辟空间的消耗提高效率 2.队列使用list而不使用vertor是因为vector不适用区头删元素这是由于队列的特性导致vertor不适用 3 . 为此STL标准库为了让栈和队列使用统一的适配器又产生了一个新的适配器也就是双端队列这个容器适合给栈和队列当作默认适配器。 五、deque的原理简单介绍 deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。 deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组其底层结构如下图所示 双端队列底层是一段假象的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问的假象落在了deque的迭代器身上因此deque的迭代器设计就比较复杂如下图所示
那deque是如何借助其迭代器维护其假想连续的结构呢 使用cur进行遍历cur不等于last就一直进行操作当等于last后node指向下个buffermap存的是指针数组的映射那么first和last也指向下一个的buffer的开头和结尾cur指向first的位置往复如此到最后一个buffer的时候cur等于end()那么就遍历结束了 deque的源码解引用和判断操作
5.1 deque的缺点 与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是必vector高的。 与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。 但是deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作为stack和queue的底层数据结构
六、priority_queue的介绍 优先级队列的特点是优先级高的先出。
优先级队列是一种容器适配器不提供迭代器它的底层是一个堆默认是大堆这个堆默认使用vector进行适配。
priority_queueint pq;//pq底层为大堆
priority_queueint,vectorint,greaterint pq;//pq底层为小堆6.1 优先队列中使用仿函数
仿函数又称函数对象它是一个类类中重载了函数调用符号()这个运算符重载的返回值根据需要去给。
templateclass T
class Less
{public:bool operator()(const T x,const T y){return x y;}
};templateclass T
class Greater
{public:bool operator()(const T x,const T y){return x y;}
};6.2 模拟实现优先级队列
#include iostream
#include vector
#include cassert
using namespace std;
namespace sqy
{templateclass Tclass Less{public:bool operator()(const T x,const T y){return x y;}};templateclass Tclass Greater{public:bool operator()(const T x,const T y){return x y;}};templateclass T, class Container std::vectorT, class Compare LessTclass priority_queue{private:void AdjustUp(int child){Compare con;int n _con.size();int parent (child - 1) / 2;while(child 0){if(con(_con[parent],_con[child])){swap(_con[parent],_con[child]);child parent;parent (child - 1) / 2;}else{break;}}}void AdjustDown(int parent){Compare con;int n _con.size();int child 2 * parent 1;while(child n){if(child 1 n con(_con[child],_con[child1])){child;}if(con(_con[parent], _con[child])){swap(_con[parent],_con[child]);parent child;child 2 * parent 1;}else{break;}}}public:priority_queue(){}templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last){while(first ! last){_con.push_back(*first);first;}for(int i _con.size() - 2; i 0; i--){AdjustDown(i);}}void pop(){assert(_con.size() ! 0);swap(_con[0],_con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}void push(const T x){_con.push_back(x);AdjustUp(_con.size() - 1);}const T top(){assert(_con.size() ! 0);return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};注意博主使用的是自己实现的仿函数仿函数和c语言中的函数指针类似但是祖师爷觉得使用c语言中的函数指针来比较大小太过于麻烦所以祖师爷使用了仿函数的思想进行比较大小这样我们想要比较自定义类型时只要自定义类型写了运算符重载小于号和大于号那就适用于给优先级队列否则就会报错 还有一种情况优先级队列存的是某个类的地址但是需要比较指针指向值的优先级。那这个时候就不能用中的less和greater控制建堆需要自己写仿函数。仿函数也可以加上模板特化
