数据结构之“队列”（全方位认识）

                                    🌹个人主页🌹：喜欢草莓熊的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;
}

总结

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

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

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

相关文章

【无标题】ubuntu的安装和登录

【无标题】ubuntu的安装和登录

1.安装ubuntu系统并允许root用户登录 一、安装ubuntu分为以下几个步骤&#xff1a; a、在官方网站下载镜像&#xff1a;https://ubuntu.com/ b、选择安装模式为&#xff1a;Try or install Ubuntu &#xff08;体验或安装&#xff09; c、选择体验系统或安装系统&#xff1a…
阅读更多...
ComfyUI预处理器ControlNet简单介绍与使用（附件工作流）

ComfyUI预处理器ControlNet简单介绍与使用（附件工作流）

简介 ControlNet 是一个很强的插件&#xff0c;提供了很多种图片的控制方式&#xff0c;有的可以控制画面的结构&#xff0c;有的可以控制人物的姿势&#xff0c;还有的可以控制图片的画风&#xff0c;这对于提高AI绘画的质量特别有用。接下来就演示几种热门常用的控制方式 1…
阅读更多...
RAG理论：ES混合搜索BM25+kNN(cosine)以及归一化

RAG理论：ES混合搜索BM25+kNN(cosine)以及归一化

接前一篇:RAG实践：ES混合搜索BM25+kNN(cosine) https://blog.csdn.net/Xin_101/article/details/140230948 本文主要讲解混合搜索相关理论以及计算推导过程， 包括BM25、kNN以及ES中使用混合搜索分数计算过程。 详细讲解： （1）ES中如何通过BM25计算关键词搜索分数； （2）…
阅读更多...
【手写数据库内核组件】0201 哈希表hashtable的实战演练，多种非加密算法，hash桶的冲突处理，查找插入删除操作的代码实现

【手写数据库内核组件】0201 哈希表hashtable的实战演练，多种非加密算法，hash桶的冲突处理，查找插入删除操作的代码实现

hash表原理与实战 ​专栏内容&#xff1a; postgresql使用入门基础手写数据库toadb并发编程 个人主页&#xff1a;我的主页 管理社区&#xff1a;开源数据库 座右铭&#xff1a;天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物. 文章目录 hash表…
阅读更多...
下载linux的吐槽

下载linux的吐槽

本来这几天放假了&#xff0c;想下一个linux玩一玩 教程&#xff08;我就是根据这个教程进行下载的&#xff0c;但是呢在进行修改BIOS 模式的 地方遇见了困难&#xff0c;也许是电脑修过的原因&#xff0c;我狂按F12 以及 FnF12都没有BIOS设置&#xff0c;只有一个让我选择用w…
阅读更多...
第二次练习

第二次练习

目录 一、student表的增删改查 1.向student表中添加一条新记录 2. 向student表中添加多条新记录 3.向student表中添加一条新记录 4.更新表&#xff0c;grade 大于90的加0.5 5.删除成绩为空的记录 二、用户权限部分 1、创建一个用户test1使他只能本地登录拥有查询student表的权…
阅读更多...
6、Redis系统-数据结构-05-整数

6、Redis系统-数据结构-05-整数

五、整数集合&#xff08;Intset&#xff09; 整数集合是 Redis 中 Set 对象的底层实现之一。当一个 Set 对象只包含整数值元素&#xff0c;并且元素数量不大时&#xff0c;就会使用整数集合这个数据结构作为底层实现。整数集合通过紧凑的内存布局和升级机制&#xff0c;实现了…
阅读更多...
NSSCTF-Web题目24(RCE-空格绕过、过滤绕过)

NSSCTF-Web题目24(RCE-空格绕过、过滤绕过)

目录 [MoeCTF 2021]babyRCE 1、题目 2、知识点 3、思路 [SWPUCTF 2022 新生赛]funny_web 4、题目 5、知识点 6、思路 [MoeCTF 2021]babyRCE 1、题目 2、知识点 空格绕过、过滤绕过 3、思路 出现源码&#xff0c;进行代码审计 需要我们GET方式上传一个rce变量&#x…
阅读更多...
针对tcp不出网打——HTTP隧道代理（以CFS演示）

针对tcp不出网打——HTTP隧道代理（以CFS演示）

目录 上传工具到攻击机 使用说明 生成后门文件 由于电脑短路无法拖动文件&#xff0c;我就wget发送到目标主机tunnel.php文件​ 成功上传​ 可以访问上传的文件 启动代理监听 成功带出 后台私信获取弹药库工具reGeorg 上传工具到攻击机 使用说明 生成后门文件 pyt…
阅读更多...
分班结果老师怎么发给家长？

分班结果老师怎么发给家长？

分班结果老师怎么发给家长&#xff1f; 随着新学期的脚步渐近&#xff0c;老师们的工作也变得愈发繁忙。从准备教学计划到整理课程材料&#xff0c;每一项任务都不容小觑。而其中&#xff0c;分班结果的告知工作&#xff0c;更是让不少老师头疼不已。传统的分班通知方式&#…
阅读更多...
fork创建子进程详解

fork创建子进程详解

一.前言 在上一篇文章-进程的概念&#xff0c;最后我们提到了创建进程的方式有两种方式&#xff0c;一种是手动的创建出进程&#xff0c;还有一种就是我们今天要学习的使用代码的方式创建出子进程-fork。 而学习fork创建出进程的过程中&#xff0c;我们会遇到以下问题&#x…
阅读更多...
STL——map和set

STL——map和set

目录 一、set 二、map 1.插入 2.隆重介绍 [] A使用场景 B原理 一、set set即STL库中提供的K模型的二叉搜索树&#xff0c;他的函数使用和其他容器很相似&#xff0c;可以自行阅读文档#include <set> 本文旨对库中难以理解的函数作说明 二、map map即KV模型的二…
阅读更多...
触底加载的两种思路(以vue3前端和nodejs后端为例)

触底加载的两种思路(以vue3前端和nodejs后端为例)

一:首先,nodejs后端的代码都是一样的. 需要前端返回page参数,然后nodejs逻辑进行处理,截取页数和每页条数和总条数, 总条数用来作为判断是否有数据的条件,也可以不用,注意看下文 一:不用获取容器高度的. pinia中进行的axios请求处理 在vue文件中进行pinia中数据的导入,继续进…
阅读更多...
全面解析 TypeScript 泛型的二三事

全面解析 TypeScript 泛型的二三事

2024年了相信大家都已经在日常开发的过程中使用上了 TypeScript 了。TypeScript 增强了代码可靠性和可维护性&#xff0c;确保减少运行时错误并提高开发人员的工作效率。 TypeScript 通过类型声明 使得 javascript 拥有了强类型校验。而泛型的是类型声明中最重要的一环&#x…
阅读更多...
Nettyの源码分析

Nettyの源码分析

本篇为Netty系列的最后一篇&#xff0c;按照惯例会简单介绍一些Netty相关核心源码。 1、Netty启动源码分析 代码就使用最初的Netty服务器案例&#xff0c;在bind这一行打上断点&#xff0c;观察启动的全过程&#xff1a; 由于某些方法的调用链过深&#xff0c;节约篇幅&#xf…
阅读更多...
Linux内核链表使用方法

Linux内核链表使用方法

简介&#xff1a; 链表是linux内核中最简单&#xff0c;同时也是应用最广泛的数据结构。内核中定义的是双向链表。 linux的链表不是将用户数据保存在链表节点中&#xff0c;而是将链表节点保存在用户数据中。linux的链表节点只有2个指针(pre和next)&#xff0c;这样的话&#x…
阅读更多...
在Linux操作系统使用逻辑卷的快照（snapshot），进行对逻辑卷的数据备份。

在Linux操作系统使用逻辑卷的快照（snapshot），进行对逻辑卷的数据备份。

作用&#xff1a;结合特定应用程序&#xff0c;方便备份数据。 基于cow&#xff08;copy on write 写时复制&#xff09;机制 在创建逻辑卷快照的时候&#xff0c;如果不去设置逻辑卷快照的权限的话&#xff0c;那么这个逻辑卷的权限就是可读可写&#xff0c; 创建逻辑卷快照…
阅读更多...
coco数据集格式计算mAP的python脚本

coco数据集格式计算mAP的python脚本

目录 背景说明COCOeval 计算mAPtxt文件转换为coco json 格式自定义数据集标注 背景说明 在完成YOLOv5模型移植&#xff0c;运行在板端后&#xff0c;通常需要衡量板端运行的mAP。 一般需要两个步骤 步骤一&#xff1a;在板端批量运行得到目标检测结果&#xff0c;可保存为yol…
阅读更多...
AI教你如何系统的学习Python

AI教你如何系统的学习Python

Python学习计划 第一阶段&#xff1a;Python基础&#xff08;1-2个月&#xff09; 目标&#xff1a;掌握Python的基本语法、数据类型、控制结构、函数、模块和包等。 学习Python基本语法&#xff1a;包括变量、数据类型&#xff08;整数、浮点数、字符串、列表、元组、字典、…
阅读更多...
STM32基础篇：GPIO

STM32基础篇：GPIO

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

Copyright @ 2022~2023