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

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 作用&#xff1a;判断栈中是否为空 我们看到这里s1初始化的时候是空初始化&#xff0c;所以用empty来判断出的就是空的栈 1.2size size的作用就是判断栈中的数据个数 1.3push 与vector,string,list不同的是,stack中没有头插尾插的概念 因为栈有一个原则&…...

Linux-C/C++《C++/1、C++基础》(C++语言特性、面向对象等)

这里主要介绍概念为主&#xff0c;主要介绍 C与 C 语言中常用的不同点&#xff0c;和一些新的变化。其中不会去说指针、数据类型、变量类型、判断和循环等这些知识&#xff0c;这些和C 语言基本是一样使用的。我们主要学习 C的面向对象编程&#xff0c;对学习 Qt 有很大的帮助。…...

交易所开发:数字市场的核心动力

数字资产交易所作为连接用户与市场的核心枢纽&#xff0c;已成为推动数字经济发展的关键引擎。其开发不仅需要技术创新&#xff0c;还需兼顾用户体验、合规安全与生态构建&#xff0c;以下是交易所开发的核心要素与实践路径分析&#xff1a; 一、交易所的核心定位与技术架构…...

Spring Boot 应用(官网文档解读)

Spring Boot 启动方式 SpringApplication.run(MyApplication.class, args); Spring Boot 故障分析器 在Spring Boot 项目启动发生错误的时候&#xff0c;我们通常可以看到上面的内容&#xff0c;即 APPLICATION FAILED TO START&#xff0c;以及后面的错误描述。这个功能是通过…...

.Net面试宝典【刷题系列】

文章目录 1、JIT是如何工作的2、值类型和引用类型的区别3、解释泛型的基本原理4、如何自定义序列化和反序列化的过程5、如何使用 IFormattable 接口实现格式化输出6、请解释委托的基本原理7、什么是链式委托8、请解释反射的基本原理和其实现的基石9、如何利用反射来实现工厂模式…...

Unity游戏制作中的C#基础(3)加减乘除算术操作符,比较运算符,逻辑与,或运算符

1. 基本算术运算符 算术运算符主要用于对数值类型&#xff08;整型和浮点型&#xff09;进行基本的数学运算。以下是常见的算术运算符及其说明&#xff1a; 运算符描述示例结果加法运算符&#xff0c;用于两个数相加&#xff0c;也可用于字符串连接int a 5 3; string str &…...

如何优化 Webpack 的构建速度?

优化 Webpack 的构建速度是现代前端开发中至关重要的任务。随着项目规模的扩大&#xff0c;构建时间可能会显著增加&#xff0c;影响开发效率。以下是一些实用的方法和策略&#xff0c;以帮助你优化 Webpack 的构建速度。 一、使用生产模式和开发模式 1. 生产模式与开发模式 …...

win10把c盘docker虚拟硬盘映射迁移到别的磁盘

c盘空间本身就比较小、如果安装了docker服务后&#xff0c;安装的时候没选择其他硬盘&#xff0c;虚拟磁盘也在c盘会占用很大的空间&#xff0c;像我的就三十多个G&#xff0c;把它迁移到其他磁盘一下子节约几十G 1、先输入下面命令查看 docker 状态 wsl -l -v 2、如果没有停止…...

conda 配置源

无论是Anaconda vs Miniconda vs Miniforge 中的哪个&#xff0c;只要使用conda就涉及源&#xff0c;换源的目的是为了加速包的获取 修改配置文件 通过修改用户目录下的 .condarc 文件来使用 不同系统下的 .condarc 目录如下&#xff1a; Linux: ${HOME}/.condarcmacOS: ${…...

使用nvm管理node.js版本,方便vue2,vue3开发

在Vue项目开发过程中&#xff0c;我们常常会遇到同时维护Vue2和Vue3项目的情况。由于不同版本的Vue对Node.js 版本的要求有所差异&#xff0c;这就使得Node.js 版本管理成为了一个关键问题。NVM&#xff08;Node Version Manager&#xff09;作为一款强大的Node.js 版本管理工具…...

Linux离线环境安装miniconda并导入依赖包

一、实现目标 在Linux离线环境中安装miniconda后&#xff0c;将联网环境中的依赖包导入到离线miniconda中&#xff0c;使得python项目在Linux离线环境中正常运行 二、前置条件 设备需要拷贝的文件联网Linux虚拟机miniconda安装包、依赖包、项目文件离线Linux虚拟机/ 三、实…...

【opencv】图像基本操作

一.计算机眼中的图像 1.1 图像读取 cv2.IMREAD_COLOR&#xff1a;彩色图像 cv2.IMREAD_GRAYSCCALE&#xff1a;灰色图像 ①导包 import cv2 # opencv读取的格式是BGR import matplotlib.pyplot as plt import numpy as np %matplotlib inline ②读取图像 img cv2.imread(…...

泛微OA编写后端Rest接口

泛微OA编写后端Rest接口 前言 具体实现 运行结果 注意要点 总结 前言 在泛微E9中&#xff0c;可以通过注解的方式来编写对外的接口&#xff0c;之前的版本都是通过编写servlet类&#xff0c;然后在web.xml文件中将这个类和访问路径进行编辑之后才好在浏览器中通过输入对应…...

AI助力下的PPT革命:DeepSeek 与Kimi的高效创作实践

清华大学出品《DeepSeek&#xff1a;从入门到精通》分享 在忙碌的职场中&#xff0c;制作一份高质量的PPT往往需要投入大量时间和精力&#xff0c;尤其是在临近截止日期时。今天&#xff0c;我们将探索如何借助 AI 工具 —— DeepSeek 和 Kimi —— 让 PPT 制作变得既快捷又高…...

002 SpringCloudAlibaba整合 - Feign远程调用、Loadbalancer负载均衡

前文地址&#xff1a; 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 特征提取算法深度解析 前言 在图像处理领域亦或是计算机视觉中&#xff0c;首先我们需要先理解几个名词&#xff1a; 什么是尺度不变&#xff1f; 在实际场景中&#xff0c;同一物体可能出现在不同距离&#xff08;如远处的山和近处的树&#xff09;…...

DeepSeek接入Siri(已升级支持苹果手表)完整版硅基流动DeepSeek-R1部署

DeepSeek接入Siri&#xff08;已升级支持苹果手表&#xff09;完整版硅基流动DeepSeek-R1部署 **DeepSeek** 是一款专注于深度学习和人工智能的工具或平台&#xff0c;通常与人工智能、机器学习、自动化分析等领域有关。它的主要功能可能包括&#xff1a;深度学习模型搜索&…...

elabradio入门第八讲——帧同步技术

一、帧同步的相关知识 数字通信中&#xff0c; 为了使接收到的码元能够被理解&#xff0c;需要知道其如何分组。一般说来&#xff0c;接收端需要利用帧同步码去划分接收码元序列。将标志码组开始位置的帧同步码插入于一个码组的前面&#xff0c;如图所示。 这里的帧同步码是一…...

站长工具SEO综合查询是什么?怎么利用站长工具SEO综合查询

你的网站是否像一辆没有仪表盘的车&#xff1f;明明在狂奔却不知道油耗、时速、故障灯状态&#xff1f;2025年SimilarWeb数据显示&#xff0c;83%的站长因缺乏数据化诊断工具&#xff0c;导致50%以上的流量白白流失。今天我们用“修车师傅”的视角&#xff0c;拆解SEO综合查询工…...

超简单理解KMP算法(最长公共前后缀next数组、合并主子串、子串偏移法)

KMP算法理解 最长公共前后缀next合并主子串子串偏移 参考b站&#xff1a;子串偏移、合并主子串 最长公共前后缀next 这个概念是一个trick&#xff0c;帮助我们记录遍历了一遍的数组的相似特性&#xff0c;想出来确实很nb&#xff0c;我也不理解逻辑是怎么想出来的。 字符串的…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

初探Service服务发现机制

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

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...