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

news/2024/10/6 9:10:07/

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

总结

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


http://www.ppmy.cn/news/1473907.html

相关文章

【2024_CUMCM】T检验、F检验、卡方检验

【2024_CUMCM】T检验、F检验、卡方检验

T检验 T检验主要用于比较两组数据的均值差异&#xff0c;适用于小样本数据分析。它可以分为单样本T检验、独立样本T检验和配对样本T检验。 单样本T检验用于比较一个样本与已知的总体均值差异&#xff0c;独立样本T检验用于比较两个独立样本的均值差异&#xff0c;配对样本T检…
阅读更多...
比Elasticsearch更高效的开源搜索引擎Meilisearch——筑梦之路

比Elasticsearch更高效的开源搜索引擎Meilisearch——筑梦之路

功能说明 快速与高效&#xff1a; Meilisearch 旨在提供快速的搜索速度。它可以在毫秒级别内返回查询结果&#xff0c;即使在处理大型数据集时也是如此。 例如&#xff0c;在官方提供的基准测试中&#xff0c;使用 Meilisearch 处理 10 万个文档时&#xff0c;平均搜索时间为 …
阅读更多...
Web3 ETF的主要功能

Web3 ETF的主要功能

Web3 ETF的主要功能可以概括为以下几点&#xff0c;Web3 ETF仍是一项新兴投资产品&#xff0c;其长期表现仍存在不确定性。投资者在投资Web3 ETF之前应仔细研究相关风险&#xff0c;并做好充分的风险评估。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xf…
阅读更多...
如何在Spring Boot中实现数据加密

如何在Spring Boot中实现数据加密

如何在Spring Boot中实现数据加密 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01; 一、数据加密的重要性与应用场景 在当今信息安全日益受到重视的背景下&…
阅读更多...
吴恩达深度学习笔记：机器学习策略（2）(ML Strategy (2)) 2.5-2.6

吴恩达深度学习笔记：机器学习策略（2）(ML Strategy (2)) 2.5-2.6

目录 第三门课 结构化机器学习项目&#xff08;Structuring Machine Learning Projects&#xff09;第二周&#xff1a;机器学习策略&#xff08;2&#xff09;(ML Strategy (2))2.5 数据分布不匹配时的偏差与方差的分析&#xff08;Bias and Variance with mismatched data di…
阅读更多...
智能物联网鱼缸

智能物联网鱼缸

硬件部分及接线图 工具 继电器、开发板、物联网os、云平台 微信小程序 结构&#xff1a;images、pages两个为主体。 标题头部分 <view class"container"> <view class"head_box"> <image src"/images/面性鱼缸.png"><…
阅读更多...
01 Docker 概述

01 Docker 概述

目录 1.Docker简介 2.传统虚拟机 vs 容器 3.Docker运行速度快的原因 4.Docker基本组成三要素 5.Docker 平台架构 入门版 架构版 1.Docker简介 Docker是基于Go语言实现的云开源项目。 Docker的主要目标是&#xff1a;Build, Ship and Run Any App, Anywhere&#xff0c…
阅读更多...
如何监控和分析 PostgreSQL 中的查询执行计划？

如何监控和分析 PostgreSQL 中的查询执行计划？

文章目录 一、为什么监控和分析查询执行计划很重要二、PostgreSQL 中用于获取查询执行计划的方法三、理解查询执行计划的关键元素四、通过示例分析查询执行计划五、优化查询执行计划的常见策略六、使用工具辅助分析七、结合实际案例的详细分析八、总结 在 PostgreSQL 数据库中&…
阅读更多...
最新文章

Copyright @ 2022~2023