当前位置: 首页 > news >正文

【玩转c++】stack和queue的介绍和模拟实现

本期主题:list的讲解和模拟实现

博客主页: 小峰同学

分享小编的在Linux中学习到的知识和遇到的问题

小编的能力有限,出现错误希望大家不吝赐

  1. 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的介绍和模拟实现

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

Linux order(文件、磁盘、网络、系统管理、备份压缩)

1. Linux 文件命令 -rwxrwxrwx chmod&#xff1a;change mode&#xff0c;用于&#xff08;文件所有者或 root &#xff09;变更用户(u:owner g:group o:other a:all)的权限 chmod [OPTION]… MODE[,MODE]… FILE… OPTION -R&#xff1a;递归修改more option&#xff1a;chmod…...

最详细的CentOS7安装Mysql数据库服务

1.查看是否安装mysql: rpm -qa | grep mysql如果有查出来东西&#xff0c;使用命令删除&#xff1a; rpm -e xxx2.检查是否有mysql用户组和mysql用户,没有就添加有就忽略&#xff1a; groups mysql 添加用户组和用户 groupadd mysql && useradd -r -g mysql mysql&a…...

【IoT】项目管理:如何做好端到端的项目管理?

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

渲染十万条数据就把你难住了?不存在的!

虚拟列表的使用场景如果我想要在网页中放大量的列表项&#xff0c;纯渲染的话&#xff0c;对于浏览器性能将会是个极大的挑战&#xff0c;会造成滚动卡顿&#xff0c;整体体验非常不好&#xff0c;主要有以下问题&#xff1a;页面等待时间极长&#xff0c;用户体验差CPU计算能力…...

编程学习的心路历程和困惑回顾

回首入行9年的经历&#xff0c;从大一开始学习C语言和数据结构&#xff0c;老师一直是在用IDE演示程序的编写和运行&#xff0c;我们也就一直在跟黑乎乎的命令行窗口打交道。 后来在一些课程的实验环节&#xff0c;接触到了一些别人编写好的工程代码&#xff0c;知道了Makefile…...

请介绍类加载过程,什么是双亲委派模型?

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

Navisworks编辑材质和Revit快速切换材质问题

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

Object对象键值的输出循序到底如何排列的?

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

气泡式水位计的安装方法详解

气泡水位计的安装实际上就是气管的安装&#xff0c;气管的安装是否正确将直接影响到仪器测量数据的结果&#xff0c;气泡水位计它由活塞泵产生的压缩空气流经测量管和气泡室&#xff0c;进入被测的水体中&#xff0c;测量管中的静压力与气泡室上的水位高度成正比。那么接下来就…...

求“二维随机变量的期望E(X)与方差D(X)”例题(一)

离散型 设随机变量(X,Y)的联合分布律为 X\Y0100.10.210.30.4 (1)求E(X) 先求x的边缘分布律&#xff0c;表格里x0的概率为0.10.2&#xff0c;于是我们可得 X01P0.30.7直接求E(X)即可&#xff0c;得到结果 (2)求E(XY) 直接x与y相乘就行。 记得别乘多了&#xff0c;别的算了又…...

MySQL 搞定行转列,列转行

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

正点原子裸机开发之C语言点灯程序

一. 简介 本文针对 IMX6ULL 的裸机开发的&#xff08;即不带Linux操作系统的开发&#xff09;。 主要分两部分的工作&#xff1a; 1. 配置 C语言运行环境 2. C 语言编写及运行 二. 配置C语言运行环境 配置 C 语言运行环境的工作分 三部分。如下&#xff1a; 1. 设置…...

cv::阈值分割OTUS原理+代码

opencv库的阈值分割分为全局分割和局部分割全局分割&#xff1a;普通分割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局部分割&#xff1a;…...

Postgresql-12.5 visual studio-2022 windows 添加pg工程并调试

pg内核学习&#xff0c;记录一下 文章目录安装包编译安装VS添加Postgresql工程调试源码安装包 &#xff08;1&#xff09;perl下载 https://www.perl.org/get.html &#xff08;2&#xff09;diff下载 http://gnuwin32.sourceforge.net/packages/diffutils.htm &#xff08;…...

长沙学院2023 第一次蓝桥训练题解

每道题都在洛谷上&#xff0c;每个题都有很详细的题解&#xff0c;可以先自行做&#xff0c;不会再看题解。 题目解析思路都写在代码中&#xff0c;中文题面就不单独解释题意了。 P2440 木材加工&#xff08;二分答案&#xff09; 链接&#xff1a;P2440 木材加工 解析 代码…...

云端Docker搭建ABY库以及本地CLion使用

文章目录ABY的搭建以及使用前言ABY库的下载、安装及测试CLion配置后续杂项项目改名使用其他的库最后ABY的搭建以及使用 前言 仅做记录&#xff0c;仅供参考&#xff0c;不同人有不同的使用方式命令手敲&#xff0c;可能有错&#xff0c;自己辨识勿问&#xff0c;我懂的也不多…...

ES6-箭头函数、解构赋值、对象简写

箭头函数特点 1、 (只有1个形参) 可以省略() 2、 {} 可以省略 只有一句代码 或 只有返回值的时候,省略return 3、arguments 不可用&#xff0c;arguments在没有形参的时候可以拿到调用函数拿在的实参 获取伪数组通过Array.from转为真数组。 4、 箭头函数没有this&#xff0c; …...

【CSS】CSS 背景设置 ② ( 背景位置 | 背景位置-方位值设置 )

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

HTML 扫盲

✏️作者&#xff1a;银河罐头 &#x1f4cb;系列专栏&#xff1a;JavaEE &#x1f332;“种一棵树最好的时间是十年前&#xff0c;其次是现在” 目录前言HTML 结构快速生成代码框架HTML 常见标签注释标签标题标签: h1-h6段落标签&#xff1a;p换行标签&#xff1a;br格式化标签…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

Java数组Arrays操作全攻略

Arrays类的概述 Java中的Arrays类位于java.util包中&#xff0c;提供了一系列静态方法用于操作数组&#xff08;如排序、搜索、填充、比较等&#xff09;。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序&#xff08;sort&#xff09; 对数组进行升序…...