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

数据结构之“队列”(全方位认识)

                                    🌹个人主页🌹:喜欢草莓熊的bear

                                    🌹专栏🌹:数据结构


前言

上期博客介绍了”  栈 “这个数据结构,他具有先进后出的特点。本期介绍“ 队列 ”这个数据结构,他具有先进先出的特点。

 

目录

前言

一、队列

1.1队列的概念及结构

1.2队列的实现

1.2.1队列结构体定义

1.2.2初始化和销毁

1.2.3队尾插入和队头删除

1.2.3.1队尾插入

1.2.3.2队头删除

1.2.4获取队头与队尾数据

1.2.5返回队列里面的元素个数

1.2.6队列判空

1.3测试代码

1.4代码展示

头文件

 实现功能文件.c

总结


一、队列

1.1队列的概念及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有 先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为 队尾 出队列:进行删除操作的一端称为 队头。 根据队列的特点我们设计了以下,队尾用来入数据,队头用来出数据。

1.2队列的实现

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。

1.2.1队列结构体定义

根据上面提到的我们基于链表(这里的链表代指单链表)来实现队列。所以我就定义以下结构体

typedef int QDataType;typedef struct QueueNode//我们基于单链表创建的队列节点
{struct QueueNode* next;//下一节点的地址QDataType val;
}QNode;

 根据内容发现我们要获取队列的队头数据和队尾数据,所以我们要创建两个这样的结构体。由于节点的地址是通过一级指针来表示的,所以要用二级指针来储存,所以我们传参数时要使用二级指针。 记住只要涉及通过形式参数改变实参的都要传地址。

这时我们很牛的杭哥就给了一个思路,那就是再创建一个结构体里面的元素是上一个结构体。这样既满足了队头和队尾指针,还不需要传二级指针。因为有一个计数的功能所以再定义一个计数的变量。

typedef struct Queue //因为我们要传头指针和尾指针,所以我们要传两个指针//我们又要传二级指针,但是呢很麻烦,所以我们就新创建一个结构体来储存//上一个结构体的指针。
{QNode* phead;//队头指针QNode* ptail;//队尾指针int size;
}Queue;

1.2.2初始化和销毁

初始化:这一步和上次写的栈的初始化可以说是十分相似,第一步还是判断传来的是否为空队列,把结构体里面的指针置为NULL,再把size赋值位0。就ok了。

void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}

销毁:因为要申请空间,必定需要free,因为我们是基于链表实现的参考一下单链表的销毁。

 所以我们也需要一个一个节点释放,最后把指针指向空指针,把size赋值为0.

void QueueDestory(Queue* pq)
{assert(pq);QNode* pur = pq->phead;while (pur){QNode* cur = pur->next;free(pur);pur = cur;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

1.2.3队尾插入和队头删除

1.2.3.1队尾插入

因为我们是基于单链表的实现的,所以只需要创建节点就可以了,通过malloc申请空间。添加一个节点就开辟一块空间。

链表不为空;很简单直接进行尾插操作,不要忘了给size++。

链表为空;那就把头和尾指针同时指向这个新节点。

判别是否为空链表少不了。

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* Newnode = (QNode*)malloc(sizeof(QNode));if (Newnode == NULL){perror("malloc fail");return;}Newnode->next = NULL;Newnode->val = x;if (pq->phead==NULL)//空链表{pq->phead = pq->ptail = Newnode;}else{pq->ptail->next = Newnode;pq->ptail = Newnode;}pq->size++;//用来计数
}

1.2.3.2队头删除

链表中只有一个节点:当phead == ptail 时就只有一个节点了,所以我们把这个节点释放了以后要把phead 和 ptail 都置为空指针,预防出现野指针。

多个节点:我们创建一个节点用来储存头节点的下一个指针,这样释放了头节点也可以找到剩下的节点。对头删除当然要size--。

老生常谈,判断是否为空链表,还要判断是否还可以进行队头删除操作。也就队列里面还有数据吗

void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);if (pq->phead == pq->ptail)//只有一个节点{free(pq->phead);pq->phead = pq->ptail = NULL;}else//多个节点{QNode* tmp = pq->phead->next;free(pq->phead);pq->phead = tmp;}pq->size--;
}

1.2.4获取队头与队尾数据

很简单返回指针里面储存的数据就可以了,除了判断队列是否为空。还要判断这些头尾指针是否为空的。

QDataType QueueFront(Queue* pq) //返回队头数据
{assert(pq);assert(pq->phead);return pq->phead->val;
}QDataType QueueBack(Queue* pq) //返回队尾数据
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}

1.2.5返回队列里面的元素个数

这时就可以体现出我们再第二给结构体中创建size的价值了,我们直接返回size。没有创建size我们就需要遍历队列了。

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

1.2.6队列判空

前面创建的szie又帮了大忙,还可以用来判断是否为空对列。

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

1.3测试代码

进行了4个数据的插入,检测了判空、获取队头元素、队头删除。等操作,在这里还是建议大家每完成一个功能就进行测试,不然一起测试出现了很多问题修改起来很麻烦的。作者身有体会,

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);printf("%d ", QueueFront(&q));QueuePop(&q);QueuePush(&q, 3);QueuePush(&q, 4);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}QueueDestory(&q);return 0;
}

 成功实现了队列 “ 先进先出 ”的特点。

1.4代码展示

头文件

Queue.h
#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>typedef int QDataType;typedef struct QueueNode//我们基于单链表创建的队列节点
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue //因为我们要传头指针和尾指针,所以我们要传两个指针//我们又要传二级指针,但是呢很麻烦,所以我们就新创建一个结构体来储存//上一个结构体的指针。
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化和销毁
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);//队尾插入和队头删除
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);//获取队头、尾数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);//返回个数和判空
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);

 实现功能文件.c

Queue.c
#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueueDestory(Queue* pq)
{assert(pq);QNode* pur = pq->phead;while (pur){QNode* cur = pur->next;free(pur);pur = cur;}pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* Newnode = (QNode*)malloc(sizeof(QNode));if (Newnode == NULL){perror("malloc fail");return;}Newnode->next = NULL;Newnode->val = x;if (pq->phead==NULL)//空链表{pq->phead = pq->ptail = Newnode;}else{pq->ptail->next = Newnode;pq->ptail = Newnode;}pq->size++;//用来计数
}void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);if (pq->phead == pq->ptail)//只有一个节点{free(pq->phead);pq->phead = pq->ptail = NULL;}else//多个节点{QNode* tmp = pq->phead->next;free(pq->phead);pq->phead = tmp;}pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

总结

很感谢大家的喜欢,有问题大家在评论区发来我们一起交流。下期预告通过栈和队列互相实现对方的功能。

相关文章:

数据结构之“队列”(全方位认识)

&#x1f339;个人主页&#x1f339;&#xff1a;喜欢草莓熊的bear &#x1f339;专栏&#x1f339;&#xff1a;数据结构 前言 上期博客介绍了” 栈 “这个数据结构&#xff0c;他具有先进后出的特点。本期介绍“ 队列 ”这个数据结构&#xff0c;他具有先进先出的特点。 目录…...

密码学复习

目录 基础 欧拉函数 欧拉函数φ(n)定义 计算方法的技巧 当a=a_1*a_2*……*a_n时 欧拉定理 剩余系 一些超简单密码 维吉尼亚 密钥fox 凯撒(直接偏移) 凯特巴氏(颠倒字母表) 摩斯密码(字母对应电荷线) 希尔(hill)密码 一些攻击 RSA 求uf+vg=1 快速幂模m^…...

【文献解析】一种像素级的激光雷达相机配准方法

大家好呀&#xff0c;我是一个SLAM方向的在读博士&#xff0c;深知SLAM学习过程一路走来的坎坷&#xff0c;也十分感谢各位大佬的优质文章和源码。随着知识的越来越多&#xff0c;越来越细&#xff0c;我准备整理一个自己的激光SLAM学习笔记专栏&#xff0c;从0带大家快速上手激…...

Http 实现请求body体和响应body体的双向压缩方案

目录 一、前言 二、方案一(和http header不进行关联) 二、方案二(和http header进行关联) 三、 客户端支持Accept-Encoding压缩方式,服务器就一定会进行压缩吗? 四、参考 一、前言 有时请求和响应的body体比较大,需要进行压缩,以减少传输的带宽。 二、方案一(和…...

C++(Qt)-GIS开发-简易瓦片地图下载器

Qt-GIS开发-简易瓦片地图下载器 文章目录 Qt-GIS开发-简易瓦片地图下载器1、概述2、安装openssl3、实现效果4、主要代码4.1 算法函数4.2 瓦片地图下载url拼接4.3 多线程下载 5、源码地址6、参考 更多精彩内容&#x1f449;个人内容分类汇总 &#x1f448;&#x1f449;GIS开发 …...

誉天教育7月开班计划:为梦想插上腾飞的翅膀!

随着夏日的脚步渐近&#xff0c;誉天教育也迎来了新一轮的学习热潮。在这个充满活力和希望的季节里&#xff0c;我们精心策划了7月的开班计划&#xff0c;旨在为广大学子提供一个优质、高效的学习平台&#xff0c;助力他们追逐梦想&#xff0c;实现自我价值。 本月 Linux云计算…...

STM32基础篇:GPIO

GPIO简介 GPIO&#xff1a;即General Purpose Input/Output&#xff0c;通用目的输入/输出。就是一种片上外设&#xff08;内部模块&#xff09;。 对于STM32的芯片来说&#xff0c;周围有一圈引脚&#xff0c;有时需要对引脚进行读写&#xff08;读&#xff1a;从外部输入一…...

HTTPS 发送请求出现TLS握手失败

最近在工作中&#xff0c;调外部接口&#xff0c;发现在clientHello步骤报错&#xff0c;服务端没有返回serverHello。 从网上找了写方法&#xff0c;都没有解决&#xff1b; 在idea的vm options加上参数&#xff1a; -Djavax.net.debugSSL,handshake 把SSL和handshake的日…...

数字化精益生产系统--IFS财务管理系统

IFS财务管理系统是一款功能丰富、高效且灵活的企业财务管理软件&#xff0c;广泛应用于多个行业和不同规模的企业中。以下是对IFS财务管理系统的功能设计&#xff1a;...

基于SpringBoot的校园台球厅人员与设备管理系统

本系统是要设计一个校园台球厅人员与设备管理系统&#xff0c;这个系统能够满足校园台球厅人员与设备的管理及用户的校园台球厅人员与设备管理功能。系统的主要功能包括首页、个人中心、用户管理、会员账号管理、会员充值管理、球桌信息管理、会员预约管理、普通预约管理、留言…...

免杀笔记 ---> Session0--DLL注入

刚更新完上一篇&#xff0c;于是我们就马不停蹄的去跟新下一篇&#xff01;&#xff01; Session0注入 &#xff1a;&#xff1a; 各位看官如果觉得还不错的可以给博主点个赞&#x1f495;&#x1f495; 这次&#xff0c;我把这个脚本直接传到Github上了 喜欢的师傅点个Star噢…...

如何做好IT类的技术面试?

我们在找工作时&#xff0c;需要结合自己的现状&#xff0c;针对意向企业做好充分准备。作为程序员&#xff0c;你有哪些面试IT技术岗的技巧&#xff1f; 方向一&#xff1a;分享你面试IT公司的小技巧 我分享一些基于广泛观察和用户反馈的面试IT公司的小技巧&#xff1a; 技术准…...

A7 配置方式Master SPI如何更改位宽

在 FPGA 完成自初始化后&#xff0c;INIT 释放&#xff0c;FPGA 对模式引脚 (M[2:0]) 进行采样&#xff0c;以确定使用哪种配置模式。当模式引脚 M[2:0] 001 时&#xff0c;FPGA 开始以大约 3 MHz 的频率在 CCLK 上输出时钟。随后&#xff0c;FCS_B 驱动为低电平&#xff0c;紧…...

linux kthread任务管理

目录 一、linux 创建内核线程1.1 kthread_create1.2 kthread_create_worker kthread_queue_work 二、设置线程优先级和调度策略2.1 sched_setscheduler2.2 调度策略 一、linux 创建内核线程 1.1 kthread_create 在 linux 中&#xff0c;可以使用 kthread_create 接口创建内核…...

第一节 网络安全概述

一.网络空间安全 网络空间&#xff1a;一个由信息基础设施组成相互依赖的网络。 ---- 海陆空天&#xff08;大海、陆 地、天空、航天&#xff09; 通信保密阶段 ---- 计算机安全 ----- 信息系统安全 ----- 网络空间安全 计算机安全&#xff1a;开始秉持着“严于律己&#x…...

星光云VR全景系统源码

星光云VR全景系统源码 体验地址请查看...

spdlog一个非常好用的C++日志库(七): 源码分析之异常类spdlog_ex

目录 1.自定义异常类spdlog_ex 1.1.通用异常 1.2.系统调用异常 1.3.what()函数 2.异常的使用 2.1.抛出异常 2.2.控制异常使用 1.自定义异常类spdlog_ex 标准库异常类&#xff08;std::exception&#xff09;系列&#xff0c;能满足大多数使用异常的场景&#xff0c;但对…...

从一次 SQL 查询的全过程了解 DolphinDB 线程模型

1. 前言 DolphinDB 的线程模型较为复杂&#xff0c;写入与查询分布式表都可能需要多个类型的线程。通过了解 SQL 查询的全过程&#xff0c;可以帮助我们了解 DolphinDB 的线程模型&#xff0c;掌握 DolpinDB 的配置&#xff0c;以及优化系统性能的方法。 本教程以一个分布式 …...

Vue3.js“非原始值”响应式实现基本原理笔记(二)

如果您觉得这篇文章有帮助的话&#xff01;给个点赞和评论支持下吧&#xff0c;感谢~ 作者&#xff1a;前端小王hs 阿里云社区博客专家/清华大学出版社签约作者/csdn百万访问前端博主/B站千粉前端up主 此篇文章是博主于2022年学习《Vue.js设计与实现》时的笔记整理而来 书籍&a…...

论文 | PRCA: 通过可插拔奖励驱动的上下文适配器拟合用于检索问答的黑盒大语言模型

论文全称&#xff1a;PRCA: Fitting Black-Box Large Language Models for Retrieval Question Answering via Pluggable Reward-Driven Contextual Adapter 核心问题&#xff1a;如何在检索增强式问答&#xff08;ReQA&#xff09;任务中&#xff0c;利用大型语言模型&#xf…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

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

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

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...