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

初识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

目录 前言&#xff1a; 1 Stack 1.1 双端队列 2 Queue 前言&#xff1a; 经历了list三个自定义类型的洗礼&#xff0c;来个简单的放松放松&#xff0c;即栈和队列&#xff1a; 文档记录的&#xff0c;栈和队列是一种容器适配器&#xff0c;它们不属于stl&#xff0c;但是它…...

MFC工控项目实例之一主菜单制作

1、本项目用在WIN10下安装的vc6.0兼容版实现。创建项目名为SEAL_PRESSURE的MFC对话框。在项目res文件下添加相关256色ico格式图片。 2、项目名称&#xff1a;密封压力试验机 主菜单名称&#xff1a; 系统参数 SYS_DATA 系统测试 SYS_TEST 选择型号 TYP_CHOICE 开始试验 TES_STA…...

JVMの堆、栈内存存储

1、JVM栈的数据存储 通过前面的学习&#xff0c;我们知道&#xff0c;将源代码编译成字节码文件后&#xff0c;JVM会对其中的字节码指令解释执行&#xff0c;在解释执行的过程中&#xff0c;又利用到了栈区的操作数栈和局部变量表两部分。 而局部变量表又分为一个个的槽位&…...

二叉树—堆(C语言实现)

一、树的概念及结构 1.树的概念 树是一种非线性的数据结构&#xff0c;它是有n&#xff08;n > 0&#xff09;个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树&#xff0c;也就是说它是根朝上&#xff0c;而叶朝下。 ● 有一个特殊的结点…...

儿童有声挂图的芯片AD156—云信通讯

有声挂图是一种结合了图像和声音的媒体形式&#xff0c;用户可以触发图像上的声音&#xff0c;从而获得与图像内容相关的音频信息。这种融合了视觉和听觉的交互方式&#xff0c;既满足了人们对美感和观感的需求&#xff0c;又提高了信息传递的效果和效率。 有声挂图作为孩子的…...

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&#xff1a;退出gdb list/l&#xff1a;l 文件名&#xff1a;行号/函数名&#xff0c;l 行号/函数名 b:b 文件名&#xff1a;行号/函数名&#xff0c;b 行号/函数名 info/i: info b d:d 断电编号 disable/enable 断电编号&#xff1a;使能&#xff08;关闭&#xff0…...

二进制安装mysql8.1

MySQL的安装各个版本步骤几乎一致&#xff0c;本文以安装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&#xff08;Visual Studio Code&#xff09;是一款由微软开发的强大且轻量级的代码编辑器&#xff0c;支持多种编程语言&#xff0c;并提供了丰富的扩展插件生态系统。 这里主要介绍如何使用配置 ESLint、Stylelint 等插件来提升开发效率。 1 自动格式化代码 最终要…...

重学java 59.Properties属性集集合嵌套集合下总结

不要咀嚼小小悲观&#xff0c;而忘掉整个世界 —— 24.6.3 一、Properties集合&#xff08;属性集&#xff09; 1.概述 Properties 继承 于HashTable 2.特点 a、key唯一&#xff0c;value可重复 b、无序 c、无索引 d、线程安全 e、不能存null键&#xff0c;null值 f、Propertie…...

Kafka系列之高频面试题

基础 简介 特点&#xff1a; 高吞吐、低延迟&#xff1a;kafka每秒可以处理几十万条消息&#xff0c;延迟最低只有几毫秒&#xff0c;每个Topic可以分多个Partition&#xff0c;Consumer Group对Partition进行Consumer操作可扩展性&#xff1a;Kafka集群支持热扩展持久性、可…...

SIP通话分析

20240603 - 引言 分析SIP协议的时候&#xff0c;发现了几个问题。虽然说&#xff0c;从整体上来看这个SIP的通话流程也没麻烦&#xff0c;实际上从RFC的概述部分就已经基本上就已经了解了全貌。但在实际的场景中&#xff0c;很多字段起到的作用就不太一样了。 虽然一开始的时…...

【SVG 生成系列论文(九)】如何通过文本生成 svg logo?IconShop 模型推理代码详解

SVG 生成系列论文&#xff08;一&#xff09; 和 SVG 生成系列论文&#xff08;二&#xff09; 分别介绍了 StarVector 的大致背景和详细的模型细节。SVG 生成系列论文&#xff08;三&#xff09;和 SVG 生成系列论文&#xff08;四&#xff09;则分别介绍实验、数据集和数据增…...

有哪些兼职软件一天能赚几十元?盘点十个能长期做下去的挣钱软件

在当今这个信息泛滥的时代&#xff0c;众人纷纷寻求迅速致富的捷径。许多人在从事兼职或副业时&#xff0c;并不期望取得巨大的成就&#xff0c;只要每天能额外收入数十元&#xff0c;便已心满意足。 今天&#xff0c;我将带领大家深入探究&#xff0c;揭开那些隐藏在日常生活…...

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 库有&#xff1a; Jsoncpp boost ison Qt Json (不推荐使用) nlohman::json (推荐使用) 其中Qt中json解析的相关类只在qt中有用&#xff0c;为了避免以后不用qt无法解析json&#xff0c;建议使用nlohmann/json&#xff0c;适用于任何C框架。 1. 简介 nlohmann是一…...

【Java面试】六、Spring框架相关

文章目录 1、单例Bean不是线程安全的2、AOP3、Spring中事务的实现4、Spring事务失效的场景4.1 情况一&#xff1a;异常被捕获4.2 情况二&#xff1a;抛出检查异常4.3 注解加在非public方法上 5、Bean的生命周期6、Bean的循环引用7、Bean循环引用的解决&#xff1a;Spring三级缓…...

【GIC400】——PLIC,NVIC 和 GIC 中断对比

文章目录 PLIC,NVIC 和 GIC 中断对比中断向量表PLIC中断向量表中断使能中断服务函数NVIC中断向量表中断使能中断服务函数GIC中断向量表系列文章 【ARMv7-A】——异常与中断 【ARMv7-A】——异常中断处理概述...

17.Redis之主从复制

1.主从复制是怎么回事&#xff1f; 分布式系统, 涉及到一个非常关键的问题: 单点问题 单点问题&#xff1a;如果某个服务器程序, 只有一个节点(只搞一个物理服务器, 来部署这个服务器程序) 1.可用性问题,如果这个机器挂了,意味着服务就中断了~ 2.性能/支持的并发量也是比较有限…...

计算机类专业应该怎么选学校和方向?优先选这些!

&#x1f446;点击关注 获取更多编程干货&#x1f446; 高考季临近&#xff0c;不少有意向报考计算机专业的同学在为院校和细分专业的选择而苦恼&#xff0c;以下是一些建议&#xff0c;希望能帮到大家&#xff01; 01 选校建议 在选择计算机科学&#xff08;CS&#xff09…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...