【玩转c++】stack和queue的介绍和模拟实现
本期主题:list的讲解和模拟实现
博客主页: 小峰同学
分享小编的在Linux中学习到的知识和遇到的问题
小编的能力有限,出现错误希望大家不吝赐

stack的介绍和使用
1.1.stack的介绍
1. stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行 元素的插入与提取操作。
2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定 的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出。
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下 操作: empty:判空操作 back:获取尾部元素操作 push_back:尾部插入元素操作 pop_back:尾部删除元素操作
4. 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器, 默认情况下使用deque。

1.2.stack的使用
stack的接口很少,就下面的几个,主要的是结构很好。学习这种结构和,怎么模拟实现。

2. queue的介绍和使用
2.1.queue的介绍
1. 队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端 提取元素。
2. 队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列,从队头出队列。
3. 底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操 作: empty:检测队列是否为空 size:返回队列中有效元素的个数 front:返回队头元素的引用 back:返回队尾元素的引用 push_back:在队列尾部入队列 pop_front:在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标 准容器deque。

2.2. queue的使用
这里就很简单啦

3.stack和queue的模拟实现
3.1.stack模拟实现
直接上源码
namespace zxf
{//以前我们在实现栈的时候//往往回去直接一个动态数组,手动来控制元素。//template<class T>//class stack//{//private:// T* _parr;// size_t _top;// size_t capacity;//};//c++这样写就很麻烦。//所以就会有一种很简单的设计模式。//就是:适配器模式//适配器模式: 就是使用已经存在的东西去封装转换出自己想要的东西,不需要我们自己去实现。template<class T, class container = deque<T>>class stack{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_back();}bool empty(){return _con.empty();}T& top(){//return *(_con.end()-1);return _con.back();//vector 和 list 都支持 back() 这个接口。}size_t size(){return _con.size();}private://这里可以写死是 vector ,或者 list //vector<T> _vt;//list<T> _lt;//也可以不写死,在来一个模板参数container _con;//调用的时候传入两个类型参数即可。//stack<int , vector<int>> st1;//stack<int , list<int>> st1;};
}
知识点:
1.这里使用了一种设计模式叫适配器模式。
2.适配器模式就是使用就是使用已经存在的东西去封装转换出自己想要的东西,不需要我们自己去实现
3.这里用vector 或者 list 去实现 stack的类型。
3.2.queue模拟实现
直接上源码
namespace zxf
{//也是使用是适配器模式来实现的啦。//stl 库中实现的时候 给第二个参数container一个缺省参数 deque<T>template<class T ,class container = deque<T>>class queue{public:void pop(){_con.pop_front();//注意 vector 没有实现 pop_front()接口 。}void push(const T& val){_con.push_back(val);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& back(){return _con.back();} const T& front(){return _con.front();}private:container _con;//调用的时候传入两个类型参数即可。//queue<int , vector<int>> st1;//queue<int , list<int>> st1;};
}
1.也是适配器模式的实现,适配器的好处,就是使用简单,方便, 上面我们给模板的第二个参数 可以是 stl中已经存在的,也可以是我们自己写一个只要含有哪些接口 都可以 ,适配成这样的.
2.stl库中的queue 和stack 都是适配器实现的.
4.简单介绍deque
4.1.deque的原理介绍
1.deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),
2.与vector比较,头插效率高,不需要搬移元素;
与list比较,空间利用率比 较高.
3.感觉兼具 list 和 vector的优点于一身.

接口我就不一一讲解了. 经给stl的学习,肯定看一眼就可以懂了.
deque文本介绍
deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组,其底层结构如下图所示:

1,要尾部插入直接就插入了,但是想头部插入的时候,需要在首节点的的前面再开一个常数大小的数组,插入数据.空间浪费也解决了.
2.双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落 在了deque的迭代器身上,因此deque的迭代器设计就比较复杂,如下图所示:

那deque是如何借助其迭代器维护其假想连续的结构呢?

4.2.deque的缺陷
1.deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到 某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历.
2.因此在实际中,需要线性结构 时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作 为stack和queue的底层数据结构。
3.中间插入删除也不好做,需要挪动数据.
4.deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不 需要搬移大量的元素,因此其效率是比vector高的。 与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。
5.中间插入删除少,头部尾部插入删除多,偶尔随机访问,甚至不随机访问,的适合使用 deque.常见的就是作为stack和queue的底层数据结构.
4.3.为什么选择deque作为stack和queue的底层默认容器
1,stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可 以作为stack的底层容器,比如vector和list都可以;
2,queue是先进先出的特殊线性数据结构,只要具有 push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如list。
但是STL中对stack和 queue默认选择deque作为其底层容器,主要是因为:
1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长 时,deque不仅效率高,而且内存使用率高。
相关文章:

【玩转c++】stack和queue的介绍和模拟实现
本期主题:list的讲解和模拟实现博客主页: 小峰同学分享小编的在Linux中学习到的知识和遇到的问题小编的能力有限,出现错误希望大家不吝赐stack的介绍和使用1.1.stack的介绍1. stack是一种容器适配器,专门用在具有后进先出操作的上…...

Linux order(文件、磁盘、网络、系统管理、备份压缩)
1. Linux 文件命令 -rwxrwxrwx chmod:change mode,用于(文件所有者或 root )变更用户(u:owner g:group o:other a:all)的权限 chmod [OPTION]… MODE[,MODE]… FILE… OPTION -R:递归修改more option:chmod…...

最详细的CentOS7安装Mysql数据库服务
1.查看是否安装mysql: rpm -qa | grep mysql如果有查出来东西,使用命令删除: rpm -e xxx2.检查是否有mysql用户组和mysql用户,没有就添加有就忽略: groups mysql 添加用户组和用户 groupadd mysql && useradd -r -g mysql mysql&a…...

【IoT】项目管理:如何做好端到端的项目管理?
今天主要来谈谈项目管理这个话题。 首先来看一个我在网络上看到的一个关于项目管理的案例或者是段子。 将项目管理的作用及意义非常直观地展示了出来。 有一个植树搞绿化的企业,在公司内部设置有五个部门,分别是: 运输部门;挖坑部…...

渲染十万条数据就把你难住了?不存在的!
虚拟列表的使用场景如果我想要在网页中放大量的列表项,纯渲染的话,对于浏览器性能将会是个极大的挑战,会造成滚动卡顿,整体体验非常不好,主要有以下问题:页面等待时间极长,用户体验差CPU计算能力…...
编程学习的心路历程和困惑回顾
回首入行9年的经历,从大一开始学习C语言和数据结构,老师一直是在用IDE演示程序的编写和运行,我们也就一直在跟黑乎乎的命令行窗口打交道。 后来在一些课程的实验环节,接触到了一些别人编写好的工程代码,知道了Makefile…...

请介绍类加载过程,什么是双亲委派模型?
第23讲 | 请介绍类加载过程,什么是双亲委派模型? Java 通过引入字节码和 JVM 机制,提供了强大的跨平台能力,理解 Java 的类加载机制是深入 Java 开发的必要条件,也是个面试考察热点。 今天我要问你的问题是࿰…...

Navisworks编辑材质和Revit快速切换材质问题
一、如何在Navisworks2016中编辑材质 初次使用NW2016-2017时发现,原来用于创建编辑材质的小地球不见了,如图1所示,在各大技术群里求助没有回应,度娘搜索也总是摇头。 经过仔细排查可能出现的地方,终于找到了可以编辑材…...

Object对象键值的输出循序到底如何排列的?
1.日常摸鱼看八股 今天又是复习八股文的一天,发现还是彻底懂得原理才好和面试官吹牛批呀。 接着来看看我chat大宝贝的回答: 在现代浏览器中,Object 对象的键值输出循序是比较稳定的,通常是按照如下顺序输出: 所有的数…...

气泡式水位计的安装方法详解
气泡水位计的安装实际上就是气管的安装,气管的安装是否正确将直接影响到仪器测量数据的结果,气泡水位计它由活塞泵产生的压缩空气流经测量管和气泡室,进入被测的水体中,测量管中的静压力与气泡室上的水位高度成正比。那么接下来就…...
求“二维随机变量的期望E(X)与方差D(X)”例题(一)
离散型 设随机变量(X,Y)的联合分布律为 X\Y0100.10.210.30.4 (1)求E(X) 先求x的边缘分布律,表格里x0的概率为0.10.2,于是我们可得 X01P0.30.7直接求E(X)即可,得到结果 (2)求E(XY) 直接x与y相乘就行。 记得别乘多了,别的算了又…...

MySQL 搞定行转列,列转行
行转列方法总结1、使用case…when…then2、使用SUM(IF()) 生成列3、使用SUM(IF()) 生成列 WITH ROLLUP 生成汇总行4、使用SUM(IF()) 生成列 UNION 生成汇总行,并利用 IFNULL将汇总行标题显示为 Total5、使用SUM(IF()) 生成列,直接生成汇总结果,不再利用…...

正点原子裸机开发之C语言点灯程序
一. 简介 本文针对 IMX6ULL 的裸机开发的(即不带Linux操作系统的开发)。 主要分两部分的工作: 1. 配置 C语言运行环境 2. C 语言编写及运行 二. 配置C语言运行环境 配置 C 语言运行环境的工作分 三部分。如下: 1. 设置…...

cv::阈值分割OTUS原理+代码
opencv库的阈值分割分为全局分割和局部分割全局分割:普通分割ret1,th1 cv2.threshold(img,127, 255, cv2.THRESH_BINARY) #127为阈值 #cv2.THRESH_BINARY |cv2.THRESH_BINARY_INV | cv2.THRESH_TRUNC|cv2.THRESH_TOZERO|cv2.THRESH_TOZERO_INV局部分割:…...

Postgresql-12.5 visual studio-2022 windows 添加pg工程并调试
pg内核学习,记录一下 文章目录安装包编译安装VS添加Postgresql工程调试源码安装包 (1)perl下载 https://www.perl.org/get.html (2)diff下载 http://gnuwin32.sourceforge.net/packages/diffutils.htm (…...
长沙学院2023 第一次蓝桥训练题解
每道题都在洛谷上,每个题都有很详细的题解,可以先自行做,不会再看题解。 题目解析思路都写在代码中,中文题面就不单独解释题意了。 P2440 木材加工(二分答案) 链接:P2440 木材加工 解析 代码…...

云端Docker搭建ABY库以及本地CLion使用
文章目录ABY的搭建以及使用前言ABY库的下载、安装及测试CLion配置后续杂项项目改名使用其他的库最后ABY的搭建以及使用 前言 仅做记录,仅供参考,不同人有不同的使用方式命令手敲,可能有错,自己辨识勿问,我懂的也不多…...
ES6-箭头函数、解构赋值、对象简写
箭头函数特点 1、 (只有1个形参) 可以省略() 2、 {} 可以省略 只有一句代码 或 只有返回值的时候,省略return 3、arguments 不可用,arguments在没有形参的时候可以拿到调用函数拿在的实参 获取伪数组通过Array.from转为真数组。 4、 箭头函数没有this, …...

【CSS】CSS 背景设置 ② ( 背景位置 | 背景位置-方位值设置 )
文章目录一、背景位置1、语法说明2、注意事项二、背景位置-方位值设置1、效果展示2、完整代码示例一、背景位置 1、语法说明 如果 盒子的大小 大于 背景图片的大小 , 默认的 图片 位置是 左上角 ; 设置背景位置的 CSS 语法如下 : background-position : length length backgro…...

HTML 扫盲
✏️作者:银河罐头 📋系列专栏:JavaEE 🌲“种一棵树最好的时间是十年前,其次是现在” 目录前言HTML 结构快速生成代码框架HTML 常见标签注释标签标题标签: h1-h6段落标签:p换行标签:br格式化标签…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...

linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...

Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

基于Springboot+Vue的办公管理系统
角色: 管理员、员工 技术: 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能: 该办公管理系统是一个综合性的企业内部管理平台,旨在提升企业运营效率和员工管理水…...