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

数据结构——队列的模拟实现

大家好,上一篇博客我带领大家进行了数据结构当中的栈的模拟实现

今天我将带领大家实现一个新的数据结构————队列

一:队列简介

首先来认识一下队列:

队列就像我们上学时的排队一样,有一个队头也有一个队尾。

有人入队的话就从对尾入队出队只能从对头出队,队头出队之后后面的人才可以选择出队

队列的特点就是:队尾入,对头出,先进先出(first in first out)(先入队的先出队)。

1 2 3 4 入——1 2 3 4出。

队列的模拟实现是选择数组还是链表呢?

队列的特定规则需要两个指针分别指向首元素和尾原元素,如果选用数组的话,删除队首的数据就比较复杂(向前覆盖,时间复杂度为O(N))。

相较于数组,使用链表删除队首的数据就简单了很多,因此我们选择通过链表的形式来实现队列。

给出两个指针(一个把住头,一个把住尾),一个指向队首结点(负责队首出数据),一个指向队尾结点(负责队尾插入数据)。

二:队列的模拟实现

0.队列结构题的创建

与前面几个数据结构相比,队列这一数据结构需要两个指针,一个指向队首,一个指向队尾。

这里为了方便,将两个结点指针用另一个结构体分装。(否则的话每次传参传两个结点指针变量就很麻烦)。

size表示队列中结点个数。

2.队列的初始化

队列的模拟实现使用的是链表,队列中的数据是存储在链表的结点中的,因此,队列的初始化就是先给上两个空指针,后续有了结点之后再使用。

3.队尾插入数据(入队)

插入数据首先要开辟一个结点的空间用来存储数据。

插入数据之前首先要判断是否队列为空:

如果队列为空,就让两个指针都指向新结点。

如果队列不为空,队头结点不动,建立队尾结点与新结点之间的关系。

4.队头删除数据(出队)

删除数据就要先断言是否有数据

删除数据就是改变头结点指针的指向关系。

这里也要分两种情况进行讨论:

如果队列中只有一个结点,直接free就好了。

如果队列中不仅仅只有一个结点,free之前要先保留第二个结点的位置,否则后续就找不到了。

5.求队列中的数据个数

6.获取队首数据

想要获取队列中的数据就先要断言判断队列不能为空。

7.获取队尾数据

想要获取队列中的数据就先要断言判断队列不能为空。

8.队列的销毁

队列的销毁和单链表的销毁类似,还是从前到后,依次free

注意:free掉前一个结点之前一定要保留下一个结点的位置,否则free掉对头其余的结点就再也找不到了,会造成内存泄漏。

9.队列的测试

三:队列的经典题目

1.题目一:

使用两个队列实现后入先出的栈

队列的特点是先入队的数据先出队,栈的特点是后入栈的数据先出栈。

我们可以使用两个队列来实现栈的功能。

我们先将1 2 3 4依次放入一个队列中,出数据的话要先出4,但是队列只能先出1 2 3.

这时候我们就要用到第二个队列,将1 2 3存放到第二个队列中,再出4就可以了。

下一步出3,先将1 2导入另一个空队列中就可以出3了。

如果要插入数据(数据进栈)的话就在有数据的那个队列尾部插入数据

依次进行,使用两个队列实现栈就完工了。

2.题目二:

使用两个栈实现先进先出的队列

队列的特点是先入队的数据先出队,栈的特点是后入栈的数据先出栈。

我们可以使用两个栈来实现队列的功能。

一个栈只管用来出数据,另外一个栈只管用来进数据。

比如:将数据1 2 3 4进入到一个栈中,由于队列的特性是先进先出,因此出数据的话要先出1,但按照栈的逻辑要先出4.因此此时要用到另外一个栈来导数据。将4 3 2导入另外一个栈中,然后出1。4 3 2就可以依次出栈了,入数据的话就只在另一个栈中入数据,当4 3 2全部出完后,再将入数据的栈中的数据导入出数据的栈中,这样往复,就可以实现使用两个栈来实现队列。

完:

相关文章:

数据结构——队列的模拟实现

大家好,上一篇博客我带领大家进行了数据结构当中的栈的模拟实现 今天我将带领大家实现一个新的数据结构————队列 一:队列简介 首先来认识一下队列: 队列就像我们上学时的排队一样,有一个队头也有一个队尾。 有人入队的话就…...

在window环境下安装openssl生成钥私、证书和签名,nodejs利用express实现ssl的https访问和测试

在生成我们自己的 SSL 证书之前,让我们创建一个简单的 Express应用程序。 要创建一个新的 Express 项目,让我们创建一个名为node-ssl -server 的目录,用终端cmd中进入node-ssl-server目录。 cd node-ssl-server 然后初始化一个新的 npm 项目…...

Redis 最佳实践

这是以前写下来的文章,发出来备份一下 Redis 在企业中的最佳实践可以帮助提高性能、可用性和数据管理效率。以下是一些推荐的做法: 选择合适的数据结构: 根据需求选择适当的 Redis 数据结构(如 Strings、Lists、Sets、Hashes、So…...

网站灰度发布?Tomcat的8005、8009、8080三个端口的作用什么是CDNLVS、Nginx和Haproxy的优缺点服务器无法开机时

前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默, 忍不住分享一下给大家。点击跳转到网站 学习总结 1、掌握 JAVA入门到进阶知识(持续写作中……) 2、学会Oracle数据库入门到入土用法(创作中……) 3、手把…...

从客户跟进到库存管理:看板工具赋能新能源汽车销售

在新能源汽车市场日益扩张的今天,门店销售管理变得更加复杂和重要。从跟踪客户线索到优化订单流程,再到团队协作,效率低下常常成为许多门店的“隐形成本”。如果你曾为销售流程不畅、客户管理混乱而苦恼,那么一种简单直观的工具—…...

算法时间空间复杂度的计算

一、时间复杂度 :找循环最内层 二、空间复杂度: 1.找int float等变量 2.递归调用:空间复杂度递归调用的深度 int 型变量: 四个字节...

人才画像系统如何支撑企业的人才战略落地

在当今竞争激烈的商业环境中,企业的人才战略对于其长期发展至关重要。为了有效实施人才战略,企业需要一套精准、高效的人才管理工具,而人才画像系统正是满足这一需求的关键解决方案。本文将探讨人才画像系统如何支撑企业的人才战略落地&#…...

[数据结构] 链表

目录 1.链表的基本概念 2.链表的实现 -- 节点的构造和链接 节点如何构造? 如何将链表关联起来? 3.链表的方法(功能) 1).display() -- 链表的遍历 2).size() -- 求链表的长度 3).addFirst(int val) -- 头插法 4).addLast(int val) -- 尾插法 5).addIndex -- 在任意位置…...

三格电子——新品IE103转ModbusTCP网关

型号:SG-TCP-IEC103 产品概述 IE103转ModbusTCP网关型号SG-TCP-IEC103,是三格电子推出的工业级网关(以下简称网关),主要用于IEC103数据采集、DLT645-1997/2007数据采集,IEC103支持遥测和遥信,可…...

遥感影像目标检测:从CNN(Faster-RCNN)到Transformer(DETR

我国高分辨率对地观测系统重大专项已全面启动,高空间、高光谱、高时间分辨率和宽地面覆盖于一体的全球天空地一体化立体对地观测网逐步形成,将成为保障国家安全的基础性和战略性资源。未来10年全球每天获取的观测数据将超过10PB,遥感大数据时…...

深入详解神经网络基础知识——理解前馈神经网络( FNN)、卷积神经网络(CNN)和循环神经网络(RNN)等概念及应用

深入详解神经网络基础知识 深度学习作为人工智能(AI)的核心分支之一,近年来在各个领域取得了显著的成果。从图像识别、自然语言处理到自动驾驶,深度学习技术的应用无处不在。而深度学习的基础,神经网络,是理…...

react 项目打包二级目 使用BrowserRouter 解决页面刷新404 找不到路由

使用BrowserRouter package 配置 &#xff08;这部分代码可以不做配置也能实现&#xff09; {"homepage": "/admin",}vite.config 配置 export default defineConfig({base: /admin])BrowserRouter 添加配置项 <BrowserRouter basename/admin>&l…...

EasyPlayer.js播放器Web播放H.265要兼顾哪些方面?

在数字化时代&#xff0c;流媒体技术已经成为信息传播和娱乐消费的重要方式。随着互联网技术的飞速发展和移动设备的普及&#xff0c;流媒体服务正在重塑我们的生活和工作方式。从视频点播、在线直播到音乐流媒体&#xff0c;流媒体技术的广泛应用不仅改变了内容的分发和消费模…...

使用 acme.sh 申请域名 SSL/TLS 证书完整指南

使用 acme.sh 申请域名 SSL/TLS 证书完整指南 简介为什么选择 acme.sh 和 ZeroSSL&#xff1f;前置要求安装过程 步骤一&#xff1a;安装 acme.sh步骤二&#xff1a;配置 ZeroSSL 证书申请 方法一&#xff1a;手动 DNS 验证&#xff08;推荐新手使用&#xff09;方法二&#xf…...

睡岗和玩手机数据集,4653张原始图,支持YOLO,VOC XML,COCO JSON格式的标注

睡岗和玩手机数据集&#xff0c;4653张原始图&#xff0c;支持YOLO&#xff0c;VOC XML&#xff0c;COCO JSON格式的标注 数据集分割 训练组70&#xff05; 3257图片 有效集20&#xff05; 931图片 测试集10&#xff05; 465图片 预处理 没有采用任何预处…...

[Unity] 【VR】【游戏开发】在VR中使用New Input System获取按键值的完整教程

在使用Unity开发VR项目时,推荐使用 New Input System 来处理输入操作。相比于旧的Input系统,New Input System更加灵活、功能强大,尤其在处理VR控制器的按键输入时具有明显优势。本文将详细介绍如何在VR项目中使用New Input System获取按键值,并通过代码示例和图文讲解,帮…...

网络安全渗透有什么常见的漏洞吗?

弱口令与密码安全问题 THINKMO 01 暴力破解登录&#xff08;Weak Password Attack&#xff09; 在某次渗透测试中&#xff0c;测试人员发现一个网站的后台管理系统使用了非常简单的密码 admin123&#xff0c;而且用户名也是常见的 admin。那么攻击者就可以通过暴力破解工具&…...

2024年合肥师范学院信息安全小组内部选拔赛(c211)WP

目录 前言MISC签到题_熟悉吗又来一道签到题文件包含 CRYPTO古典1古典2RSA webbaby_sql 前言 [HFNU 校级选拔] 已经结束&#xff0c;接下来一起了解下题目是怎么做的。 通过网盘分享的文件&#xff1a;ARCHPR_4.66.266.0_汉化绿色版.7z 链接: https://pan.baidu.com/s/1N_c0PJX…...

GESP CCF C++八级编程等级考试认证真题 2024年12月

202412 GESP CCF C八级编程等级考试认证真题 1 单选题&#xff08;每题 2 分&#xff0c;共 30 分&#xff09; 第 1 题 小杨家响应国家“以旧换新”政策&#xff0c;将自家的汽油车置换为新能源汽车&#xff0c;正在准备自编车牌。自编车牌包括5 位数字或英文字母&#xff0c…...

GlusterFS 部署全攻略:详细步骤与要点解析(上)

文章目录 1、二进制部署1.1 安装yum源1.2 准备服务器1.3 添加本地解析1.4关闭防火墙及selinux1.5 加载内核模块1.6 格式化分区和挂载brick1.7 安装GlusterFS1.8 iptables配置1.9 配置可信任池1.10 设置GlusterFS卷1.11 测试volume卷 2、使用heketi将二进制GlusterFS集群作为k8s…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

「Java基本语法」变量的使用

变量定义 变量是程序中存储数据的容器&#xff0c;用于保存可变的数据值。在Java中&#xff0c;变量必须先声明后使用&#xff0c;声明时需指定变量的数据类型和变量名。 语法 数据类型 变量名 [ 初始值]; 示例&#xff1a;声明与初始化 public class VariableDemo {publi…...