c++:stack与deque
1.stack使用
1.1empty
作用:判断栈中是否为空
我们看到这里s1初始化的时候是空初始化,所以用empty来判断出的就是空的栈
1.2size
size的作用就是判断栈中的数据个数
1.3push
与vector,string,list不同的是,stack中没有头插尾插的概念
因为栈有一个原则:后进先出。也就是他像杯子装水一样限制了我们只能从唯一接口进行数据插入与删除。所以也就自然没有push_back了,只有push
通过push,我们成功给栈插入了一个1
1.4pop
在pop前,栈中有一个1
pop之后栈中的1被删掉了
1.5top
我们按照顺序将1,2,3,4依次插入栈中,也就是说4应该是最后进栈的,他就是栈顶数据
2.容器适配器
适配器:是一种设计模式,他的目的是将一个接口转换成客户希望的另一个接口
容器适配器:就是将一个容器转换成另外一种容器
eg:vector/list -> stack
(1)只支持一种容器的写法
这里是使用数组实现栈,由于底层锁死了vector,所以要改成链表实现栈就很麻烦了,底层的都要改动
(2)支持多种容器的写法
这里面我们就可以将其他各种容器给到模板参数container,达到可以切换多种容器的目的
eg: m_stack<int,list<int>>
3.利用容器适配器实现stack
这里我们直接复用大部分容器中都有的方法来实现栈
注意:函数参数和模板参数是类似的,只不过函数参数传的是值,而模板参数传的是类型
所以我们的其中一种使用就是:my_stack<int, vector<int>> m;
不过我们其实需要给container一个默认容器类型,就像给函数参数一个缺省值一样。
4.deque
标准库中的栈默认的容器既不是数组,也不是链表,而是用deque。
vector:
优势:可以实现数据的随机高效访问
劣势:插入删除效率较低,扩容会有一定空间浪费
list:
优势:可以实现高效的随机存储,没有空间浪费
劣势:不支持下标随机访问
deque结合了数组随机读取的优势和链表插入删除方便的优势,但是也带来了一些新的问题
当只需要查找和头尾数据操作的时候,deque是可以完美替代vector与list的,除了这种情况,deque就会比较麻烦了
示意图:
vector是一段连续的长空间,存储所有数据
list是一个个断开的空间,存储一个个数据
deque是由中控数组与存储数组组成的,中控数组存储着存储数组的指针,负责从一个存储数组跳到另一个存储数组访问,存储数组是一大段连续空间存储数据,且存储数组的长度是一样的
接下来看看他的迭代器
迭代器由四个指针组成,其中三个是一级指针,一个是二级指针。
cur指向当前访问到的数据,first指向存储数组的首元素位置,last指向存储数组的尾元素位置
node指向中控数组中指向当前存储数组的指针
下面是更完整的结构
由于deque的应用场景是头尾的插入删除,所以这里主要有两个迭代器,分别是start与finish,他们分别是指向中控数组的第一个元素的指针,与最后一个元素的指针
(1)遍历
从first的cur开始遍历,不涉及存储数组转换就是cur++,涉及存储数组变化就改变node指针的指向,然后根据node指针取得first指针的地址并更新cur,再根据存储数组固定的元素个数推断出last的指针地址,这样就完成了迭代器的更新。
(2)尾部插入数据
数据没满:直接插入数据并cur++
数据满了:开一个新的存储数组,将数据存在新数组开头,更新finish迭代器
(3)头部插入数据
存储数组满了:开一个新的数组,把数据存在新数组的结尾,更新start迭代器
存储数组没满:直接插入,然后cur--
(4)下标随机访问
i/size求出在第几个存储数组,i%size求出在存储数组的第几个位置
插入与删除:
他们需要把pos后面的数据跨存储数组移动,效率很低
下标随机访问:
略低于vector
头尾插入删除:
优于vector和list排序:
用vector
5.priority_queue
priority_queue是优先级队列,他的底层是利用堆来实现的,默认大数据优先级更高。
5.1框架搭建
我们还是使用容器适配器来构建该容器
5.2插入
由于底层是堆,所以我们的插入是先直接插入到堆尾,然后向上调整,最后完成一个堆结构插入
5.3删除
堆的删除:先把首尾元素值交换,然后删除尾元素,接着向下调整
向下调整用到了假设法:我们先假设左孩子是较大的,然后进行判断,若实际上右孩子更大,则让child++。不过要注意,进行右孩子的访问前,需要确定有右孩子
5.4仿函数使用
我们前面实现的插入删除都是针对大堆的(大数据优先级高的),那如果我们要针对小堆,怎么实现?
方法一:在类中直接修改代码比较逻辑
方法二:使用仿函数
方法一的修改需要改动底层,且不适合做成模板,方法二可以写成模板,改动比较逻辑可以从接口处改动,不用动底层
接下来我们实现lessfuc仿函数
其实仿函数就是一个类中重载()运算符,然后在这个重载函数中实现函数的功能
由于lessfuc是大的数据优先级高,所以我们需要注意向上和向下调整中parent和child数据的位置
这里把parent的数据放在child之前,若parent<child,则交换数据,满足大数据优先
这里再讲解一个仿函数的应用
假设我们有一个date类,我们的比较逻辑是指针直接比较,但是我们希望的是指针指向的内容大小比较,我们就可以写一个仿函数,重载()运算符,实现指向内容的比较,然后传仿函数给date类
综上:仿函数可以增加一些代码的可变性,通过传不同的仿函数实现一个类兼容多种情况
相关文章:
c++:stack与deque
1.stack使用 1.1empty 作用:判断栈中是否为空 我们看到这里s1初始化的时候是空初始化,所以用empty来判断出的就是空的栈 1.2size size的作用就是判断栈中的数据个数 1.3push 与vector,string,list不同的是,stack中没有头插尾插的概念 因为栈有一个原则&…...
Linux-C/C++《C++/1、C++基础》(C++语言特性、面向对象等)
这里主要介绍概念为主,主要介绍 C与 C 语言中常用的不同点,和一些新的变化。其中不会去说指针、数据类型、变量类型、判断和循环等这些知识,这些和C 语言基本是一样使用的。我们主要学习 C的面向对象编程,对学习 Qt 有很大的帮助。…...
交易所开发:数字市场的核心动力
数字资产交易所作为连接用户与市场的核心枢纽,已成为推动数字经济发展的关键引擎。其开发不仅需要技术创新,还需兼顾用户体验、合规安全与生态构建,以下是交易所开发的核心要素与实践路径分析: 一、交易所的核心定位与技术架构…...
Spring Boot 应用(官网文档解读)
Spring Boot 启动方式 SpringApplication.run(MyApplication.class, args); Spring Boot 故障分析器 在Spring Boot 项目启动发生错误的时候,我们通常可以看到上面的内容,即 APPLICATION FAILED TO START,以及后面的错误描述。这个功能是通过…...
.Net面试宝典【刷题系列】
文章目录 1、JIT是如何工作的2、值类型和引用类型的区别3、解释泛型的基本原理4、如何自定义序列化和反序列化的过程5、如何使用 IFormattable 接口实现格式化输出6、请解释委托的基本原理7、什么是链式委托8、请解释反射的基本原理和其实现的基石9、如何利用反射来实现工厂模式…...
Unity游戏制作中的C#基础(3)加减乘除算术操作符,比较运算符,逻辑与,或运算符
1. 基本算术运算符 算术运算符主要用于对数值类型(整型和浮点型)进行基本的数学运算。以下是常见的算术运算符及其说明: 运算符描述示例结果加法运算符,用于两个数相加,也可用于字符串连接int a 5 3; string str &…...
如何优化 Webpack 的构建速度?
优化 Webpack 的构建速度是现代前端开发中至关重要的任务。随着项目规模的扩大,构建时间可能会显著增加,影响开发效率。以下是一些实用的方法和策略,以帮助你优化 Webpack 的构建速度。 一、使用生产模式和开发模式 1. 生产模式与开发模式 …...
win10把c盘docker虚拟硬盘映射迁移到别的磁盘
c盘空间本身就比较小、如果安装了docker服务后,安装的时候没选择其他硬盘,虚拟磁盘也在c盘会占用很大的空间,像我的就三十多个G,把它迁移到其他磁盘一下子节约几十G 1、先输入下面命令查看 docker 状态 wsl -l -v 2、如果没有停止…...
conda 配置源
无论是Anaconda vs Miniconda vs Miniforge 中的哪个,只要使用conda就涉及源,换源的目的是为了加速包的获取 修改配置文件 通过修改用户目录下的 .condarc 文件来使用 不同系统下的 .condarc 目录如下: Linux: ${HOME}/.condarcmacOS: ${…...
使用nvm管理node.js版本,方便vue2,vue3开发
在Vue项目开发过程中,我们常常会遇到同时维护Vue2和Vue3项目的情况。由于不同版本的Vue对Node.js 版本的要求有所差异,这就使得Node.js 版本管理成为了一个关键问题。NVM(Node Version Manager)作为一款强大的Node.js 版本管理工具…...
Linux离线环境安装miniconda并导入依赖包
一、实现目标 在Linux离线环境中安装miniconda后,将联网环境中的依赖包导入到离线miniconda中,使得python项目在Linux离线环境中正常运行 二、前置条件 设备需要拷贝的文件联网Linux虚拟机miniconda安装包、依赖包、项目文件离线Linux虚拟机/ 三、实…...
【opencv】图像基本操作
一.计算机眼中的图像 1.1 图像读取 cv2.IMREAD_COLOR:彩色图像 cv2.IMREAD_GRAYSCCALE:灰色图像 ①导包 import cv2 # opencv读取的格式是BGR import matplotlib.pyplot as plt import numpy as np %matplotlib inline ②读取图像 img cv2.imread(…...
泛微OA编写后端Rest接口
泛微OA编写后端Rest接口 前言 具体实现 运行结果 注意要点 总结 前言 在泛微E9中,可以通过注解的方式来编写对外的接口,之前的版本都是通过编写servlet类,然后在web.xml文件中将这个类和访问路径进行编辑之后才好在浏览器中通过输入对应…...
AI助力下的PPT革命:DeepSeek 与Kimi的高效创作实践
清华大学出品《DeepSeek:从入门到精通》分享 在忙碌的职场中,制作一份高质量的PPT往往需要投入大量时间和精力,尤其是在临近截止日期时。今天,我们将探索如何借助 AI 工具 —— DeepSeek 和 Kimi —— 让 PPT 制作变得既快捷又高…...
002 SpringCloudAlibaba整合 - Feign远程调用、Loadbalancer负载均衡
前文地址: 001 SpringCloudAlibaba整合 - Nacos注册配置中心、Sentinel流控、Zipkin链路追踪、Admin监控 文章目录 8.Feign远程调用、loadbalancer负载均衡整合1.OpenFeign整合1.引入依赖2.启动类添加EnableFeignClients注解3.yml配置4.日志配置5.远程调用测试6.服务…...
计算机视觉之图像处理-----SIFT、SURF、FAST、ORB 特征提取算法深度解析
SIFT、SURF、FAST、ORB 特征提取算法深度解析 前言 在图像处理领域亦或是计算机视觉中,首先我们需要先理解几个名词: 什么是尺度不变? 在实际场景中,同一物体可能出现在不同距离(如远处的山和近处的树)…...
DeepSeek接入Siri(已升级支持苹果手表)完整版硅基流动DeepSeek-R1部署
DeepSeek接入Siri(已升级支持苹果手表)完整版硅基流动DeepSeek-R1部署 **DeepSeek** 是一款专注于深度学习和人工智能的工具或平台,通常与人工智能、机器学习、自动化分析等领域有关。它的主要功能可能包括:深度学习模型搜索&…...
elabradio入门第八讲——帧同步技术
一、帧同步的相关知识 数字通信中, 为了使接收到的码元能够被理解,需要知道其如何分组。一般说来,接收端需要利用帧同步码去划分接收码元序列。将标志码组开始位置的帧同步码插入于一个码组的前面,如图所示。 这里的帧同步码是一…...
站长工具SEO综合查询是什么?怎么利用站长工具SEO综合查询
你的网站是否像一辆没有仪表盘的车?明明在狂奔却不知道油耗、时速、故障灯状态?2025年SimilarWeb数据显示,83%的站长因缺乏数据化诊断工具,导致50%以上的流量白白流失。今天我们用“修车师傅”的视角,拆解SEO综合查询工…...
超简单理解KMP算法(最长公共前后缀next数组、合并主子串、子串偏移法)
KMP算法理解 最长公共前后缀next合并主子串子串偏移 参考b站:子串偏移、合并主子串 最长公共前后缀next 这个概念是一个trick,帮助我们记录遍历了一遍的数组的相似特性,想出来确实很nb,我也不理解逻辑是怎么想出来的。 字符串的…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
从零开始了解数据采集(二十八)——制造业数字孪生
近年来,我国的工业领域正经历一场前所未有的数字化变革,从“双碳目标”到工业互联网平台的推广,国家政策和市场需求共同推动了制造业的升级。在这场变革中,数字孪生技术成为备受关注的关键工具,它不仅让企业“看见”设…...





















