初识C++ · 模拟实现stack和Queue
目录
前言:
1 Stack
1.1 双端队列
2 Queue
前言:
经历了list三个自定义类型的洗礼,来个简单的放松放松,即栈和队列:


文档记录的,栈和队列是一种容器适配器,它们不属于stl,但是它们的大体结构我们都是了解的,在数据结构初阶我们已经用了C语言进行实现,这里用C++进行实现。
1 Stack
根据文档,stack也是使用了模板,第一个参数是数据类型,那么第二个是?
我们在C语言阶段使用的是一个整型指针,一个size一个capacity来实现,如果我们在C++仍然这样实现就不用介绍了,没意思了就。
后面的参数deque是另一种结构,叫做双端队列,后面细说,为什么引入第二个模板参数呢?
因为我们有了vector list基础,完全可以复用的,为什么复用vector list,就和deque有关了。
1.1 双端队列
deque是双端队列,那么为什么在stack queue的模板参数里面都有这个结构呢?
因为这个结构集成了vector和list,但是不是只集成了它们的优点。
先简单谈谈deque的结构:
list的优点是插入删除效率很高,缺点是不好访问数据,vector的优点是访问任意数据的效率很高,缺点是插入删除数据如果在头部或者中间的效率很低。
所以惠普的大佬就寻思再来一个结构,可以当vector用也可以当list使用,这里因为是了解,所以就直接给结构了:
看起来就像是个大boss,当我们存数据的时候,该结构会开一块空间,比如叫buff,空间大小为16,当一直插入数据,该数据插满之后,不会扩容,会重新开一块空间,空间大小也是16,数据插好后,我们该如何快速访问呢?
假定开的空间大小不变,我们想访问第i个数据,一块空间的大小为N,那么我们就应该先找到i数据在第几个空间的,在找该数据在第几个,找到在哪个空间可以i / N,第几个可以i % N,这样就可以快速访问了。
那么这么多空间应该如何管理?
这里使用的是中控指针,即再开一块空间,这块空间里面只有指针,指针指向不同的空间,但是指针是从中间开始存储的,因为涉及到头插。
但是对于deque的结构来说,只有两个迭代器,一个迭代器有4个指针,分别指向当前节点,头结果,尾节点和中控指针的节点,如果涉及到了插入删除数据,比如头插,就要先开一块空间,倒着存数据,那么此时找数据,i就要先减去这个不满的第一个数据块的数据个数,才能通过/ % 快速访问数据。中间插入数据的时候,有两个选择,一是重新开空间,二是在原来的空间上扩容,但是扩容之后,每个空间的大小不一样,找数据的效率就会降低了。
当涉及删除数据的时候,删除了之后,后面的数据往前移动,比较麻烦。
所以别看deque集成了list vector,缺点也蛮多的。
比如访问数据的效率不极致,中间插入删除数据也没list快,它就比较尴尬。。
这也是为什么,stack queue的模板参数默认是deque,这个"大哥"虽然有点缺点,但是用起来也算不错。
我们在stack实现的接口有入栈 出栈 size empty 返回栈顶元素,只有5个接口,这5个接口在vector里面都有,所以,直接使用:
namespace Free3
{template <class T, class container = vector<T>>class stack{public:void push(const T& val){_con.push_back(val);}size_t size(){return _con.size();}bool empty(){return _con.empty();}T& top(){return _con.back();}void pop(){_con.pop_back();}private:container _con;};}
这里有个很牛逼的点就是,模板参数也可以有缺省值,我们给上vector<int>,那么默认的用vector来实现stack。
测试代码如下:
#include "Stack.h"
using namespace Free3;
int main()
{Free3::stack<int, vector<int>> s1;Free3::stack<int> s2;s1.push(1);s1.push(2);s1.push(3);s1.push(4); s2.push(1);s2.push(2);s2.push(3);s2.push(4);s2.push(5);while (!s2.empty()){cout << s2.top() << " ";s2.pop();}cout << endl;return 0;
}
2 Queue
队列这里还有点不一样,栈可以用vector也可以用list,但是队列不行,队列的出队,相当于是头删,如果非要用vector里面的erase来头删也可以,但是效率很差,是O(N),这里就非常不推荐,所以队列就用list来实现。
namespace Free4
{template<class T>class Queue{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_front();}size_t size(){return _con.size();}T& front(){return _con.front();}bool empty(){return _con.empty();}private:list<T> _con;};}
感谢阅读!
相关文章:
初识C++ · 模拟实现stack和Queue
目录 前言: 1 Stack 1.1 双端队列 2 Queue 前言: 经历了list三个自定义类型的洗礼,来个简单的放松放松,即栈和队列: 文档记录的,栈和队列是一种容器适配器,它们不属于stl,但是它…...
MFC工控项目实例之一主菜单制作
1、本项目用在WIN10下安装的vc6.0兼容版实现。创建项目名为SEAL_PRESSURE的MFC对话框。在项目res文件下添加相关256色ico格式图片。 2、项目名称:密封压力试验机 主菜单名称: 系统参数 SYS_DATA 系统测试 SYS_TEST 选择型号 TYP_CHOICE 开始试验 TES_STA…...
JVMの堆、栈内存存储
1、JVM栈的数据存储 通过前面的学习,我们知道,将源代码编译成字节码文件后,JVM会对其中的字节码指令解释执行,在解释执行的过程中,又利用到了栈区的操作数栈和局部变量表两部分。 而局部变量表又分为一个个的槽位&…...
二叉树—堆(C语言实现)
一、树的概念及结构 1.树的概念 树是一种非线性的数据结构,它是有n(n > 0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树,也就是说它是根朝上,而叶朝下。 ● 有一个特殊的结点…...
儿童有声挂图的芯片AD156—云信通讯
有声挂图是一种结合了图像和声音的媒体形式,用户可以触发图像上的声音,从而获得与图像内容相关的音频信息。这种融合了视觉和听觉的交互方式,既满足了人们对美感和观感的需求,又提高了信息传递的效果和效率。 有声挂图作为孩子的…...
AI推介-多模态视觉语言模型VLMs论文速览(arXiv方向):2024.04.25-2024.05.01
文章目录~ 1.Soft Prompt Generation for Domain Generalization2.Modeling Caption Diversity in Contrastive Vision-Language Pretraining3.Q-GroundCAM: Quantifying Grounding in Vision Language Models via GradCAM4.HELPER-X: A Unified Instructable Embodied Agent t…...
gdb调试常见指令
quit:退出gdb list/l:l 文件名:行号/函数名,l 行号/函数名 b:b 文件名:行号/函数名,b 行号/函数名 info/i: info b d:d 断电编号 disable/enable 断电编号:使能(关闭࿰…...
二进制安装mysql8.1
MySQL的安装各个版本步骤几乎一致,本文以安装8.1为例 创建用户及安装需要的依赖包 创建用户及用户组 groupadd mysql useradd -g mysql -s /sbin/nologin mysql 安装依赖包 apt install libncurses5 libncursesw5 libaio1 numactl wget -y 获取二进制包 可以…...
前端工程化工具系列(六)—— VS Code(v1.89.1):强大的代码编辑器
VS Code(Visual Studio Code)是一款由微软开发的强大且轻量级的代码编辑器,支持多种编程语言,并提供了丰富的扩展插件生态系统。 这里主要介绍如何使用配置 ESLint、Stylelint 等插件来提升开发效率。 1 自动格式化代码 最终要…...
重学java 59.Properties属性集集合嵌套集合下总结
不要咀嚼小小悲观,而忘掉整个世界 —— 24.6.3 一、Properties集合(属性集) 1.概述 Properties 继承 于HashTable 2.特点 a、key唯一,value可重复 b、无序 c、无索引 d、线程安全 e、不能存null键,null值 f、Propertie…...
Kafka系列之高频面试题
基础 简介 特点: 高吞吐、低延迟:kafka每秒可以处理几十万条消息,延迟最低只有几毫秒,每个Topic可以分多个Partition,Consumer Group对Partition进行Consumer操作可扩展性:Kafka集群支持热扩展持久性、可…...
SIP通话分析
20240603 - 引言 分析SIP协议的时候,发现了几个问题。虽然说,从整体上来看这个SIP的通话流程也没麻烦,实际上从RFC的概述部分就已经基本上就已经了解了全貌。但在实际的场景中,很多字段起到的作用就不太一样了。 虽然一开始的时…...
【SVG 生成系列论文(九)】如何通过文本生成 svg logo?IconShop 模型推理代码详解
SVG 生成系列论文(一) 和 SVG 生成系列论文(二) 分别介绍了 StarVector 的大致背景和详细的模型细节。SVG 生成系列论文(三)和 SVG 生成系列论文(四)则分别介绍实验、数据集和数据增…...
有哪些兼职软件一天能赚几十元?盘点十个能长期做下去的挣钱软件
在当今这个信息泛滥的时代,众人纷纷寻求迅速致富的捷径。许多人在从事兼职或副业时,并不期望取得巨大的成就,只要每天能额外收入数十元,便已心满意足。 今天,我将带领大家深入探究,揭开那些隐藏在日常生活…...
ubuntu 22.04配置静态ip
ubuntu 22.04配置静态ip vim /etc/netplan/01-network-manager-all.yaml# Let NetworkManager manage all devices on this system network:renderer: NetworkManagerethernets:enp4s0f1:addresses:- 192.168.1.18/24dhcp4: falseroutes:- to: defaultvia: 192.168.1.1nameser…...
C++ 使用 nlohmann/json 库
C常用 json 库有: Jsoncpp boost ison Qt Json (不推荐使用) nlohman::json (推荐使用) 其中Qt中json解析的相关类只在qt中有用,为了避免以后不用qt无法解析json,建议使用nlohmann/json,适用于任何C框架。 1. 简介 nlohmann是一…...
【Java面试】六、Spring框架相关
文章目录 1、单例Bean不是线程安全的2、AOP3、Spring中事务的实现4、Spring事务失效的场景4.1 情况一:异常被捕获4.2 情况二:抛出检查异常4.3 注解加在非public方法上 5、Bean的生命周期6、Bean的循环引用7、Bean循环引用的解决:Spring三级缓…...
【GIC400】——PLIC,NVIC 和 GIC 中断对比
文章目录 PLIC,NVIC 和 GIC 中断对比中断向量表PLIC中断向量表中断使能中断服务函数NVIC中断向量表中断使能中断服务函数GIC中断向量表系列文章 【ARMv7-A】——异常与中断 【ARMv7-A】——异常中断处理概述...
17.Redis之主从复制
1.主从复制是怎么回事? 分布式系统, 涉及到一个非常关键的问题: 单点问题 单点问题:如果某个服务器程序, 只有一个节点(只搞一个物理服务器, 来部署这个服务器程序) 1.可用性问题,如果这个机器挂了,意味着服务就中断了~ 2.性能/支持的并发量也是比较有限…...
计算机类专业应该怎么选学校和方向?优先选这些!
👆点击关注 获取更多编程干货👆 高考季临近,不少有意向报考计算机专业的同学在为院校和细分专业的选择而苦恼,以下是一些建议,希望能帮到大家! 01 选校建议 在选择计算机科学(CS)…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
