一篇讲透数据结构之链式队列
目录
一.队列的定义
二.队列的分类
三.队列的功能
四.链式队列的声明
五.链式队列功能的实现
5.1 初始化队列
5.2 判断队列是否为空
5.3 获取队头元素
5.4 获取队尾元素
5.5获取队列长度
5.6 入队
5.7出队
5.8 打印队列元素
5.9 销毁队列
一.队列的定义
队列(queue)是一种只允许在一端进行插入操作,而在另一端进行删除操作的线性表。其严格遵循先进先出(First In First Out)的规则,简称FIFO。
队列与栈类似,实现方式有两种。一种是以数组的方式实现,另一种以单链表来实现。这两种实现方式各有优劣,并且都有细节需要处理。
二.队列的分类
队列可以根据分为单向队列、双向队列(特殊的队列)、循环队列三种。
其中,单向队列为本篇文章中要实现的队列
双向队列为可以从两端进行插入和删除的队列(我也不知道为什么要弄一个这样的队列出来,根定义不一样了都)
循环队列是循环的队列。
三.队列的功能
队列主要需要实现如下功能:
5.1 初始化队列
5.2 判断队列是否为空
5.3 获取队头元素
5.4 获取队尾元素
5.5获取队列长度
5.6 入队
5.7出队
5.8 打印队列元素
5.9 销毁队列
四.链式队列的声明
由于我们实现的队列是由链表实现的,因此我们需要先声明一个结构体类型表示链表。
之后,我们就可以声明队列了,队列其中的成员分别是队列的头指针、队列的尾指针、队列的长度。
typedef int QDataType;
typedef struct QueueNode
{QDataType data;//队列数据struct QueueNode* next;//指向下一个队列块
}QNode;
typedef struct Queue
{QNode* front;//队列头QNode* rear;//队列尾int size;//队列长度
}Queue;
五.链式队列功能的实现
5.1 初始化队列
初始化队列,就是给队列的每个成员赋初值。
由于front和rear是指针,因此我们初始化为空。
由于size是整型,因此我们初始化为0.
void QueueInit(Queue* q)
{q->front = NULL;q->rear = NULL;q->size = 0;
}
5.2 判断队列是否为空
判断一个队列是否为0的方式有很多,
可以通过判断size是否为0判断;
也可以通过队列头和队列尾的指针来判断 。
这里我们通过size是否等于0来判断。
bool QueueEmpty(Queue* q)
{assert(q);return q->size;
}
5.3 获取队头元素
获取队列的头元素,只要保证队列存在并且不为空即可。
队列的头元素就是队列头指针的data,我们访问即可。
QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->front->data;
}
5.4 获取队尾元素
队列的尾部数据的获取,和获取队头数据类似,直接返回队尾指针即可。
、
QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->rear->data;
}
5.5获取队列长度
直接返回size即可。
//获取队列长度
int QueueSize(Queue* q)
{assert(q);return q->size;
}
5.6 入队
入队列,首先我们应动态申请一个链表结点。
之后我们就可以自行初始化链表结点的值了。
再然后我们要分为两种情况了,
第一种情况是链表没有结点,这时我们的结点入队列对队头和队尾都会产生影响;
第二种情况是链表中已有结点,这时我们的结点入队列只会对队尾产生影响。
因此我们在这里需要通过分支结构处理这个问题。
由于这两种情况都需要处理size,为了防止代码冗长,我们将size的自增语句写在分支结构之外。
void QueuePush(Queue* q, QDataType x)
{assert(q);//初始化新结点QNode* newnode = (QNode*)malloc(sizeof(QNode));newnode->data = x;newnode->next = NULL;//队列为空if (q->front == q->rear == NULL){//更新信息q->front = q->rear = newnode;//q->size++;}else{//更新信息q->rear->next = newnode;q->rear = newnode;//q->size++;}q->size++;
}
5.7出队
在已经讲解了入队列之后,我们再讲解一下出队列。
出队列首先要确保队列中已有队列结点,否则将无队列结点可出。
出队列也分为两种情况,
第一种情况是队列中只有一个结点,我们需要释放掉这个结点并将队列的头指针和尾指针置空;
第二种情况是队列中有好多个结点,这时我们释放掉队列头的结点之后,更新队头即可。
//出队
//1.考虑情况要全面
//2.在更新队列时,要将数据结构中受到影响的成员全部更新
//3.如果分不清谁受到了影响,就逐个排查。
void QueuePop(Queue* q)
{assert(q);assert(q->front);if (q->size == 1){free(q->front);q->front = q->rear = NULL;}else{QNode* ret = q->front->next;free(q->front);q->front = ret;}q->size--;
}
在有多个结点的情况下,我们在出队时,需要注意的是需要定义一个指针保存队头的下一个结点,否则在更新时则无从下手。
5.8 打印队列元素
与链表的打印方式一样,打印即可。
void QueuePrint(Queue* q)
{assert(q);QNode* cur = q->front;printf("队头->");while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("队尾");
}
5.9 销毁队列
与链表的销毁方法一样,销毁即可。
void QueueDestroy(Queue* q)
{assert(q);QNode* ret = q->front;while (ret){QNode* next = ret->next;free(ret);ret = next;}q->front = q->rear = NULL;
}
相关文章:

一篇讲透数据结构之链式队列
目录 一.队列的定义 二.队列的分类 三.队列的功能 四.链式队列的声明 五.链式队列功能的实现 5.1 初始化队列 5.2 判断队列是否为空 5.3 获取队头元素 5.4 获取队尾元素 5.5获取队列长度 5.6 入队 5.7出队 5.8 打印队列元素 5.9 销毁队列 一.队列的定义 队列&…...

【408真题】2009-24
“接”是针对题目进行必要的分析,比较简略; “化”是对题目中所涉及到的知识点进行详细解释; “发”是对此题型的解题套路总结,并结合历年真题或者典型例题进行运用。 涉及到的知识全部来源于王道各科教材(2025版&…...

6年IT找工作想法
由于我学历比较低,当时没好好学,后面参加了大数据培训,现在也已经有6年了。 我是计算机专业的,我的培训同学有些不是计算机的,但是是本科,双非一本的这种,在6年后和我的差距不是一点点了&#x…...

TOPSIS综合评价
TOPSIS法(Technique for Order Preference by Similarity to an Ideal Solution)是一种常用的综合评价方法,该方法根据有限个评价对象与理想化目标的接近程度进行排序,是在现有的对象中进行相对优劣的评价。 TOPSIS法的原理是通过…...

修改vuetify3的开关组件v-switch在inset模式下的大小
<v-switchv-model"model":label"Switch: ${model.toString()}"hide-detailsinset></v-switch>使用方式1:本页面使用 本页面中使用,必须要含有lang“scss” scoped,才会生效 <style lang"scss"…...

m1系列芯片aarch64架构使用docker-compose安装nacos
之前看到 DockerHub 上发布了 m1 芯片 aarch64 架构的 nacos 镜像, 所以就尝试的安装了下, 亲测可用: 一. docker-compose.yml 编写 请确保自己的 mysql 服务已经启动了, 并且允许远程连接 volumes 挂载目录需要换成自己的目录 二. 容器运行和网络组 2.1 查看容器运行情况 …...

优化耗时业务:异步线程在微服务中的应用
大家好,我是程序员大猩猩。 大家都知道,在我们实际开发过程中,我们经常会遇到一些耗时的业务和逻辑,比如说要上传什么大文件,又或者是大文件的数据处理。我们不能一个接口上等着这些耗时任务完成之后了,再…...

torch.scatter看图理解
torch.Tensor.scatter 有 4 个参数: scatter(dim, index, src, reduceNone) 先忽略 Reduce,最后再解释。先从最简单的开始。我们有一个 (2,4) 形状的张量,里面填充了 1: 粉红色的符号表示张量结构 并且我们传入相应的参数并得到…...

适合学生党的蓝牙耳机有哪些?盘点四大性价比蓝牙耳机品牌
对于追求高品质音乐体验而又预算有限的学生党来说,一款性价比高的蓝牙耳机无疑是最佳选择,在众多品牌和型号中,如何挑选到既适合自己需求又价格亲民的蓝牙耳机,确实是一个值得思考的问题,作为一个蓝牙耳机大户…...

【ORB_SLAM系列3】—— 如何在Ubuntu18.04中使用自己的单目摄像头运行ORB_SLAM3(亲测有效,踩坑记录)
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、ORB_SLAM3源码编译二、ORB_SLAM3实时单目相机测试1. 查看摄像头的话题2. 运行测试 三. 运行测试可能的报错1. 报错一(1) 问题描述(2) 原因分析(3) 解决 2. …...

Science Advances|柔性超韧半导体纤维的大规模制备(柔性半导体器件/可穿戴电子/纤维器件/柔性电子)
北京大学 雷霆(Ting Lei)团队,在《Science Advances》上发布了一篇题为“Continuous production of ultratough semiconducting polymer fibers with high electronic performance”的论文。论文内容如下: 一、 摘要 共轭聚合物具有良好的光电特性,但其脆性和机械特性差,…...

VirtualBox虚拟机与bhyve虚拟机冲突问题解决@FreeBSD
问题 在安装完bhyve虚拟系统的主机上启动VirtualBox虚拟机的时候,报错:不能为虚拟电脑 debian 打开一个新任务. VirtualBox cant operate in VMX root mode. Please close all other virtualization programs. (VERR_VMX_IN_VMX_ROOT_MODE). 返回 代码…...

【网络层】ICMP 因特网控制协议
文章目录 ICMP 含义以及作用ICMP协议解析结合ICMP协议和ping常见问题 ICMP 含义以及作用 ICMP:Internet control massage protocol 因特网控制协议 Internet控制报文协议ICMP是网络层的一个重要协议。 ICMP协议用来在网络设备间传递各种差错和控制信息,…...

汇编原理(四)[BX]和loop指令
loop:循环 误区:在编译器里写代码和在debug里写代码是不一样的,此时,对于编译器来说,就需要用到[bx] [bx]: [bx]同样表示一个内存单元,他的偏移地址在bx中,比如下面的指令 move bx, 0 move ax,…...

Linux查看设备信息命令
dmidecode | grep Product Name 查看grub版本号:rpm -qa | grep -i "grub" 客户端操作系统版本: cat /etc/issue cat /etc/redhat-release 处理器品牌及型号: less /proc/cpuinfo |grep model...

transformer的特点
Transformers是一种用于处理序列数据的神经网络架构,最初由Vaswani等人在2017年提出,主要用于自然语言处理任务。与传统的循环神经网络(RNN)和卷积神经网络(CNN)不同,Transformers采用了一种全新…...

27快28了,想转行JAVA或者大数据,还来得及吗?
转行到JAVA或者大数据领域,27岁快28岁的年龄完全来得及。我这里有一套编程入门教程,不仅包含了详细的视频讲解,项目实战。如果你渴望学习编程,不妨点个关注,给个评论222,私信22,我在后台发给你。…...

英飞凌 AURIX TriCore 单片机开发入门
文章目录 目的硬件准备AURIX™ Development StudioInfineon MemtoolAURIX™ iLLD Drivers总结 目的 英飞凌的32位 AURIX™ TriCore™ 系列单片机 经常用于汽车和工业领域。开发该系列单片机比较常用的开发环境有 HighTec 和 AURIX™ Development Studio 。本文将基于后者&…...

Centos安装,window、ubuntus双系统基础上安装Centos安装
文章目录 前言一、准备工作二、开始安装1、2、首先选择DATE&TIME2、选择最小安装3、 选择安装位置 总结 前言 因工作需要,我需要在工控机上额外装Centos7系统,不过我是装在机械硬盘上了不知道对性能是否有影响,若有影响,后面…...

2023年全国职业院校技能大赛(高职组)“云计算应用”赛项赛卷6(容器云)
#需要资源(软件包及镜像)或有问题的,可私聊博主!!! #需要资源(软件包及镜像)或有问题的,可私聊博主!!! #需要资源(软件包…...

第13章 常用类
一、包装类 二、String String的常用方法: equals:判断内容是否相等,区分大小写。 String str1 "hello";String str2 "Hello";System.out.println(str1.equals(str2));//false equalsIgnoreCase:判断内容…...

15.数组的方法(改变原数组和不改变原数组)
改变原数组 (1)pop 语法:数组名.pop() 作用:删除数组最后一项 返回值:返回被删除的那一项 var arr=["zhangsna","lisi","wanger","mazi"] var res=arr.pop() console.log(arr) //[zhangsna, lisi, wange…...

随后记: uniapp uview u-dropdown 下拉菜单固定高度滑动不生效
使用u-dropdown 下拉组件 按照uview官网讲解使用 配置根本不生效 scroll-y"true" style"height: 200rpx;" 但是在下拉的时候,不能上下滑动 ,原因是自带的遮罩层挡住了 解决办法:在下拉菜单打开和关闭的时候,…...

一文梭哈动态代理
大家好,这里是教授.F 引入: 先看一个生活化的例子,如果一个明星他会唱歌,会跳舞。但是自己太忙了,没时间去宣传自己和去找工作,所以他需要有人帮他代理。然后呢这个代理者也需要知道他会什么,什…...

如何查询Windows 10电脑的IP地址
如何查询Windows 10电脑的IP地址 引言 在Windows 10操作系统中,查询电脑的IP地址是一项基本而重要的任务,无论是为了配置网络、解决连接问题,还是进行远程访问。 基础知识 IP地址:互联网协议地址,用于标识网络中的…...

java: 警告: 源发行版 8 需要目标发行版 8
前言 该文章中项目背景是:IDEA与设置的版本与实际电脑配置的不一致。也就是说只改了这个团队项目的JDK版本,IDEA上其它项目JDK版本未更改。 提示: IDEA警告:javaX:警告:源发行版 需要目标发行版 简略步…...

CCF-CSP认证 2023年12月 2.因子化简
题解: 通过质数筛法,用个板子函数就行了,计算出质数系数就行了 #pragma GCC optimize(2, 3, "Ofast", "inline") #include <bits/stdc.h> #define endl \n using namespace std; long long int num; const int M…...

基于Vue2与3版本的Element UI与Element Plus入门
基于Vue2与3版本的Element UI与Element Plus入门 Element UI 入门安装引入 Element UI使用组件 Element Plus 入门安装引入 Element Plus使用组件 常用组件自定义主题兼容性和升级社区和支持 Element UI 入门 Element UI 是基于 Vue 2.0 的桌面端组件库,它提供了一…...

Mysql数据库创建自增序列
创建序列表 CREATE TABLE sequence (name varchar(50) NOT NULL,current_value bigint(30) NOT NULL,increment int(11) NOT NULL DEFAULT 1 ) ENGINEInnoDB DEFAULT CHARSETutf8 ROW_FORMATDYNAMIC COMMENT序列表;创建函数 查询当前序列名的序列值 CREATE DEFINERroot% FUNC…...

macOS上用Qt creator编译并跑shotcut
1 简介 Shotcut是一个开源的跨平台的视频编辑软件,支持WIN/MACOS/LINUX等平台,由于该项目的编译较为麻烦,踩坑几许,因此写此文章记录完整编译构建过程,后续按此法编译,可减少走弯路,提高生产力。…...