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

stack和queue模拟实现

前言

上一期我们介绍了stack和queue的使用,本期我们来模拟实现一下他们!

本期内容介绍

容器适配器 

deque介绍

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

stack 模拟现实

queue 模拟实现

什么是容器适配器?

适配器是一种设计模式,该种模式是将一个类的接口转换为用户希望的另一个接口!

什么是设计模式?

设计模式是一套被反复使用的,多数人知晓的,经过分类编目的,代码设计经验的总结。

总结:设计模式就是一种常用的编程套路,该套路被很多人知晓和使用,具有可靠性!

常见的设计模式有:单例设计模式、工厂设计模式等。

举个例子:

你平时手机没电了,你是拿充电器先到插板上去充,而不是直接去拿电线充。因为电线直接充是不符合我们的需求的(一下子弄不好你就被干没了)!我们要用插板提供的接口插充电器才可以充!其实本质你手机充的还是电线里面的电。只是把他转换了一下!充电器就像是一个适配器,将电源的接口转换成手机充电口的接口,使得手机可以与电源连接起来充电。同样地,容器适配器也起到了类似的作用,它将一个容器的接口转换成另一个容器的接口,使得原本不兼容的容器能够协同工作。

deque介绍

stack和queue中虽然也可以存放元素,但是STL并没有将他们划分到容器的行列里面!而是将其称为:容器适配器,这里是因为stack和queue只是对其他的容器进行了包装,STL中stack和queue底层默认deque, deque就是我们在上一期介绍stack和queue的时候,看到了他们的模板参数多了一个的那个容器类型的默认容器!

什么是deque?

deque到底是什么呢?上一期专门没有介绍,就等到这一期来介绍!

deque叫双端队列!是一种双开口的"连续"空间的数据结构。双开口的含义是:可以在头和尾两端进行插入和删除操作!而且时间复杂度为O(1),与vector相比头插效率高,不需要在头删时挪动大量的数据了,与list相比,空间利用率比较高!所以我们可以认为他是list和vector的结合版!可以支持元素的随机访问。支持头尾的插入删除,而且效率很高!

注意:duque并不是真的连续的空间!而是由一段段连续的小空间拼接而成,实际的deque类似于一个动态的二维数组!

这个中控数组实际上一个数组指针!里面存的就是每个小段的数组的地址!这个中控数组是可以扩容的!!

所以双端队列的底层是一段假象的连续空间,实际上是分段连续的,为了维护其“整体连续”以及随机访问的假象,重任就落在了deque的迭代器身上了!

deque的迭代器也很复杂:

deque是如何借助迭代器维护其假想的连续结构的呢?

它的底层搞了两个迭代器start和finish一个指向第一个buffer小段数组,另一个指向最后一个buffer小数组,遍历时,从第一个buffer开始,如果不到最后一个buffer的最后一个位置即finish的最后一个end就到下一个buffer继续遍历!直到遍历完!

deque是如何用下标+[]来访问的?

因为中控数组中的每个小buffer数组的长度都是一样大的!所以我们在访问第i个位置时,通过 i / N 获取他是在那个buff数组,再根据 i % N来确定他是在第几个!从而实现了下标遍历~!

deque的缺陷

与vector相比,deque的优势是:在头部插入和删除的时候,不需要移动元素,效率特别高,而在扩容时也不需要移动大量的元素,因此这里是效率比vector高的!

与list相比,它的底层的空间是连续的,空间利用率高,不需要额外的存储字段!

但是,deque也有很致命的缺陷:

不适合遍历,一位在遍历时,deque的迭代器要频繁的去检测其是否移动到了都一小段的边界,导致效率下降!所以在实际中,需要线性结构中一般优选的是vector和list!

不适合在中间插入删除、因为你在某个中间的buffer插入时,如果满了得扩容,删除时怎么删??你不可能说--size吧,人家下标可不管这些,解决的办法就是删除时缩容,但是缩容后就有新问题,如何知道第i个位置的元素?导致效率降低!

以及它的[]的效率很一般!下面有代码验证:

void test_op1()
{srand(time(0));const int N = 1000000;deque<int> dq;vector<int> v;for (int i = 0; i < N; ++i){auto e = rand() + i;v.push_back(e);dq.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();sort(dq.begin(), dq.end());int end2 = clock();printf("vector:%d\n", end1 - begin1);printf("deque:%d\n", end2 - begin2);
}

我们知道sort的底层会大量的用到[],结果差了三倍多!!!

第二个:

void test_op2()
{srand(time(0));const int N = 1000000;deque<int> dq1;deque<int> dq2;for (int i = 0; i < N; ++i){auto e = rand() + i;dq1.push_back(e);dq2.push_back(e);}int begin1 = clock();sort(dq1.begin(), dq1.end());int end1 = clock();int begin2 = clock();// vectorvector<int> v(dq2.begin(), dq2.end());sort(v.begin(), v.end());dq2.assign(v.begin(), v.end());int end2 = clock();printf("deque sort:%d\n", end1 - begin1);printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}

这个是把一个deque的数据拷贝到vector排完了再拷回来,都比deque快:

所以ton过这两个栗子足以证明deque的[]效率可见一般了~!

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

STL选择让他默认为栈和队列的原因有两个:

1、stack和queue不需要遍历,他们根本没有迭代器。只是需要在固定的一端或两端进行插入和删除操作!

2、在stack中元素增加时,与vector相比deque的扩容效率更高(deque扩容不需要移动大量的数据)。

综上两点,deque完美的解决stack和queue的问题,而且正好弥补了用vector和list的缺陷!所以STL就选择了他作为默认的容器!

OK,我们来看看它的接口:

直接包含了vector和list所有的好用接口!!!

stack的模拟实现

我们以前在数据结构的时候,实现栈使用的是单链表或顺序表!这里你也可以接着这样玩,直接用vector和list。但是我这里就不这样玩了,我直接来使用deque!

    template<class T, class Container = deque<T>>class stack{public:stack(){}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}T& top(){return _con.back();}const T& top() const {return _con.back();}void push(const T& val){_con.push_back(val);}void pop(){assert(!empty());_con.pop_back();}private:Container _con;};

这里都很简单不在逐一解释!

需要注意的是:你可以不用写这个stack的默认构造!因为stack这个类里面只有一个自定义类型的变量!所以你不写编译器默认生成的那个就自己去调用调他自己成员的默认构造了!

另外,这里选择的是尾部实现的,你也可以选择头部实现!

queue模拟实现

同样的队列这里你也可以和数据结构那样搞个链表玩!介绍了deque那必然用它~!

    template<class T, class Container = deque<T>>class queue{public:queue() {}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}T& front() {return _con.front();}const T& front() const {return _con.front();}T& back() {return _con.back();}const T& back() const{return _con.back();}void push(const T& val){_con.push_back(val);}void pop(){_con.pop_front();}private:Container _con;};

和上面同样你也可以不写默认构造!另外注意的是:插入是尾插,删除是头删

OK,我测试一下:

没有问题~!OK,本期分享就到这里!好兄弟,我们下期再见~!

结束语:心怀理想,勇往直前!

相关文章:

stack和queue模拟实现

前言 上一期我们介绍了stack和queue的使用&#xff0c;本期我们来模拟实现一下他们&#xff01; 本期内容介绍 容器适配器 deque介绍 为什么stack和queue的底层选择deque为默认容器&#xff1f; stack 模拟现实 queue 模拟实现 什么是容器适配器&#xff1f; 适配器是一种设…...

docker操作

1、容器生命周期管理命令 docker run docker run --name tomcat8 -d -p 28080:8080 tomcat:8.5.38 docker run -i --name hausf --network bridge --ip 172.17.0.10 ubuntu:20.04 /bin/bash docker run -d --name hausf --net host ubuntu:20.04 /bin/bash docker run…...

分布式锁介绍

引言 分布式锁是一种用于协调不同进程或线程对共享资源的访问控制的机制。在分布式系统中&#xff0c;由于多个节点可能同时访问或修改同一资源&#xff0c;因此需要一个中心化的协调机制来确保资源的访问是有序的&#xff0c;避免数据不一致的问题。 分布式锁的特性&#xf…...

Unity 获取RenderTexture像素颜色值

拿来吧你~ &#x1f9aa;功能介绍&#x1f32d;Demo &#x1f9aa;功能介绍 &#x1f4a1;不通过Texture2D 而是通过ComputerShader 提取到RenderTexture的像素值&#xff0c;效率有提升哦&#xff01; &#x1f4a1;通过扩展方法调用&#xff0c;方便快捷&#xff1a;xxxRT.G…...

Tomcat以服务方式启动,无法访问网络共享目录问题

关于“Tomcat以服务方式启动&#xff0c;无法访问网络共享目录问题”解决方式如下&#xff1a; 1、通过doc命令【services.msc】打开本地服务找到&#xff0c;找到tomcat服务所在位置 2、右键打开Tomcat服务的属性 3、选择 登陆选项卡 4、选择“此账户”选项&#xff0c;并…...

SVN的介绍

首先SVN是什么&#xff1a; Apache下的一个开源的项目Subversion&#xff0c;通常缩写为 SVN&#xff0c;是一个版本控制系统。 版本控制系统是一个软件&#xff0c;它可以伴随我们软件开发人员一起工作&#xff0c;让我们编写代码的完整的历史保存下来。 目前它的各个版本的…...

ZYNQ-700呼吸灯

参考野火例程 实现呼吸灯即要调整led亮的占比时间&#xff0c;完成视觉上看起来由灭到亮或者由亮到灭的过程。 如果主频为50MHz&#xff0c;理论上一秒钟我们可以控制50_000_000次led的亮和灭&#xff0c;肉眼不可能分辨出来每一次亮灭&#xff0c;如果这50M我们设定为间隔一…...

UE5学习日记——制作多语言版本游戏,同时初步学习UI制作、多语言化、控制器配置、独立进程测试、打包配置和快速批量翻译等

所有的文本类&#xff0c;无论变量还是控件等都能实现本地化&#xff0c;以此实现不同语言版本。 在这里先将重点注意标注一下&#xff1a; 所有文本类的变量、控件等都可以多语言&#xff1b;本地化控制板中收集、编译时&#xff0c;别忘了编译这一步&#xff1b;支持批量复制…...

电脑重启后word文档空白或打不开,word无法自动修复,如何拯救

最近编辑word文档&#xff0c;写了好几个星期的内容随着电脑重启的一瞬间&#xff0c;灰飞烟灭&#xff0c;让我简直痛不欲生&#xff01; 好在&#xff0c;天无绝人之路&#xff0c;以下两个方法拯救了地球 第一&#xff0c;普通的文档word自动修复不好使的时候&#xff0c;…...

MVC和MVVM这两种设计模式的区别

一、MVC和MVVM是什么&#xff1f; MVC是Model-View-Controller的简写&#xff0c;Model就是模型&#xff0c;对应后端数据&#xff0c;View就是视图对应用户界面&#xff0c;Controller就是控制器&#xff0c;对应页面的业务逻辑。 MVC的工作机制原理就是&#xff0c;用户操作…...

淘宝app端商品详情数据采集(商品价格,商品库存,商品销量,商品优惠券)

在淘宝App端采集商品详情数据&#xff0c;包括商品价格、库存、销量以及优惠券信息&#xff0c;可以通过多种方式实现。以下是几种常见的方法&#xff1a; 使用淘宝开放平台API&#xff1a; 淘宝开放平台提供了一系列API接口&#xff0c;这些接口允许开发者获取淘宝商品的详细…...

第42篇:随机存取存储器(RAM)模块<一>

Q&#xff1a;本期开始我们分期介绍随机存取存储器&#xff08;RAM&#xff09;模块及其设计实现方法。 A&#xff1a;随机存储器RAM&#xff0c;即工作时可以随时从一个指定地址读出数据&#xff0c;也可以随时将数据写入一个指定的存储单元。 DE2-115开发板上的Cyclone IV …...

在Java中实现记录1000万用户连续7天登录的功能,可以使用Redis的Bitmap来跟踪每个用户的登录状态

在Java中实现记录1000万用户连续7天登录的功能&#xff0c;可以使用Redis的Bitmap来跟踪每个用户的登录状态。以下是一个简化的Java示例&#xff0c;使用了Jedis库作为Redis的Java客户端。 首先&#xff0c;确保你已经在项目中添加了Jedis的依赖。如果你使用Maven&#xff0c;…...

深入探讨VIVE OpenXR:为Unity开发者的全面指南

随着虚拟现实&#xff08;VR&#xff09;和增强现实&#xff08;AR&#xff09;技术的迅速发展&#xff0c;开发者们对于能够简化和优化沉浸式应用开发的工具需求日益增长。HTC Vive 作为行业内的领先品牌&#xff0c;其最新推出的 VIVE OpenXR 插件为Unity开发者提供了一个强大…...

【Altium Designer 20 笔记】PCB线宽与过孔尺寸

电源线&#xff1a;40mil1A&#xff08;一般翻倍给&#xff09;,地线比电源线粗一点即可&#xff1b;信号线&#xff1a;10-15mil 一、线宽 市电的火线和零线&#xff1a;80-100mil12V /24V 20mil~60mil 5V 20-30mil 3V 20-30mil GND 越宽越好20-30mil普通信号线 10mil-15mil…...

基于java的社区生活超市管理系统

开发语言&#xff1a;Java 框架&#xff1a;ssm 技术&#xff1a;JSP JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclip…...

51单片机入门_江协科技_27~28_OB记录的自学笔记_AT24C02数据存储秒表

27. AT24C02(I2C总线) 27.1. 存储器介绍 27.2. 存储器简化模型介绍&#xff0c;存储原理 27.3. AT24C02介绍 •AT24C02是一种可以实现掉电不丢失的存储器&#xff0c;可用于保存单片机运行时想要永久保存的数据信息 •存储介质&#xff1a;E2PROM •通讯接口&#xff1a;I2…...

LeetCode-热题100:169. 多数元素

题目描述 给定一个大小为 n 的数组 nums &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 示例 1&#xff1a; 输入&#xff1a; nums [3,2,3] 输出&#xf…...

汽车维修类中译英的英语翻译

近年来&#xff0c;随着全球化的加速和汽车市场的不断扩大&#xff0c;汽车维修领域的交流与合作也日益频繁。汽车维修类中译英的英语翻译在汽车行业中扮演着至关重要的角色。那么&#xff0c;针对汽车维修类翻译&#xff0c;中译英的英语翻译有何技巧&#xff1f; 业内人士指出…...

java中的List,ArrayList和LinkedList集合

List集合&#xff1a; void add(int index, E element) Inserts the specified element at the specified position in this list (optional operation). 在此集合中的指定位置插入指定元素 E remove(int index) Removes the element at the specified position in this list (…...

RESTful API与Web应用程序构建:原理与实践

在现代Web开发中&#xff0c;RESTful API已经成为构建应用程序的核心组件之一。RESTful API不仅为前后端分离的开发模式提供了强有力的支持&#xff0c;还使得不同服务和应用之间的数据交互变得简单高效。本文将深入探讨RESTful API的原理&#xff0c;并展示如何使用它来构建We…...

输了,腾讯golang一面凉了

本月正值4月,是金三银四的找工作的最佳时机。同时竞争也是很大,因为每年这个时候快要毕业的大学生也进去了找工作的潮水中。 今天分享我的一位大佬朋友CC,勇闯腾讯golang的面试经历。 这次面试问题的方向主要集中在计算机基础个网络方面。 下面是主要问到的问题。 第一个…...

如何通过代码签名证书加强安全防护?

在当今数字化时代&#xff0c;安全防护是用户和企业保护其数据和应用程序免受恶意攻击的关键。代码签名证书是一种通过数字签名来验证软件代码来源和完整性的安全工具。通过对软件代码进行数字签名&#xff0c;代码签名证书可以加强安全防护&#xff0c;防止恶意软件和篡改攻击…...

Docker速成:新手变专家!

Docker介绍 容器历史 1、Chroot Jail 就是常见的chroot命令的用法。它在1979年的时候就出现了&#xff0c;被认为是最早的容器化技术之一。它可以把一个进程的文件系统隔离起来。 2、The FreeBSD Jail &#xff08;监狱&#xff09;实现了操作系统级别的虚拟化&#xff0c;他…...

numpy/arrayobject.h: No such file or directory

catkin编译时出现,numpy/arrayobject.h: No such file or directory 错误表明编译过程中找不到 NumPy 相关的头文件。这通常是因为环境中的 NumPy 没有被正确配置到包含路径中,或者 NumPy 没有被安装。以下是几个解决步骤来帮助你解决这个问题: 确认 NumPy 已安装 首先,确保…...

前端大文件分块上传、断点续传

文章目录 前端分块上传流程分块上传代码重点1. let start currentChunk * chunkSize;2. let end Math.min(file.size, start chunkSize);3. let chunk file.slice(start, end); 结合断点续传注意事项 大文件上传是一个复杂的过程&#xff0c;尤其是在前端&#xff0c;我们需…...

使用新版FLIR (FLIR_ADAS_v2) 数据集创建yolo格式数据集(目标检测)

FLIR在2022.1.19发布了新版的FLIR_ADAS_v2&#xff0c;有着更多的类别和数量更丰富的图像。数据集同步注释热图像和无注释RGB图像供参考。本文章主要介绍如何使用FLIR_ADAS_v2中的rgb图像和thermal图像来制作yolo格式数据集。 1.官方数据集下载&#xff1a;FLIR_ADAS_v2数据集…...

PHP发票查验接口未返回正确信息的原因、发票ocr识别接口

发票查验接口未返回正确信息的原因一般有以下几种&#xff0c;第一种可能是接口没有调通&#xff0c;第二种是本身这张发票就是一张错票、假票&#xff0c;第三种可能是税局系统或者网络问题等等。那么&#xff0c;遇到这种情况应该如何解决呢&#xff1f;翔云发票查验接口&…...

RA4000CE为汽车动力传动系统提供解决方案

目前汽车电气化的水平越来越高&#xff0c;其中比较显著的一个发展方向就是将发动机管理系统和自动变速器控制系统&#xff0c;集成为动力传动系统的综合控制(PCM)。作为汽车动力的核心部件&#xff0c;通过电子系统的运用&#xff0c;将外部多个传感器和执行环节的数据进行统一…...

算法中的二阶差分

众所周知&#xff0c;在往区间的每一个数都加上一个相同的数k&#xff0c;进行n次后会得到一个新的数列&#xff0c;如果每次加都循环区间挨个数加上k&#xff0c;这样时间复杂度无疑是O(n^2)&#xff0c;很高。这时可以采用一阶差分就可解决&#xff0c;这里默认会一阶差分&am…...

wordpress在哪修改代码/线上引流线下推广方案

查mysql bin-logbinlog基本定义&#xff1a;二进制日志&#xff0c;也成为二进制日志&#xff0c;记录对数据发生或潜在发生更改的SQL语句&#xff0c;并以二进制的形式保存在磁盘中&#xff1b; 作用&#xff1a;MySQL的作用类似于Oracle的归档日志&#xff0c;可以用来查看数…...

如何提高网站用户体验/手机百度网页版登录入口

Java SE、Java EE、Java ME三者的区别现在一个个来分析1. Java SE(Java Platform&#xff0c;Standard Edition)。Java SE 以前称为 J2SE。它允许开发和部署在桌面、服务器、嵌入式环境和实时环境中使用的 Java 应用程序。Java SE 包含了支持 Java Web 服务开发的类&#xff0c…...

wordpress禁用主题字体/推广网站大全

案例&#xff1a;电脑清理怎么做&#xff1f; 【求一个电脑清理的好方法&#xff01;电脑垃圾文件太多了又不敢随意删除&#xff0c;怕误删重要的文件&#xff01;哪位友友可以帮我出出主意呀&#xff1f;到底应该怎么清理电脑呢&#xff1f;】 电脑使用的时间长了都会慢慢变…...

做的网站 显示乱码/官网关键词优化价格

MySQL讲义第18讲——使用explain命令查看与分析索引的使用情况 文章目录MySQL讲义第18讲——使用explain命令查看与分析索引的使用情况一、数据准备二、使用 explain 分析查询三、explain 各个选项的详细说明及举例1、id2、select_type3、table4、partitions5、type6、possible…...

荔湾网站建设公司/天津搜索引擎优化

在刚刚过去的MWC2019上&#xff0c;如果要为无数终端展台总结一个特点&#xff0c;那么可能是这样的&#xff1a;千变万化&#xff0c;各显神通。早先几年&#xff0c;手机行业似乎比拼的是对趋势的跟随能力&#xff0c;行业有清晰的聚焦点&#xff0c;谁能更快跟随主流&#x…...

济南住房与城乡建设局网站/西安seo网站关键词

ASP操作数据库的类 作者&#xff1a;coldstone 时间&#xff1a; 2007-11-12 文档类型&#xff1a;原创 来自&#xff1a;蓝色理想 第 1 页 ASP操作数据库的类 [1] 第 2 页 ASP操作数据库的类 [2] 第 3 页 ASP操作数据库的类 [3] 第 4 页 ASP操作数据库的类 [4] 对于ASP…...