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

C++的stack和queue+优先队列

文章目录

  • 什么是容器适配器
  • 底层逻辑
  • 为什么选择deque作为stack和queue的底层默认容器
  • 优先队列
  • 优先队列的模拟实现
  • stack和queue的模拟实现

什么是容器适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总
结),该种模式是将一个类的接口转换成客户希望的另外一个接口。

底层逻辑

stack和queue都是容器适配器,底层都是通过去适配双端队列deque去实现的,STL中没有把stack和queue划分在容器中,而是放在容器适配器,stack和queue默认使用deque.
在这里插入图片描述
在这里插入图片描述
那可不可以用vector去适配呢?
这也是可以的,只要是他们的所有接口,在这个容器中包含就可以进行适配,那么为什么底层默认会选择使用deque去进行适配呢?
deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。
deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组。
与vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是必vector高的。
与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。但是,deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到
某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构

为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以;queue是先进先出的特殊线性数据结构,只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如list。但是STL中对stack和queue默认选择deque作为其底层容器,主要是因为:

  1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。
  2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高。结合了deque的优点,而完美的避开了其缺陷。

优先队列

优先队列本质上就是topk问题,那么优先队列是怎么实现的呢?
优先队列的底层物理结构是数组,其中模板参数Compare是控制优先队列是大堆还是小堆,
优先队列默认是大堆–缺省参数就是less,如果要给大堆就是greater
这两个模板参数的底层实现:

//仿函数/函数对象
//重载了括号,让类可以向函数一样被调用
template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};

优先队列的模拟实现

//优先队列,其实就是topk问题,底层结构就是堆,所以我们用数组---vector来存取数据template<class T, class Container = vector<T>, class Compare = less<T>>//默认是大堆,less对应的就是大堆//greater<T>对应的是小堆 通过传Compare来控制大堆还是小堆,默认不传是大堆//仿函数控制实现大小堆class priority_queue{private:void AdjustDown(size_t parent){Compare com;size_t chidren = parent * 2 + 1;while (chidren < _con.size()){if (chidren + 1 < _con.size() && com( _con[chidren], _con[chidren + 1])){chidren += 1;}//if (_con[parent] < _con[chidren])if (com(_con[parent], _con[chidren])){swap(_con[parent], _con[chidren]);parent = chidren;chidren = parent * 2 + 1;}else{break;}}}void AdjustUp(int chidren){Compare com;int parent = (chidren - 1) / 2;while (parent >= 0){if (com(_con[parent], _con[chidren])){swap(_con[chidren], _con[parent]);chidren = parent;parent = (chidren - 1) / 2;}else{break;}}}public:priority_queue(){}template<class InputInterator>priority_queue(InputInterator first, InputInterator last){//插入数据while (first != last){_con.push_back(*first);++first;}//建堆//从最后一个非叶子节点开始建堆-----关键for (int i = (_con.size()-1-1) / 2; i >= 0; i--){AdjustDown(i);}}void pop()//删除的是第一个元素{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}void push(const T& x){//_con[_con.size()] = x;_con.push_back(x);AdjustUp(_con.size() - 1);}T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};

stack和queue的模拟实现

#pragma once//适配器模拟实现
namespace sw
{	//数组栈与链式栈之间秒切换---------适配器template<class T, class Container = deque<T>>//模板参数不仅可以是int,double等内置类型也可以是容器,同时也可以给缺省值class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();//取最后一个元素,}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_stack(){cout << "stack" << endl;stack<int, vector<int>> st1;st1.push(1);st1.push(2);st1.push(3);st1.push(4);while (!st1.empty()){cout << st1.top() << " ";st1.pop();}cout << endl;stack<int, list<int>> st2;st2.push(1);st2.push(2);st2.push(3);st2.push(4);while (!st2.empty()){cout << st2.top() << " ";st2.pop();}cout << endl;stack<int> st3;st3.push(1);st3.push(2);st3.push(3);st3.push(4);while (!st3.empty()){cout << st3.top() << " ";st3.pop();}cout << endl;}
}
#pragma oncenamespace sw
{//适配器template<class T, class Container = deque<T>>//模板参数不仅可以是int,double等内置类型也可以是容器,同时也可以给缺省值class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}T& front(){return _con.front();}T& back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_queue(){cout << "queue" << endl;queue<int, deque<int>> q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);while (!q1.empty()){cout << q1.front() << " ";q1.pop();}cout << endl;queue<int, list<int>> q2;q2.push(1);q2.push(2);q2.push(3);q2.push(4);while (!q2.empty()){cout << q2.front() << " ";q2.pop();}cout << endl;}
}

相关文章:

C++的stack和queue+优先队列

文章目录 什么是容器适配器底层逻辑为什么选择deque作为stack和queue的底层默认容器优先队列优先队列的模拟实现stack和queue的模拟实现 什么是容器适配器 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结)&#xff0c;…...

Ubuntu 18.04.6 Android Studio Giraffe adb logcat 无法使用

在 Ubuntu 18.04.6 上 在链接上设备以后&#xff0c;发现可以用 Android Studio 安装应用 但无法用 Android Studio 看 logcat 手动从命令行停止&#xff0c;启动 adb 会报错如下: daemon not running. starting it now on port 5037 ADB server didnt ACK fail…...

Python采集天气数据,做可视化分析【附源码】

嗨害大家好鸭&#xff01;我是小熊猫~ 毕业设计大家着急吗&#xff1f; 没事&#xff0c;我来替大家着急 源码、素材python永久安装包:点击此处跳转文末名片获取 本文知识点: 动态数据抓包 requests发送请求 结构化非结构化数据解析 开发环境: python 3.8 运行代码 pycharm 2…...

优维低代码实践:自定义模板

优维低代码技术专栏&#xff0c;是一个全新的、技术为主的专栏&#xff0c;由优维技术委员会成员执笔&#xff0c;基于优维7年低代码技术研发及运维成果&#xff0c;主要介绍低代码相关的技术原理及架构逻辑&#xff0c;目的是给广大运维人提供一个技术交流与学习的平台。 优维…...

电商3D产品渲染简明教程

3D 渲染让动作电影看起来更酷&#xff0c;让建筑设计变得栩栩如生&#xff0c;现在还可以帮助营销人员推广他们的产品。 从最新的《阿凡达》电影到 Spotify 的上一次营销活动&#xff0c;3D 的应用让一切变得更加美好。 在营销领域&#xff0c;3D 产品渲染可帮助品牌创建产品的…...

探索未来:元宇宙与Web3的无限可能

随着科技的奇迹般发展&#xff0c;互联网已经成为了我们生活的不可分割的一部分。然而&#xff0c;尽管它的便利性和普及性带来了巨大的影响&#xff0c;但我们仍然面临着传统互联网体验的诸多限制。 购物需要不断在实体店与电商平台间切换&#xff0c;教育依然受制于时间与地…...

GraphQL(六)登录态校验Directive

GraphQL Directive&#xff08;指令&#xff09;是GraphQL中的一种特殊类型&#xff0c;它允许开发者在GraphQL schema中添加元数据&#xff0c;以控制查询和解析操作的行为 Directive的详细说明及使用可见GraphQL&#xff08;五&#xff09;指令[Directive]详解 本文将介绍通过…...

强大的AI语言模型

1.kameAI 点我 1️⃣可以绘图 2️⃣对接4.0 3️⃣具有长篇写作...

成集云 | 鼎捷ERP采购单同步钉钉 | 解决方案

源系统成集云目标系统 方案介绍 鼎捷ERP&#xff08;Enterprise Resource Planning&#xff09;是一款综合性的企业管理软件&#xff0c;它包括了多个模块来管理企业的各个方面&#xff0c;其中之一就是采购订单模块。鼎捷ERP的采购订单模块可以帮助企业有效管理和控制采购过程…...

【Kubernetes】Kubernetes的PV和PVC的用法

PV、PVC 前言一、 存储卷1. emptyDir 存储卷1.1 概念1.2 实例 2. hostPath 存储卷2.1 概念2.2 实例 3. nfs共享存储卷 二、PV 和 PVC1. 概念1.1 PV1.2 PVC1.3 PVC 的使用逻辑1.4 创建机制1.5 PV 和 PVC 的生命力周期1.6 创建及销毁 PV 的流程 2. PV 和 PVC 的创建2.1 查看定义2…...

【Redis】Redis三种集群模式-主从、哨兵、集群各自架构的优点和缺点对比

文章目录 前言1. 单机模式2. 主从架构3. 哨兵4. 集群模式总结 前言 如果Redis的读写请求量很大&#xff0c;那么单个实例很有可能承担不了这么大的请求量&#xff0c;如何提高Redis的性能呢&#xff1f;你也许已经想到了&#xff0c;可以部署多个副本节点&#xff0c;业务采用…...

Python爬虫:如何使用Python爬取网站数据

更新&#xff1a;2023-08-13 15:30 想要获取网站的数据&#xff1f;使用Python爬虫是一个绝佳的选择。Python爬虫是通过自动化程序来提取互联网上的信息。本文章将会详细介绍Python爬虫的相关技术。 一、网络协议和请求 在使用Python爬虫之前&#xff0c;我们需要理解网络协…...

剑指offer专题2:队列和栈

用两个栈模拟队列 class CQueue {stack<int> stack1;stack<int> stack2; public:CQueue() {}void appendTail(int value) {stack1.push(value);}int deleteHead() {int val-1;if(!stack2.empty()){val stack2.top();stack2.pop();}else if(!stack1.empty()){while…...

pytorch入门-神经网络

神经网络的基本骨架 import torch from torch import nn #nn模块是PyTorch中用于构建神经网络模型的核心模块。它提供了各种类和函数&#xff0c;可以帮助你定义和训练神经网络。class Tudui(nn.Module):def __init__(self):super(Tudui, self).__init__() #调用 super(Tudui,…...

kafka使用心得(二)

kafka进阶 消息顺序保证 Kafka它在设计的时候就是要保证分区下消息的顺序&#xff0c;也就是说消息在一个分区中的顺序是怎样的&#xff0c;那么消费者在消费的时候看到的就是什么样的顺序。 消费者和分区的对应关系 参考这篇文章。 分区文件 一个分区对应着log.dirs下的…...

(二)掌握最基本的Linux服务器用法——Linux下简单的C/C++ 程序、项目编译

1、静态库与动态库 静态库(Static Library)&#xff1a;静态库是编译后的库文件&#xff0c;其中的代码在编译时被链接到程序中&#xff0c;因此它会与程序一起形成一个独立的可执行文件。每个使用静态库的程序都会有自己的库的副本&#xff0c;这可能会导致内存浪费。常用后缀…...

应急响应-钓鱼邮件的处理思路溯源及其反制

0x00 钓鱼邮件的危害 1.窃取用户敏感信息&#xff0c;制作虚假网址&#xff0c;诱导用户输入敏感的账户信息后记录 2.携带病毒木马程序&#xff0c;诱导安装&#xff0c;使电脑中病毒木马等 3.挖矿病毒的传输&#xff0c;勒索病毒的传输等等 0x01 有指纹的钓鱼邮件的溯源处理…...

Hadoop Hbase Hive 版本对照一览

这里写目录标题 一、Hadoop 与 Hbase 版本对照二、Hadoop 与 Hive 版本对照 官网内容记录&#xff0c;仅供参考 一、Hadoop 与 Hbase 版本对照 二、Hadoop 与 Hive 版本对照...

Postgresql 基础使用语法

1.数据类型 1.数字类型 类型 长度 说明 范围 与其他db比较 Smallint 2字节 小范围整数类型 32768到32767 integer 4字节 整数类型 2147483648到2147483647 bigint 8字节 大范围整数类型 -9233203685477808到9223203685477807 decimal 可变 用户指定 精度小…...

Qt 之 QDebug,QString

文章目录 前言一、QDebug二、QString总结 前言 一、QDebug QDebug是Qt中用于进行调试和输出日志的类。它提供了一种便捷的方式来输出各种类型的数据&#xff0c;并可轻松地与流式输出一起使用&#xff0c;方便调试和查看程序的运行情况。 引入QDebug&#xff1a; 在使用QDebug…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...