stack,queue
创始人
2024-06-01 15:11:48
0次

stack,queue

  • stack的介绍和使用
    • 介绍
    • 使用
    • 模拟实现
  • queue的介绍和使用
    • 介绍
    • 使用
    • 模拟实现
  • priority_queue的介绍和使用
    • 介绍
    • 使用
    • 模拟实现
  • 容器适配器
    • 概念
    • 标准库中stack,queue的底层结构
    • 介绍deque
      • 原理
      • 缺陷
    • deque作为stack,queue底层默认容器

stack的介绍和使用

介绍

  1. stack是适配器的一种,专门用在具有先进后出的容器中,而且元素的删除,插入和提取都只能从容器的一端进行
  2. stack作为容器适配器被实现,容器适配器系对特定类进行封装作为其底层的容器,并提供一组特定的成员函数访问其元素,将特定类作为其底层的,元素特定容器的尾部被压入和弹出,不可遍历
  3. stack的底层容器可以是任何标准的容器类模板
    在这里插入图片描述

使用

函数说明接口说明
stack()构造空栈
empty()检测stack是否为空
size()返回stack中元素的个数
top()返回栈顶元素的引用
push()将元素val压入stack中
pop()将stack中尾部的元素弹出

模拟实现

在这里插入图片描述

模板中的第二个参数Class Container = deque,Container是容器适配器,也就是用已存在的容器进行封装转换出自己想要实现的数据结构的底层容器,而且底层容器的功能可以直接使用,不再需要自己去实现底层容器及其相关功能,使用现成的,很大程度上提高效率。在这里,也就是用deque作为底层容器,去实现stack类的数据结构

    template>class stack{public://数据入栈void push(const T& x){_con.push_back(x);}//数据出栈void pop(){_con.pop_back();}//提取栈顶数据const T& top(){return _con.back();}//检测栈是否为空bool empty(){return _con.empty();}//计算栈中有效元素的个数size_t size(){return _con.size();}private://deque作为底层容器创建变量Container _con;};

queue的介绍和使用

介绍

  1. 队列也是适配器的一种,专门用在先进先出的容器中,从容器一端插入元素,另一端提取元素
  2. 队列作为容器适配器实现,容器适配器系将特定容器进行封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队列头出队列。不可遍历
  3. 底层容器可以是标准容器模板之一
    在这里插入图片描述

使用

函数说明接口说明
queue()构造空队列
empty()检测队列是否为空
size()返回队列中有效元素的个数
front()返回队头元素的引用
back()返回队尾元素的引用
push()在队尾将元素val入队列
pop()将队头元素出队列

模拟实现

在这里插入图片描述
将 deque作为底层容器,通过其去实现 queue类的数据结构

    template>class queue{public://数据入队列void push(const T& x){_con.push_back(x);}//数据出队列void pop(){_con.pop_front();}//提取队头数据const T& top(){return _con.front();}//检测队列是否为空bool empty(){return _con.empty();}//计算队列中有效元素的个数size_t size(){return _con.size();}private://deque作为底层容器创建变量Container _con;};

priority_queue的介绍和使用

介绍

  1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的
  2. 优先队列的容器类似堆,在堆中可以随时插入元素,并且只能提取最大的元素,不可遍历
  3. 优先队列被实现为容器适配器,queue提供一组特定的成员函数来访问其元素。元素从容器的尾部弹出,其称为优先队列的顶部

使用

优先队列默认使用vector作为其底层存储数据的容器,在vector上使用堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue,默认情况下,priority_queue是大根堆

函数说明接口说明
priority_queue()构造空优先队列
empty()检测优先队列是否为空
top()返回优先队列中最大元素,即堆顶元素
push(x)在优先队列中插入元素x
pop()删除优先队列中最大元素,即堆顶元素

模拟实现

在这里插入图片描述

根据上面的介绍,优先队列的本质上就是堆,所以选择vector作为其底层容器;默认情况下,优先队列是大根堆,模板中的比较函数是less,所以如果需要将其改为小根堆的话,只需要将比较函数修改为greater即可

这里的比较函数Compare也称作仿函数
仿函数又称为函数对象是一个能行使函数功能的类,通过创建对象来实行函数功能
作为仿函数的类,都必须重载 operator() 运算符。调用仿函数,本质上就是通过类对象调用重载后的 operator() 运算符。

仿函数的实现

    template//判断前一个数小于后一个数class less{public:bool operator()(const T& x, const T& y) const {return x < y;}};template//判断前一个数大于后一个数class greater{public:bool operator()(const T& x, const T& y) const{return x > y;}};

优先队列的实现

    template,class Compare = less>class priority_queue{public://无参构造函数priority_queue(){}//迭代器构造函数templatepriority_queue(InputIterator first, InputIterator last):_con(first, last){for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i){adjust_down(i);}}//向上调整void adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}//数据入堆void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}//向下调整void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}//删除堆顶数据void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}//提取堆顶数据const T& top(){return _con[0];}//检测堆是否为空bool empty(){return _con.empty();}//计算堆中有效元素的个数size_t size(){return _con.size();}private://vector作为底层容器Container _con;};

容器适配器

概念

适配器是一种设计模式,该模式是将一个类的接口转换成客户希望的另外一个接口

标准库中stack,queue的底层结构

stack,queue本身也可以存放元素,但在STL中只是将其称为容器适配器,因为stack和queue只是对其他容器的接口进行了包装,STL中默认使用deque作为容器

介绍deque

原理

deque:一种双开口的“连续”空间的数据结构,可以在头尾两端进行插入和删除操作,并且时间复杂度为O(1),与vector相比,头插效率高,不需要搬移元素;与list相比,空间利用率比较高

在这里插入图片描述
deque并不是真正连续的空间,而是由一段连续的小空间拼接而成的,实际上deque类似于一个动态二维数组,其底层结构如下

在这里插入图片描述

缺陷

不适合遍历,在遍历时,deque的迭代器要频繁地去检测其是否移动到某段小空间的边界,导致效率低。在实际中,需要线性结构时,大多情况下优先考虑vector和list,deque的应用是,STL用其作为stack和queue的底层数据结构

deque作为stack,queue底层默认容器

stack是先进后出的特殊线性数据结构,因此是要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器;queue是先进先出的线性数据结构只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层结构,STL选择deque作为其底层容器的原因如下

  1. stack和queue不需要遍历,只需要再固定的一端或者两端进行操作
  2. 在stack中元素增长时,deque比vector的效率高;queue中元素增长时,deque不仅效率高,而且内存使用率高

总的来说就是,结合了deque的有点,并且完美地避开其缺点

相关内容

热门资讯

存储芯片巨头的好日子何时结束 ... 摩根士丹利最新报告指出,旧存储芯片行业的前景被低估。曾经因供需失衡而获得高额利润的旧存储芯片现在正处...
国足开场2分钟落后 邵佳一眉头... 点击加载图片直播吧11月17日讯 国足开场2分钟丢球,0-1落后巴林,镜头给到眉头紧锁的邵佳一。国字...
小米:相关内容纯属虚构,警惕虚... 小米旗下微博账号“小米辟谣”于11月17日发布声明,指出近期有不法分子冒充“小米汽车”发送诈骗短信,...
最差密码榜单公布 123456... 网络安全公司 NordPass 发布了《2026 年最常用密码 Top 200》报告,指出“1234...
2岁孩子生命最后11天依然努力... 25岁的妈妈将患有罕见病的儿子兜兜送进了长沙的“雏菊之家”安宁病房。她陪伴儿子度过了最后11天,并每...
13岁少年被控杀害5岁男童案 ... 一名13岁少年因妹妹被邻居5岁男童撒沙而心生怨恨,将男童带至桥上推下水致其溺亡。此案引起了媒体的广泛...
全球顶尖科学家加速回流中国 风... 全球顶尖科学家纷纷选择离开美国,转向中国任职。2026年初,莱斯大学90后斯隆奖得主汪淏田全职加盟同...
APEC工商领导人峰会今天聚焦... 11月17日,来自亚太经合组织21个经济体及英国、法国、德国、瑞士等13个域外经济体的2000多位政...
雷军APEC发言 具身智能潜力... 11月17日,小米CEO雷军在2026年APEC工商领导人峰会上表示,具身智能机器人的潜力超过汽车,...
俄罗斯记者惊呼在深圳谁还用现金... 11月17日,今日俄罗斯国际通讯社记者德米特里·加夫里洛夫在接受采访时分享了他的深圳体验。他提到,刚...
雷军:智能机器人产业潜力超汽车... 11月17日,在2026年亚太经合组织工商领导人峰会上,小米CEO雷军介绍了公司在AI、智能制造和机...
保研举报成风,这不只是“坏人变... 保研举报成风,这不只是“坏人变小了” 制度留操作空间。高校保研季举报成风:这不是学生坏,是制度留了太...
广东01年医护女孩为00年闺蜜... 据河南广播电视台小莉帮忙,广东一位01年的女孩,亲自为自己00年的闺蜜接生。她们的缘分有多深?女孩称...
广东网友为迎接APEC会议周有... 11月14日,2026年APEC领导人会议周新闻中心举办了广东省、深圳市专场中外媒体吹风会。这是20...
动车插座在头顶被吐槽像在打吊瓶... 近日,有网友在社交平台发帖分享自己的乘车经历:乘坐D2928次动车组时,发现车厢内的充电插座安装在顶...
万斯称与特朗普无分歧 一致反对... JD·万斯周一表示,他与总统唐纳德·特朗普在伊朗战争问题上完全一致。此前,他曾将共和党在中期选举中的...
痛风人群这4种饮品要少喝 咖啡... 很多尿酸高、痛风人群都知道啤酒、果汁会升高尿酸,那么有没有什么饮料对尿酸“很友好”,甚至还能降低痛风...
医生辟谣左侧睡根本不伤心:正常... 11月17日,经常朝左睡对心脏的影响引发关注。从解剖学角度看,心脏虽然位于胸腔偏左,但它并非孤零零地...
96岁奶奶扒着车窗含泪送孙女返... 近日,湖南,假期快要结束,孙女准备返程。96岁的奶奶扒着车窗,眼里满是不舍。一句有空常回家看看,戳中...
人民日报:从《持械入宋》火爆看... 有能够让行业内外普遍认可的作品出现,是一种新文艺类型成熟的重要标志。正是因为“家里家外”系列、《盛夏...