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

                                    🌹个人主页🌹：喜欢草莓熊的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.rhkb.cn/news/371246.html

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

相关文章

通信协议_C#实现自定义ModbusRTU主站

通信协议_C#实现自定义ModbusRTU主站

背景知识&#xff1a;modbus协议介绍 相关工具 mbslave:充当从站。虚拟串口工具:虚拟出一对串口。VS2022。 实现过程以及Demo 打开虚拟串口工具: 打开mbslave: 此处从站连接COM1口。 Demo实现 创建DLL库&#xff0c;创建ModbusRTU类,进行实现&#xff1a; using Syste…
阅读更多...
【JVM-04】线上CPU100%

【JVM-04】线上CPU100%

【JVM-04】线上CPU100% 1. 如何排查2. 再举一个例子 1. 如何排查 ⼀般CPU100%疯狂GC&#xff0c;都是死循环的锅&#xff0c;那怎么排查呢&#xff1f;先进服务器&#xff0c;⽤top -c 命令找出当前进程的运⾏列表按⼀下 P 可以按照CPU使⽤率进⾏排序显示Java进程 PID 为 2609…
阅读更多...
轻松驾驭开发之旅：Maven配置阿里云CodeUp远程私有仓库全攻略

轻松驾驭开发之旅：Maven配置阿里云CodeUp远程私有仓库全攻略

文章目录 引言一、为什么选择阿里云CodeUp作为远程私有仓库&#xff1f;二、Maven配置阿里云CodeUp远程私有仓库的步骤准备工作配置Maven的settings.xml文件配置项目的pom.xml文件验证配置是否成功 三、使用阿里云CodeUp远程私有仓库的注意事项 引言 在软件开发的世界里&#…
阅读更多...
Golang | Leetcode Golang题解之第214题最短回文串

Golang | Leetcode Golang题解之第214题最短回文串

题目&#xff1a; 题解&#xff1a; func shortestPalindrome(s string) string {n : len(s)fail : make([]int, n)for i : 0; i < n; i {fail[i] -1}for i : 1; i < n; i {j : fail[i - 1]for j ! -1 && s[j 1] ! s[i] {j fail[j]}if s[j 1] s[i] {fail[i…
阅读更多...
uni-appx，实现登录功能，弹窗功能。组件之间传值

uni-appx，实现登录功能，弹窗功能。组件之间传值

这篇文章的内容使用组合式API实现的&#xff0c;只有弹窗部分有选择式API的写法介绍。如果想要看其他选择式API&#xff0c;还请下载官方的hello-uni-appx源码进行学习&#xff0c;查看。想要看组合式API的写法&#xff0c;请查看源码 hello-uvue。 hello-uni-appx源码 相比于…
阅读更多...
MybatisX插件的简单使用教程

MybatisX插件的简单使用教程

搜索mybatis 开始生成 module path&#xff1a;当前项目 base package:生成的包名&#xff0c;建议先独立生成一个&#xff0c;和你原本的项目分开 encoding&#xff1a;编码&#xff0c;建议UTF-8 class name strategy&#xff1a;命名选择 推荐选择camel&#xff1a;驼峰命…
阅读更多...
PD虚拟机不能复制Mac的文件怎么回事 PD虚拟机不能复制Mac的文件怎么办 Parallels Desktop怎么用

PD虚拟机不能复制Mac的文件怎么回事 PD虚拟机不能复制Mac的文件怎么办 Parallels Desktop怎么用

PD虚拟机不仅能提供跨系统协作的服务&#xff0c;还能进行虚拟机系统与原生系统间的文件共享、文本复制、文件复制等操作&#xff0c;让系统间的资源可以科学利用。但在实际操作过程中&#xff0c;PD虚拟机不能复制Mac的文件怎么回事&#xff1f;PD虚拟机不能复制Mac的文件怎么…
阅读更多...
Java项目：基于SSM框架实现的共享客栈管理系统分前后台【ssm+B/S架构+源码+数据库+毕业论文】

Java项目：基于SSM框架实现的共享客栈管理系统分前后台【ssm+B/S架构+源码+数据库+毕业论文】

一、项目简介 本项目是一套基于SSM框架实现的共享客栈管理系统 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能完善、界面美观、操作简单、功能…
阅读更多...
CosyVoice - 阿里最新开源语音克隆、文本转语音项目 支持情感控制及粤语 本地一键整合包下载

CosyVoice - 阿里最新开源语音克隆、文本转语音项目 支持情感控制及粤语 本地一键整合包下载

近日&#xff0c;阿里通义实验室发布开源语音大模型项目FunAudioLLM&#xff0c;而且一次包含两个模型&#xff1a;SenseVoice和CosyVoice。 CosyVoice专注自然语音生成&#xff0c;支持多语言、音色和情感控制&#xff0c;支持中英日粤韩5种语言的生成&#xff0c;效果显著优于…
阅读更多...
【JavaSE复习】数据结构、集合

【JavaSE复习】数据结构、集合

JavaSE 复习 1.数据结构1.1 查找1.1.1 基本查找1.1.2 二分查找1.1.3 插值查找1.1.4 斐波那契查找1.1.5 分块查找1.1.6 分块查找的扩展&#xff08;无规律数据&#xff09; 1.2 排序1.2.1 冒泡排序1.2.2 选择排序1.2.3 插入排序1.2.4 快速排序 2. 集合2.1 基础集合2.1.1 集合和数…
阅读更多...
53-1 内网代理3 - Netsh端口转发（推荐）

53-1 内网代理3 - Netsh端口转发（推荐）

靶场还是用上一篇文章搭建的靶场 ：52-5 内网代理2 - LCX端口转发（不推荐使用LCX）-CSDN博客 一、Netsh 实现端口转发 Netsh是Windows自带的命令行脚本工具，可用于配置端口转发。在一个典型的场景中，如果我们位于公网无法直接访问内网的Web服务器，可以利用中间的跳板机通过…
阅读更多...
设计模式探索：责任链模式

设计模式探索：责任链模式

1. 什么是责任链模式 责任链模式 (Chain of Responsibility Pattern) 是一种行为型设计模式。定义如下&#xff1a; 避免将一个请求的发送者与接收者耦合在一起&#xff0c;让多个对象都有机会处理请求。将接收请求的对象连接成一条链&#xff0c;并且沿着这条链传递请求&…
阅读更多...
【Linux进阶】文件系统6——理解文件操作

【Linux进阶】文件系统6——理解文件操作

目录 1.文件的读取 1.1.目录 1.2.文件 1.3.目录树读取 1.4.文件系统大小与磁盘读取性能 2.增添文件 2.1.数据的不一致&#xff08;Inconsistent&#xff09;状态 2.2.日志式文件系统&#xff08;Journaling filesystem&#xff09; 3.Linux文件系统的运行 4、文件的删…
阅读更多...
【YOLOv9教程】如何使用YOLOv9进行图像与视频检测

【YOLOv9教程】如何使用YOLOv9进行图像与视频检测

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…
阅读更多...
14-40 剑和诗人14 - 为什么机器学习需要合成数据

14-40 剑和诗人14 - 为什么机器学习需要合成数据

​​​​​​ 数据是人工智能的命脉。如果没有高质量、有代表性的训练数据&#xff0c;我们的机器学习模型将毫无用处。但随着神经网络规模越来越大、人工智能项目越来越雄心勃勃&#xff0c;人们对数据的需求也越来越大&#xff0c;我们面临着一场危机——现实世界的数据收集和…
阅读更多...
字符串和正则表达式踩坑

字符串和正则表达式踩坑

// 中石化加油卡号格式&#xff1a;以 100011 开头共19位public static final String ZHONGSHIYOU_OIL_CARD_PATTERN "^100011\\d{13}$";// 中石油加油卡号格式&#xff1a;以90、95、70开头共16位public static final String ZHONGYOU_OIL_CARD_PATTERN "^(9…
阅读更多...
Ubuntu20.04 有线网络图标消失解决方案

Ubuntu20.04 有线网络图标消失解决方案

Ubuntu20.04 有线网络图标消失解决方案 问题描述&#xff1a; ubuntu20.04系统提示的software updater有软件包更新&#xff0c;按提示安装更新软件包&#xff0c;重启系统后&#xff0c;ubuntu系统的网络图标消失不见&#xff1b;无法正常上网&#xff1b;检查网口&#xff0…
阅读更多...
【SpringCloud应用框架】Nacos集群架构说明

【SpringCloud应用框架】Nacos集群架构说明

第六章 Spring Cloud Alibaba Nacos之集群架构说明 文章目录 前言一、Nacos支持三种部署模式二、集群部署说明三、预备环境 前言 到目前为止&#xff0c;已经完成了对Nacos的一些基本使用和配置&#xff0c;接下来还需要了解一个非常重要的点&#xff0c;就是Nacos的集群相关的…
阅读更多...
有一个日期（Date）类的对象和一个时间（Time）类的对象，均已指定了内容，要求一次输出其中的日期和时间

有一个日期（Date）类的对象和一个时间（Time）类的对象，均已指定了内容，要求一次输出其中的日期和时间

可以使用友元成员函数。在本例中除了介绍有关友元成员函数的简单应用外&#xff0c;还将用到类的提前引用声明&#xff0c;请读者注意。编写程序&#xff1a; 运行结果&#xff1a; 程序分析&#xff1a; 在一般情况下&#xff0c;两个不同的类是互不相干的。display函…
阅读更多...
【Rust入门】生成随机数

【Rust入门】生成随机数

文章目录 前言随机数库rand添加rand库到我们的工程生成一个随机数示例代码 总结 前言 在编程中&#xff0c;生成随机数是一种常见的需求&#xff0c;无论是用于数据分析、游戏开发还是模拟实验。Rust提供了强大的库来帮助我们生成随机数。在这篇文章中&#xff0c;我们将通过一…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023