stack,queue
stack,queue
- stack的介绍和使用
- 介绍
- 使用
- 模拟实现
- queue的介绍和使用
- 介绍
- 使用
- 模拟实现
- priority_queue的介绍和使用
- 介绍
- 使用
- 模拟实现
- 容器适配器
- 概念
- 标准库中stack,queue的底层结构
- 介绍deque
- 原理
- 缺陷
- deque作为stack,queue底层默认容器
stack的介绍和使用
介绍
- stack是适配器的一种,专门用在具有先进后出的容器中,而且元素的删除,插入和提取都只能从容器的一端进行
- stack作为容器适配器被实现,容器适配器系对特定类进行封装作为其底层的容器,并提供一组特定的成员函数访问其元素,将特定类作为其底层的,元素特定容器的尾部被压入和弹出,不可遍历
- stack的底层容器可以是任何标准的容器类模板

使用
| 函数说明 | 接口说明 |
|---|---|
| stack() | 构造空栈 |
| empty() | 检测stack是否为空 |
| size() | 返回stack中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素val压入stack中 |
| pop() | 将stack中尾部的元素弹出 |
模拟实现

模板中的第二个参数Class Container = deque<T>,Container是容器适配器,也就是用已存在的容器进行封装转换出自己想要实现的数据结构的底层容器,而且底层容器的功能可以直接使用,不再需要自己去实现底层容器及其相关功能,使用现成的,很大程度上提高效率。在这里,也就是用deque<T>作为底层容器,去实现stack类的数据结构
template<class T,class Container=deque<T>>class stack{public://数据入栈void push(const T& x){_con.push_back(x);}//数据出栈void pop(){_con.pop_back();}//提取栈顶数据const T& top(){return _con.back();}//检测栈是否为空bool empty(){return _con.empty();}//计算栈中有效元素的个数size_t size(){return _con.size();}private://deque作为底层容器创建变量Container _con;};
queue的介绍和使用
介绍
- 队列也是适配器的一种,专门用在先进先出的容器中,从容器一端插入元素,另一端提取元素
- 队列作为容器适配器实现,容器适配器系将特定容器进行封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队列头出队列。不可遍历
- 底层容器可以是标准容器模板之一

使用
| 函数说明 | 接口说明 |
|---|---|
| queue() | 构造空队列 |
| empty() | 检测队列是否为空 |
| size() | 返回队列中有效元素的个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素val入队列 |
| pop() | 将队头元素出队列 |
模拟实现

将 deque<T>作为底层容器,通过其去实现 queue类的数据结构
template<class T,class Container=deque<T>>class queue{public://数据入队列void push(const T& x){_con.push_back(x);}//数据出队列void pop(){_con.pop_front();}//提取队头数据const T& top(){return _con.front();}//检测队列是否为空bool empty(){return _con.empty();}//计算队列中有效元素的个数size_t size(){return _con.size();}private://deque作为底层容器创建变量Container _con;};
priority_queue的介绍和使用
介绍
- 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的
- 优先队列的容器类似堆,在堆中可以随时插入元素,并且只能提取最大的元素,不可遍历
- 优先队列被实现为容器适配器,queue提供一组特定的成员函数来访问其元素。元素从容器的尾部弹出,其称为优先队列的顶部
使用
优先队列默认使用vector作为其底层存储数据的容器,在vector上使用堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue,默认情况下,priority_queue是大根堆
| 函数说明 | 接口说明 |
|---|---|
| priority_queue() | 构造空优先队列 |
| empty() | 检测优先队列是否为空 |
| top() | 返回优先队列中最大元素,即堆顶元素 |
| push(x) | 在优先队列中插入元素x |
| pop() | 删除优先队列中最大元素,即堆顶元素 |
模拟实现

根据上面的介绍,优先队列的本质上就是堆,所以选择vector<T>作为其底层容器;默认情况下,优先队列是大根堆,模板中的比较函数是less,所以如果需要将其改为小根堆的话,只需要将比较函数修改为greater即可
这里的比较函数Compare也称作仿函数
仿函数又称为函数对象是一个能行使函数功能的类,通过创建对象来实行函数功能
作为仿函数的类,都必须重载 operator() 运算符。调用仿函数,本质上就是通过类对象调用重载后的 operator() 运算符。
仿函数的实现
template<class T>//判断前一个数小于后一个数class less{public:bool operator()(const T& x, const T& y) const {return x < y;}};template<class T>//判断前一个数大于后一个数class greater{public:bool operator()(const T& x, const T& y) const{return x > y;}};
优先队列的实现
template<class T,class Container = vector<T>,class Compare = less<T>>class priority_queue{public://无参构造函数priority_queue(){}//迭代器构造函数template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i){adjust_down(i);}}//向上调整void adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}//数据入堆void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}//向下调整void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}//删除堆顶数据void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}//提取堆顶数据const T& top(){return _con[0];}//检测堆是否为空bool empty(){return _con.empty();}//计算堆中有效元素的个数size_t size(){return _con.size();}private://vector作为底层容器Container _con;};
容器适配器
概念
适配器是一种设计模式,该模式是将一个类的接口转换成客户希望的另外一个接口
标准库中stack,queue的底层结构
stack,queue本身也可以存放元素,但在STL中只是将其称为容器适配器,因为stack和queue只是对其他容器的接口进行了包装,STL中默认使用deque作为容器
介绍deque
原理
deque:一种双开口的“连续”空间的数据结构,可以在头尾两端进行插入和删除操作,并且时间复杂度为O(1),与vector相比,头插效率高,不需要搬移元素;与list相比,空间利用率比较高

deque并不是真正连续的空间,而是由一段连续的小空间拼接而成的,实际上deque类似于一个动态二维数组,其底层结构如下

缺陷
不适合遍历,在遍历时,deque的迭代器要频繁地去检测其是否移动到某段小空间的边界,导致效率低。在实际中,需要线性结构时,大多情况下优先考虑vector和list,deque的应用是,STL用其作为stack和queue的底层数据结构
deque作为stack,queue底层默认容器
stack是先进后出的特殊线性数据结构,因此是要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器;queue是先进先出的线性数据结构只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层结构,STL选择deque作为其底层容器的原因如下
- stack和queue不需要遍历,只需要再固定的一端或者两端进行操作
- 在stack中元素增长时,deque比vector的效率高;queue中元素增长时,deque不仅效率高,而且内存使用率高
总的来说就是,结合了deque的有点,并且完美地避开其缺点
相关文章:
stack,queue
stack,queuestack的介绍和使用介绍使用模拟实现queue的介绍和使用介绍使用模拟实现priority_queue的介绍和使用介绍使用模拟实现容器适配器概念标准库中stack,queue的底层结构介绍deque原理缺陷deque作为stack,queue底层默认容器stack的介绍和使用 介绍 stack是适…...
shiro反序列化
shiro550反序列化 | 清风的博客这个看着更舒服点 环境搭建 JDK:1.7 Tomcat:8.5.83 shiro源码:下载地址:https://codeload.github.com/apache/shiro/zip/shiro-root-1.2.4 shiro war包:下载地址SHIRO-550/samples-…...
【GoF 23 概念理解】IoC/DI(控制反转/依赖注入)
搞清楚以下几个问题你就明白什么是 IoC/DI 了: 参与者都有谁?依赖:谁依赖于谁?为什么要依赖?注入:谁注入于谁?到底注入什么?控制反转:谁控制谁?控制什么&…...
stm32外设-GPIO
0. 写在最前 本栏目笔记都是基于stm32F10x 1. GPIO基本介绍 GPIO—general purpose intput output 是通用输入输出端口的简称,简单来说就是软件可控制的引脚, STM32芯片的GPIO引脚与外部设备连接起来,从而实现与外部通讯、控制以及数据采集的…...
AfxMessageBox 自定义封装
一般情况下AfxMessageBox是系统提供的一个对话框,若要做这种效果的,必须重写。 实例1: void test_SgxMemDialog_AutoSize() { //使用给定大小的对话框 CSgxMemDialog dlg(180, 60); dlg.SetWindowTitle(_T(" SegeX - CT&qu…...
登入vCenter显示503,证书过期解决办法
登入vCenter显示503 原因:当安全令牌服务 (STS) 证书已过期时,会出现这些问题。这会导致内部服务和解决方案用户无法获取有效令牌,从而导致无法按预期运行(证书两年后就会过期)。 解决办法&…...
设计模式(十九)----行为型模式之命令模式
1、概述 日常生活中,我们出去吃饭都会遇到下面的场景。 定义: 将一个请求封装为一个对象,使发出请求的责任和执行请求的责任分割开。这样两者之间通过命令对象进行沟通,这样方便将命令对象进行存储、传递、调用、增加与管理。命…...
【数据库】数据库基础架构
数据库架构 数据库对于后端程序员来说是每天都需要打交道的系统,因此了解并掌握MySQL底层原理是必须的。 基础架构图 MySQL内部分为两层,一个是Server层,另一个是存储引擎层,而我们常用的就是MyISAM、InnoDB,主要负…...
English Learning - L2 语音作业打卡 双元音 [ɔɪ] [ɪə] Day16 2023.3.8 周三
English Learning - L2 语音作业打卡 双元音 [ɔɪ] [ɪə] Day16 2023.3.8 周三💌发音小贴士:💌当日目标音发音规则/技巧:🍭 Part 1【热身练习】🍭 Part2【练习内容】🍭【练习感受】🍓元音 [ɔ…...
C++语法规则4(C++面向对象)
接口(抽象类) 接口描述了类的行为和功能,而不需要完成类的特定实现。C 接口是使用抽象类来实现的,抽象类与数据抽象互不混淆,数据抽象是一个把实现细节与相关的数据分离开的概念。 如果类中至少有一个函数被声明为纯虚…...
【Spring 深入学习】AOP的前世今生之后续
AOP的前世今生之后续 1. 概述 上篇文章【Spring 深入学习】AOP的前世今生之代理模式我们讲述了代理模式。而我们今天的主人公AOP就是基于代理模式实现的,所以我们今天会简单学习下AOP 2. 什么是AOP 是面向切面编程,一般可以帮助我们在不修改现有代码的情…...
软考高项——配置管理
配置管理配置管理配置管理6个主要活动配置项配置基线配置项的状态配置库配置库权限管理配置审计配置管理 配置管理的总线索包括: 1)配置管理6个主要活动 2)配置项 3)配置基线 4)配置项的状态 5)配置库 6&a…...
网站SEO优化,网站TDK三大标签SEO优化,LOGO SEO优化
SEO(Search Engine Optimization)汉译为搜索引擎优化,是一种利用搜索引擎的规则提高网站在有关搜索 引擎内自然排名的方式。 SEO 的目的是对网站进行深度的优化,从而帮助网站获取免费的流量,进而在搜索引擎上提升网站的…...
select查询语句
worker表的字段有id, d_id, name, sex, birthday, salary, address 编号,部门号,姓名,性别,出生日期,工资,家庭住址 department表的字段有d_id, d_name, function, address 部门号,部门名,部门职能,部门位置 (1)查询worker表的所有记录(用*表示)。 select * fro…...
没有对象感,沟通太费劲
沟通中最重要的感觉:对象感! 要沟通的是谁?以啥方式最好? 趣讲大白话:蹲着跟小孩说话 【趣讲信息科技100期】 ******************************* 对象感是沟通者必须训练和提升的 是换位思考的一种能力 以便跟沟通对象进…...
智能优化算法之遗传算法
该算法已被很多篇文章讲解,本文将会去除很多较简单的内容,挑选认为重点核心部分进行讲述,内容中有属于信息的收集整理部分,也有属于自己理解的部分。 1、遗传算法概述 遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方…...
【rabbitmq 实现延迟消息-插件版本安装(docker环境)】
一:插件简介 在rabbitmq 3.5.7及以上的版本提供了一个插件(rabbitmq-delayed-message-exchange)来实现延迟队列功能。同时插件依赖Erlang/OPT 18.0及以上。 二:插件安装 1:选择适合自己安装mq 版本的插件࿱…...
【大数据】HDFS管理员 HaAdmin 集群高可用命令详细使用说明
高可用HaAdmin使用概览使用说明checkHealth查看NameNode的状态所有NN的服务状态查询指定NN的服务状态failovertransitionToActive概览 HDFS高可用特性解决了集群单点故障问题,通过提供了两个冗余的NameNode以主动或被动的方式用于热备,使得集群既可以从…...
京区航天研究所 哪些比较好的研究所?
第一梯队:一院一部、战术武器部、10所、12所、研发部、空天部,五院501所(总体设计部)、502所、通导部、遥感部、钱室(所人均年薪35w-50w级别) 第二梯队:一院14所、15所,二院未来实验…...
Nacos配置拉取及配置动态刷新原理【源码阅读】
Nacos配置拉取及配置刷新原理 一、初始化时获取配置文件 背景 SpringCloud项目中SpringBoot在启动阶段除了会创建SpringBoot容器,还会通过bootstrap.yml构建一个SpringCloud容器,之后会在准备上下文阶段通过SPI加载实现类后,会进行配置合并…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
