【数据结构初阶(5)】链式队列的基本操作实现

文章目录

  • 队列的定义
  • 初始化队列
  • 队尾入队列
  • 队头出队列
  • 取队头元素
  • 取队尾元素
  • 获取队列有效元素个数
  • 判断队空
  • 销毁队列

因为队列比较简单,关于队列的概念就不过多赘述了,本文只讲链队的基本操作实现

队列的定义

定义队列结点结构

  • 链队中的每个结点都应该包含一个数据域用来存储数据,以及一个指针域用来存储下一个结点的地址。
typedef int QDataType;//对列中每个结点的结构
typedef struct QListNode
{QDataType data;				//数据域struct QListNode* next;		//指针域
}QNode;

定义队列

  • 一个正常的队列应该有一个队头指针和一个队尾指针分别用来指向队列的头和尾。
  • 除此之外,还需要一个变量用来表示当前队列有效数据的个数。
// 队列的结构 
typedef struct Queue
{int size;		//元素个数QNode* head;	//队头指针QNode* tail;	//队尾指针
}Queue;

初始化队列

  • 在队列内没有任何元素时,队头和队尾指针都应该指向空,元素个数也置为 0。
// 初始化队列 
void QueueInit(Queue* q)
{assert(q);q->head = q->tail = NULL;	//队头尾指针都置空q->size = 0;				//队内元素个数置空
}

队尾入队列

链队在入队时有两种情况

  1. 队列内无元素:同时让队头和队尾指针指向新结点。
  2. 队列内有元素:让队尾结点的指针域存储新结点的地址,将新插入的结点更新为尾结点。

在这里插入图片描述

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{assert(q);//创建新结点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (NULL == newnode){perror("malloc");exit(-1);}newnode->data = data;				//将数据插入新结点数据域newnode->next = NULL;				//将新结点指针域置空if (NULL == q->tail)				//当前队列没有结点{q->head = q->tail = newnode;	//队头队尾的指针域同时指针新结点}else								//当前队列中有结点{q->tail->next = newnode;		//队尾结点指针域指向新结点q->tail = newnode;				//将插入的结点更新为尾结点}q->size++;							//队列内有效元素个数 + 1
}

队头出队列

队头出队列就是删除队头元素,在删除队头元素时有两种情况。

  1. 删除的是最后一个元素:删除该结点时头指针会往后走到 NULL 的位置,此时必须也将队尾指针也置空,否则队尾指针就成野指针了。

在这里插入图片描述

  1. 删除的非最后一个元素:保存队头的地址,然后将队头指针指向下一个结点,最后释放队头。

在这里插入图片描述

// 队头出队列 
void QueuePop(Queue* q)
{assert(q);assert(q->head);			//队列不为空QNode* delete = q->head;	//保存要删除的队头结点的地址q->head = q->head->next;	//头指针走向下一个结点free(delete);				//删除队头结点delete = NULL;	if (NULL == q->head)		//前面删除的是最后一个元素{q->tail = NULL;			//尾指针也置空}q->size--;					//队内元有效元素个数 -1
}

取队头元素

  • 在队列非空时,直接返回队头结点数据域内的数据即可。
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(q);assert(q->head);return q->head->data;	//返回队头结点的数据域内容
}

取队尾元素

  • 在队列非空时,直接返回队尾结点数据域内的数据即可。
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(q);assert(q->tail);		//队列不为空return q->tail->data;	//返回队尾结点的数据域内容
}

获取队列有效元素个数

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{assert(q);return q->size;
}

判断队空

  • 检测队列是否为空,如果为空返回非零结果,如果非空返回 0 。
int QueueEmpty(Queue* q)
{assert(q);return 0 == q->size;	//表达式成立则结果为真,反之为假
}

销毁队列

  • 和单链表的销毁相同,利用一个指针 cur 保存当前要删除结点的地址,再定义一个 next 指针指向下一个要删除的结点。
  • 重复上述直到 cur 指向空为止,此时表示队列内的所有结点已经销毁完毕。

// 销毁队列 
void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->head;			//cur 先指向队头while (NULL != cur){QNode* next = cur->next;	//保存下一个结点free(cur);					//删除当前结点cur = next;					//指向下一个结点}q->head = q->tail = NULL;		//队头尾指针都置空q->size = 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/209388.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

hutool的bug之 DateUtil.endOfDay(DateUtil.date())

hutool 工具类DateUtil 使用时谨慎 DateUtil.endOfDay 得到的时间保存到数据时会增加一秒 首先比较下时间的long值: 这样就很明显的看出来,hutool工具类的date是毫秒位多了.999,保存到mysql 的时候,MySQL数据库对于毫秒大于500的数据进行…

算法通关村第十六关-白银挑战滑动窗口经典题目

大家好我是苏麟 , 今天带来滑动窗口经典的一些题目 . 我们继续来研究一些热门的、高频的滑动窗口问题 大纲 最长子串专题无重复字符的最长子串 长度最小的子数组盛最多水的容器 最长子串专题 无重复字符的最长子串 描述 : 给定一个字符串 s ,请你找出其中不含有重…

贸易公司ERP用什么软件好

不同行业的贸易公司有不同的业务结构和管理模式,日常经营管理过程中遇到的难点呈现多样化,而很多贸易公司在仓库、财务、销售、采购、订单、客户等业务一体化和部门协同效率等方面还有很多提升空间。 有些贸易公司涉及多仓库、多门店、多税制、多汇率、…

如何绕过某讯手游保护系统并从内存中获取Unity3D引擎的Dll文件

​ 某讯的手游保护系统用的都是一套,在其官宣的手游加固功能中有一项宣传是对比较热门的Unity3d引擎的手游保护方案,其中对Dll文件的保护介绍如下, “Dll加固混淆针对Unity游戏,对Dll模块的变量名、函数名、类名进行加密混淆处理&…

CSS实现小球边界碰撞回弹

如何通过CSS实现一个物体在屏幕中无限的边界碰撞回弹呢?我们可以使用动画效果实现 代码 我们只做一个小球,通过定位属性叠加动画的方式, 让小球在屏幕中进行运动,通过设置animation的alternate属性来设置回弹。最后,只…

笔记-基于CH579M模块通过网线直连电脑进行数据收发(无需网络)

刚学习,做个记录。 基于CH579M模块通过网线直连电脑进行数据收发(无需网络) 目录 一、工具1、CH579模块2、 网线3、电脑以及网络调试工具 二、操作步骤1、TCP/UDP等程序下载以及设置以太网IP2、网络断开3、检查以太网是否正常显示并稳定4、打开网络调试助手进行测试…

电气间隙和爬电距离的算法

电气间隙和爬电距离 一、定义 1、电气间隙:不同电位的两个导电部件间最短的空间直线距离。 2、爬电距离:不同电位的两个导电部件之间沿绝缘材料表面的最短距离。 3、隔离距离(机械式开关电器一个极的):满足对隔离器…

音频处理关键知识点

1 引言 现实生活中,我们听到的声音都是时间连续的,我们称为这种信号叫模拟信号。模拟信号需要进行数字化以后才能在计算机中使用。 目前我们在计算机上进行音频播放都需要依赖于音频文件。音频文件的生成过程是将声音信息采样、量化和编码产生的数字信号…

echarts笔记-GeoJSON河北数据下并裁剪为冀北地图并使用echarts加载

首先找个网站把河北的GeoJSON数据下载下来,我用的是这个,理论上任意一个都可以 DataV.GeoAtlas地理小工具系列 将json数据下载后,进行裁剪,仅保留冀北数据。 如下,我裁剪的数据: {"type": &qu…

Python练习题(四)

本文主要是【Python】——Python练习题的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是听风与他🥇 ☁️博客首页:CSDN主页听风与他 🌄每日一句:狠狠沉淀&a…

ssm医院门诊互联电子病历管理信息系统源码和论文

摘 要 网络的广泛应用给生活带来了十分的便利。所以把医院门诊互联电子病历管理与现在网络相结合,利用java技术建设医院门诊互联电子病历管理信息系统,实现医院门诊互联电子病历的信息化。则对于进一步提高医院门诊互联电子病历管理发展,对…

最强Node js 后端框架学习看这一篇文章就够

距离上次认真花时间写作,似乎已经过了许久许久,前端讲了一个新框架 ,叫 Nest.js 下方是课件,有过一定开发经验可跟随视频学习 B站 地址 : https://www.bilibili.com/video/BV1Lg4y197u1/?vd_sourcead427ffaf8a5c8344…

leetcode 202.快乐数

代码: class Solution {//计算 n 每个位置上的数字的平方和public int quadraticSum(int n){int sum0;while (n>0){int in%10;sumi*i;n/10;}return sum;}public boolean isHappy(int n) {//慢指针int slown;//快指针int fastquadraticSum(n);while (slow!fast){…

【EasyExcel实践】万能导出,一个接口导出多张表以及任意字段(可指定字段顺序)

文章目录 前言正文一、POM依赖二、核心Java文件2.1 自定义表头注解 ExcelColumnTitle2.2 自定义标题头的映射接口2.3 自定义有序map存储表内数据2.4 表头工厂2.5 表flag和表头映射枚举2.6 测试用的实体2.6.1 NameAndFactoryDemo2.6.2 StudentDemo 2.7 启动类2.8 测试控制器 三、…

linux作业管理_jobs

4.2 作业管理 是指控制当前正在运行的进程的行为,也称为进程控制。 是shell的一个特性,使用户能在多个独立进程间进行切换。 例如,用户可以挂起一个正在运行的进程,稍后再恢复其运行。当用户使用vim编辑一个文本文件&#xff0c…

PCL 空间直角坐标系与极坐标系的相互转换(C++详细过程版)

目录 一、算法原理1、空间坐标系转极坐标系2、极坐标系转空间坐标系二、代码实现三、结果展示1、空间坐标系转极坐标系2、极坐标系转空间坐标系本文由CSDN点云侠原创,原文链接。爬虫网站自重。如果你不是在点云侠的博客中看到该文章,那么此处便是不

【算法】单调栈题单(矩阵系列、字典序最小、贡献法)⭐

文章目录 题单来源经典题单496. 下一个更大元素 I(单调栈模板题)503. 下一个更大元素 II(单调栈循环数组)2454. 下一个更大元素 IV(第二个更大的元素:两个单调栈)456. 132 模式(单调…

C++ day44完全背包问题 零钱兑换Ⅱ 组合总和Ⅳ

完全背包:一个物品可以使用无数次,将01背包中倒序遍历背包变成正序遍历背包 遍历顺序:在完全背包中,对于一维dp数组来说,其实两个for循环嵌套顺序是无所谓的! 先遍历物品,后遍历背包可以&#…

idea报错——Access denied for user ‘root‘@‘localhost‘ (using password: YES)

项目场景: 使用idea启动SpringBoot项目报错,可以根据提示看到是数据库的原因,显示使用了密码,具体报错信息如下: 解决方案: 第一步:先去配置文件里面查看连接MySQL的url是否正确,如果…

【蓝桥杯选拔赛真题73】Scratch烟花特效 少儿编程scratch图形化编程 蓝桥杯创意编程选拔赛真题解析

目录 scratch烟花特效 一、题目要求 编程实现 二、案例分析 1、角色分析