数据结构第八弹---队列

队列

  • 1、队列的概念和结构
  • 2、队列的实现
    • 2.1、头文件包含和结构定义
    • 2.2、初始化
    • 2.3、销毁
    • 2.4、判断是否为空
    • 2.5、入队
    • 2.6、出队
    • 2.7、获取队头数据
    • 2.8、获取队尾数据
    • 2.9、获取有效数据个数
  • 3、代码汇总
  • 总结

1、队列的概念和结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性
表，队列具有先进先出FIFO(First In First Out) 的原则。

入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头。
在这里插入图片描述
如何实现队列？
队列是一种一端插入一端删除的数据结构，所以最好的实现方式是头删尾插效率高或者头插尾删效率高。

1.数组实现：尾插和尾删效率较高，不太适合。
2.单链表实现：头删尾插效率较高，链表头删，链表尾插。
前面单链表提到尾插之前需要找到尾结点，为什么此处又说尾插效率高呢？
因为我们可以在定义结构的时候创建一个记录尾结点的变量，这样我们每次尾插的时候就不需要找尾结点了。
3.双向链表实现：头插头删尾插尾删效率都较高，可以实现队列。
双向链表头插头删尾插尾删效率都较高，为什么此处不直接使用双向链表实现呢？
因为单链表就能很好的实现一个队列，而双向链表相较与单链表会多开辟一个结点，在空间方面会有更多的消耗，所以一般不推荐使用双向链表实现队列。

2、队列的实现

经过上述的分析，我们推荐使用单链表实现队列，那么接下来就由博主来实现一下队列。
在这里插入图片描述
首先创建一个工程。(下图为vs 2022)
在这里插入图片描述
Queue.h（队列的类型定义、接口函数声明、引用的头文件）
Queue.c（队列接口函数的实现）
test.c （主函数、测试顺序表各个接口功能）

2.1、头文件包含和结构定义

以下是实现队列可能用到的头文件。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

以下是博主创建的队列结构，可以根据自己的喜好创建喔。
建议：创建结构时最好能通俗易懂，最好不用拼音创建。
在这里插入图片描述

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next; //存放下一个结点指针
	QDataType data;         //存放数据
}QueueNode;

typedef struct Queue
{
	QueueNode* head;//头结点
	QueueNode* tail;//尾结点
}Queue;

2.2、初始化

链表的结构是通过动态开辟的空间，可以先不初始化。但是队列的结构是在栈区开辟的，为了防止越界访问，需要先初始化为NULL。

void QueueInit(Queue* pq)
{
	assert(pq);//防止空指针传入
	pq->head = pq->tail = NULL;//初始化为空指针，防止野指针问题
}

2.3、销毁

队列是通过动态开辟的内存，需要手动释放，即依次遍历将结点空间释放，并手动置空。
思想：定义一个变量用来找结点，不为空则释放然后找下一个结点，为空则结束。

在这里插入图片描述

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;//养成创建变量习惯，为了后面能找到头结点
	while (cur)
	{
		QueueNode* next = cur->next;//标记下一个结点
		free(cur);
		cur = next;//更新结点
	}
	pq->head = pq->tail = NULL;//释放完手动置NULL
}

2.4、判断是否为空

根据队列的初始化函数可知，在创建之前会将头结点置空，所以头结点为空则队列为空。

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;//头结点为空则返回真
}

测试
在这里插入图片描述

2.5、入队

入队：即在队尾处插入数据。

画图分析如下
在这里插入图片描述
代码实现

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)//动态开辟后记得判断喔！
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)//没有数据情况
	{
		pq->head = pq->tail = newnode;//将新结点赋值给头尾结点
	}
	else//有数据情况
	{
		pq->tail->next = newnode;//尾结点下一个插入数据
		pq->tail = newnode;//将尾结点更新
	}
}

测试
在这里插入图片描述

2.6、出队

出队：即在队头位置删除数据。
前提：有数据才能出队

在这里插入图片描述
代码实现

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);//确保有数据
	//一个元素
	if (pq->head->next == NULL)
	{
		free(pq->head);//释放空间
		pq->head = pq->tail = NULL;//手动置空
	}
	//多个元素
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);//释放空间
		pq->head = next;//更新头结点
	}
}

测试
在这里插入图片描述

队头元素就是头结点中存储的数据

2.7、获取队头数据

队头数据：即头结点数据。

代码实现

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

测试
在这里插入图片描述

2.8、获取队尾数据

队尾元素就是队尾结点的数据

代码实现

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}

测试
在这里插入图片描述

将队列遍历一遍，计算大小

2.9、获取有效数据个数

有效数据个数：即有效结点个数。
思想：从头结点开始计算，不为空则size++，然后更新到下一个结点，为空则结束。

代码实现

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

测试
在这里插入图片描述

3、代码汇总

以下是Queue.h的代码。

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>


typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;//头结点
	QueueNode* tail;//尾结点
}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);

以下是Queue.c的代码

#define _CRT_SECURE_NO_WARNINGS

#include "Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("QueueNode fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

总结

本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

给定0-1数组，找出连续1最长和次最长的2个子数组的起始位置和结束位置。

给定0-1数组，找出连续1最长和次最长的2个子数组的起始位置和结束位置。

题目 给定0-1数组&#xff0c;找出连续1最长和次最长的2个子数组的起始位置和结束位置。 要求&#xff1a; 子数组长度大于等于1。 如果有多个子数组满足条件&#xff0c;按照数组下标由小到大只输出满足条件的前2个数组的起始位置和结束位置&#xff0c; 如果只有1个满足&…
阅读更多...
Multisim各版本安装指南

Multisim各版本安装指南

Multisim下载链接 https://pan.baidu.com/s/1En9uUKafhGOqo57V5rY9dA?pwd0531 1.鼠标右击【Multisim 14.3(64bit)】压缩包&#xff08;win11及以上统需先点击“显示更多选项”&#xff09;选择【解压到 Multisim 14.3(64bit)】。 2.打开解压后的文件夹&#xff0c;双击打开【…
阅读更多...
深度学习中的知识蒸馏

深度学习中的知识蒸馏

一.概念 知识蒸馏&#xff08;Knowledge Distillation&#xff09;是一种深度学习中的模型压缩技术&#xff0c;旨在通过从一个教师模型&#xff08;teacher model&#xff09;向一个学生模型&#xff08;student model&#xff09;传递知识来减小模型的规模&#xff0c;同时保…
阅读更多...
UAV | 多算法在多场景下的无人机路径规划(Matlab)

UAV | 多算法在多场景下的无人机路径规划(Matlab)

近年来&#xff0c;无人机(unmanned aerial vehicle&#xff0c;UAV)由于其灵活度高、机动性强、安全风险系数小、成本低等特点&#xff0c;被广泛应用于搜索巡逻、侦察监视、抢险救灾、物流配送、电力巡检、农业灌溉等军用或民用任务。路径规划是无人机执行任务的关键&#xf…
阅读更多...
C# Attribute特性实战(1):Swtich判断优化

C# Attribute特性实战(1):Swtich判断优化

文章目录 前言简单Switch问题无参Swtich方法声明Swtich Attribute声明带有Swtich特性方法主方法结果 有参Switch修改代码修改运行过程运行结果 总结 前言 在经过前面两章内容的讲解&#xff0c;我们已经简单了解了如何使用特性和反射。我们这里解决一个简单的案例 C#高级语法 …
阅读更多...
Spring依赖注入的魔法：深入DI的实现原理【beans 五】

Spring依赖注入的魔法：深入DI的实现原理【beans 五】

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 Spring依赖注入的魔法&#xff1a;深入DI的实现原理【beans 五】 前言DI的基本概念基本概念&#xff1a;为什么使用依赖注入&#xff1a; 构造器注入构造器注入的基本概念&#xff1a;示例&#xff1a…
阅读更多...
RK3568 学习笔记 : 解决 linux_sdk 编译 python 版本报错问题

RK3568 学习笔记 : 解决 linux_sdk 编译 python 版本报错问题

前言 最近买了 【正点原子】 的 RK3568 开发板&#xff0c;下载了 开发板的资料&#xff0c;包括 Linux SDK&#xff0c;这个 Linux SDK 占用的空间比较大&#xff0c;扩展了一下 VM 虚拟机 ubuntu 20.04 的硬盘空间&#xff0c;编译才正常通过。 编译 RK3568 Linux SDK 时&am…
阅读更多...
二维地图组件开发

二维地图组件开发

很多的业务项目中&#xff0c;都会用到二维地图&#xff0c;二维地图功能简洁&#xff0c;并且很多在很多的业务中采用&#xff0c;维护难度也比三维地图小一些。而开发二维地图的开源库有QGis&#xff0c; Mapwingis等。 采用mapwingis开发了一个二维地图组件&#xff0c;可以…
阅读更多...
Jmeter事务控制器聚合报告

Jmeter事务控制器聚合报告

Jmeter 事务控制器。 在Jmeter中&#xff0c;默认一个取样器就是一个事务 事务控制器控制其子集取样器&#xff0c;合并为一个事务 添加&#xff1a;逻辑控制器/Logic Controller -> 事务控制器/Transaction Controller TPS: 服务器每秒处理的事务数 在事务控制器下添加多…
阅读更多...
Http与Tcp协议的原理以及应用

Http与Tcp协议的原理以及应用

OSI七层模型和相关协议 七层模型从上到下如下所示&#xff1a; 应用层&#xff1a;负责应用之间的通信&#xff0c;处理请求和响应的具体格式表示层&#xff1a;对于数据格式进行处理会话层&#xff1a;负责建立和断开通信连接&#xff0c;传输层&#xff1a;负责建立端口之间…
阅读更多...
gdal平面几何空间关系

gdal平面几何空间关系

关于平面几何的空间关系判定&#xff0c;gdal提供了8个函数&#xff0c;分别是&#xff1a;Intersects&#xff08;相交&#xff09;&#xff0c;Equals&#xff08;相等&#xff09;&#xff0c;Disjoint&#xff08;不相交&#xff09;&#xff0c;Touches&#xff08;接触&a…
阅读更多...
LeetCode做题总结 15. 三数之和、18. 四数之和 (Java)

LeetCode做题总结 15. 三数之和、18. 四数之和 (Java)

不会做&#xff0c;参考了代码随想录和力扣官方题解&#xff0c;对此题进行整理。 X数之和 15. 三数之和代码思路20240103重写错误1错误2Java语言点总结 18. 四数之和代码思路20240104&#xff08;伪&#xff09;错误1 第一次剪枝错误2 第二次剪枝错误3 溢出 15. 三数之和 代码…
阅读更多...
C#使用纯OpenCvSharp部署yolov8-pose姿态识别

C#使用纯OpenCvSharp部署yolov8-pose姿态识别

【源码地址】 github地址&#xff1a;https://github.com/ultralytics/ultralytics 【算法介绍】 Yolov8-Pose算法是一种基于深度神经网络的目标检测算法&#xff0c;用于对人体姿势进行准确检测。该算法在Yolov8的基础上引入了姿势估计模块&#xff0c;通过联合检测和姿势…
阅读更多...
vue icon 本地正常 线上打包失败变乱码

vue icon 本地正常 线上打包失败变乱码

出现这个原因是因为sass解析的问题 Node版本高的话可以通过升级sass版本 并且配置vue.config规避这个问题 //给sass配置的东西 这个对应的版本是sass 1.39.0 本人node版本v14 升级sass版本后出现报错css: {loaderOptions: {scss: {additionalData: import "/styles/var…
阅读更多...
网络请求 - 异步编程详解

网络请求 - 异步编程详解

一、概述 网络管理模块主要提供以下功能&#xff1a; HTTP数据请求&#xff1a;通过HTTP发起一个数据请求。WebSocket连接&#xff1a;使用WebSocket建立服务器与客户端的双向连接。Socket连接&#xff1a;通过Socket进行数据传输。 HTTP和WebSocket都是啥&#xff1f; 比如我…
阅读更多...
速记计算机网络传输介质分类

速记计算机网络传输介质分类

计算机网络中的传输介质是指用于在不同设备之间传递数据的物理媒介。传输介质的选择对于网络的性能和可靠性至关重要。在计算机网络中&#xff0c;常见的传输介质可以分为有线传输介质和无线传输介质两类。本文将对这两类传输介质进行详细的分类和介绍。 一、有线传输介质 有…
阅读更多...
外包干了4个月，技术退步明显了...

外包干了4个月，技术退步明显了...

先说一下自己的情况&#xff0c;大专生&#xff0c;18年通过校招进入武汉某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落&#xff01; 而我已经在一个企业干了四…
阅读更多...
[C]jupyter中使用C

[C]jupyter中使用C

[C]jupyter中使用C 安装使用用处 安装 https://github.com/brendan-rius/jupyter-c-kernel 下拉找到3条命令&#xff0c;装就可以了 mac和linux可用 python3可用&#xff0c; 2不可以 第二条命令可以改为 : python3 install_c_kernel 小总结&#xff1a;如果有问题&#xff0…
阅读更多...
Merge还是Rebase？这次终于懂了

Merge还是Rebase？这次终于懂了

《Git分支管理&#xff1a;Merge还是Rebase&#xff1f;》 导语&#xff1a; 在Git的分支管理中&#xff0c;Merge和Rebase是两种常见的合并策略&#xff0c;每一种都有其优劣之处。究竟应该选择Merge还是Rebase&#xff0c;取决于项目的需求和团队的工作流程。本文将深入探讨…
阅读更多...
echarts 仪表盘进度条 相关配置

echarts 仪表盘进度条 相关配置

option {series: [{type: gauge,min: 0,//最大值max: 100, //最小值startAngle: 200,//仪表盘起始角度。圆心 正右手侧为0度&#xff0c;正上方为90度&#xff0c;正左手侧为180度。endAngle: -20,//仪表盘结束角度splitNumber: 100, //仪表盘刻度的分割段数itemStyle: {color…
阅读更多...
最新文章

Copyright @ 2022~2023