[数据结构初阶]队列

鼠鼠我呀,今天写一个基于C语言关于队列的博客,如果有兴趣的读者老爷可以抽空看看,很希望的到各位老爷观点和点评捏!

在此今日,也祝各位小姐姐女生节快乐啊,愿笑容依旧灿烂如初阳,勇气与童真永不退色!

目录

1.队列的概念及结构

 2.对列的实现 

2.1.queue.h

2.2.queue.c

2.3.test.c

2.4.定义队列

2.5.初始化队列

2.6.队尾入队列

2.7.对头出队列

2.8.获取队列队头元素

2.9.获取队列队尾元素

2.10.获取队列中有效元素的个数

2.11.检测队列是否为空,如果为空返回非零结果,非空返回0

2.12.销毁队列 

 3.分析运行结果

4.ending


 

1.队列的概念及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列中的数据元素具有先进先出 FIFO(First In First Out) 的特点。

队尾:进行插入操作的一端称为队尾。

对头:进行删除操作的一端称为队头 。

咱们画一个队列的想象图就很好理解上面几个概念:

其实很好理解,队列里面的数据元素就像排队一样,先进入队列的数据元素当然先出队列了。

 2.对列的实现 

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。

而队列用链表实现的方案也是多种多样,只要满足队列的定义即可。鼠鼠我今天写一个方案(本方案基于无头单向非循环链表)各位佬们可以看看啊,俺先把三个文件和运行结果呈现如下:

2.1.queue.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int QDatatype;typedef struct QNode
{QDatatype _data;struct  QNode* _next;
}QNode;typedef struct Queue
{int k;QNode* head;QNode* tail;
}Queue;//初始化队列
void QueueInit(Queue* q);//队尾入数据
void QueuePush(Queue* q, QDatatype data);//对头出数据
void QueuePop(Queue* q);//获取队列对头元素
QDatatype QueueFront(Queue* q);//获取队列队尾元素
QDatatype QueueBack(Queue* q);//获取队列中有效元素个数
int QueueSize(Queue* q);//检测队列是否为空,如果为空返回非零结果,非空返回0
bool QueueEmpty(Queue* q);//销毁队列
void QueueDestory(Queue* q);

2.2.queue.c

#define _CRT_SECURE_NO_WARNINGS
#include"queue.h"void QueueInit(Queue* q)
{assert(q);q->head = q->tail = NULL;q->k = 0;
}void QueuePush(Queue* q, QDatatype data)
{assert(q);QNode* tmp = (QNode*)malloc(sizeof(QNode));if (tmp == NULL){perror("malloc fail");return;}tmp->_data = data;tmp->_next = NULL;if (q->tail == NULL){q->head = q->tail = tmp;}else{q->tail->_next = tmp;q->tail = tmp;}q->k++;
}void QueuePop(Queue* q)
{assert(q);assert(q->k > 0);QNode* next = q->head->_next;free(q->head);q->head = next;if (q->head == NULL){q->tail = NULL;}q->k--;
}QDatatype QueueFront(Queue* q)
{assert(q);assert(q->k > 0);return q->head->_data;
}QDatatype QueueBack(Queue* q)
{assert(q);assert(q->k > 0);return q->tail->_data;
}int QueueSize(Queue* q)
{assert(q);return q->k;
}bool QueueEmpty(Queue* q)
{assert(q);return q->tail == NULL;
}void QueueDestory(Queue* q)
{assert(q);QNode* tmp = q->head;while (tmp){QNode* next = tmp->_next;free(tmp);tmp = next;}q->k = 0;q->head = q->tail = NULL;
}

2.3.test.c

#define _CRT_SECURE_NO_WARNINGS
#include"queue.h"int main()
{Queue q;QueueInit(&q);QueuePush(&q, 0);QueuePush(&q, 1);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);QueuePush(&q, 6);printf("%d\n", QueueSize(&q));printf("%d ", QueueFront(&q));printf("%d\n", QueueBack(&q));printf("%d ", QueueFront(&q));QueuePop(&q);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n%d\n", QueueSize(&q));QueueDestory(&q);return 0;
}

运行结果如图,至于为什么是这些个结果,我们详细看以下鼠鼠的队列方案是如何实现的。

2.4.定义队列

typedef int QDatatype;typedef struct QNode
{QDatatype _data;struct  QNode* _next;
}QNode;typedef struct Queue
{int k;QNode* head;QNode* tail;
}Queue;

老样子我们将int重命名成QDatatype,方便以后代码的维护。

让后定义并重命名结构体QNode充当队列节点 ,这些节点根据数据元素的入队列或者出队列按需申请或者释放。QNode中成员_data用来存放数据元素,QNode中成员_next用来链接下一个节点。

又由于基于无头单向非循环链表(以下简称链表)实现的队列在入队列和出队列时分别需要链表尾插和头删,而且经常需要知道队列中数据元素的个数,我们定义并重命名结构体Queue来维护上面需求:Queue中成员k用来记录队列中数据元素个数;成员head用来指向链表头节点;成员tail用来指向链表尾节点。

大概这样子:

2.5.初始化队列

void QueueInit(Queue* q)
{assert(q);q->head = q->tail = NULL;q->k = 0;
}

断言防止传入的结构体变量地址为空(因为这个地址不可能为空)。将head和tail置成NULL,将k置成0即可。 

2.6.队尾入队列

void QueuePush(Queue* q, QDatatype data)
{assert(q);QNode* tmp = (QNode*)malloc(sizeof(QNode));if (tmp == NULL){perror("malloc fail");return;}tmp->_data = data;tmp->_next = NULL;if (q->tail == NULL){q->head = q->tail = tmp;}else{q->tail->_next = tmp;q->tail = tmp;}q->k++;
}

断言防止传入的结构体变量地址为空(这点以下不在赘述)。 队尾入队列其实就是链表尾插,先动态申请一个结构体QNode空间充当新节点,这个新节点的存放好想插入的数据元素,再让新节点链接好队列(链接队列是要区分队列是否为空),k加一即可。

2.7.对头出队列

void QueuePop(Queue* q)
{assert(q);assert(q->k > 0);QNode* next = q->head->_next;free(q->head);q->head = next;if (q->head == NULL){q->tail = NULL;}q->k--;
}

断言防止队列为空仍然出队列。常规来说再进行链表头删、k减一即可完成出队列,但要注意如果队列中只有一个数据元素(或者说链表只有一个节点)时,如果按常规操作的话会使得tail变成野指针,用上面一个if语句很好处理问题。 

2.8.获取队列队头元素

QDatatype QueueFront(Queue* q)
{assert(q);assert(q->k > 0);return q->head->_data;
}

 断言防止队列为空仍然获取对头元素。返回head指向的节点成员_data即可。

2.9.获取队列队尾元素

QDatatype QueueBack(Queue* q)
{assert(q);assert(q->k > 0);return q->tail->_data;
}

  断言防止队列为空仍然获取对尾元素。返回tail指向的节点成员_data即可。

2.10.获取队列中有效元素的个数

int QueueSize(Queue* q)
{assert(q);return q->k;
}

根据设定可知,返回k即可。 

2.11.检测队列是否为空,如果为空返回非零结果,非空返回0

bool QueueEmpty(Queue* q)
{assert(q);return q->tail == NULL;
}

若tail指向NULL说明队列为空(或者说链表为空),则q->tail==NULL为真,返回真。若队列不为空逻辑跟队列为空逻辑相反,返回假。 

2.12.销毁队列 

void QueueDestory(Queue* q)
{assert(q);QNode* tmp = q->head;while (tmp){QNode* next = tmp->_next;free(tmp);tmp = next;}q->k = 0;q->head = q->tail = NULL;
}

遍历链表将节点(这些节点都是动态申请的)都释放掉,再将head和tail置成NULL,并将k置成0即可。

 3.分析运行结果

佬们请看:

第一条语句:定义一个结构体Queue变量q;

第二条语句:初始化结构体变量q;

第三条到第十条语句:数据元素0、1、1、2、3、4、5、6依次入队列,执行完后队列想象图为: 

第十一条语句:执行printf函数,打印队列有效元素个数为8并换行。

第十二条和第十三条语句:均执行printf函数,分别打印对头元素0和队尾元素6,换行。

第十四条语句: 执行printf函数,打印对头元素0。

第十五条语句:对头元素0出队列,执行完第十五条语句后队列想象图为:

接下来while循环:当队列不为空时,打印对头元素再对头元素出队列。所以分别打印1、1、2、3、4、5、6。执行完while循环后,队列为空(或者说链表为空)。

再接下来打印队列有效元素个数为0,印证队列为空。再销毁队列。

4.ending

感谢阅读,有不对的地方欢迎像本鼠拿捏玩偶一样拿捏鼠鼠捏!

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

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

相关文章

【HTML】HTML基础7.2(有序列表)

目录 标签 效果 注意 标签 <ol> <li>列表内容</li> <li>列表内容</li> <li>列表内容</li> <li>列表内容</li> 。。。。。。 </ol> 效果 代码 <ol><li>银河护卫队 10000000000</li><l…

RUST 每日一省:发布到crates.io

github是开源代码分享的地方&#xff0c;rust的开源项目除了github&#xff0c;我们还可以将其发布到 crates.io 上&#xff0c;然后其它用户就可以使用cargo进行安装使用了。其实步骤很简单&#xff0c;只有三条命令了&#xff0c;我们一次来看一下。 1、cargo package 首先&a…

Threejs着色器(GPU)编程——感温管网

管网,作为支撑现代城市运转的重要基础设施,是隐藏在地面之下的庞大工程网络。这些管网如同城市的血脉,负责输送各种必要的资源,如水源、热力、燃气等,同时排除废水和其他废弃物。然而,由于其位于地下,人们往往难以直接感知其存在和运行状态。为了保障这些地下管网的安全…

Go编程实战:高效利用encoding/binary进行数据编解码

Go编程实战&#xff1a;高效利用encoding/binary进行数据编解码 引言encoding/binary 包核心概念ByteOrder 接口Binary 数据类型的处理处理复杂数据结构 基础使用教程数据类型与二进制格式的映射基本读写操作写操作 - binary.Write读操作 - binary.Read 错误处理 高级功能与技巧…

手机备忘录可以设置密码吗 能锁屏加密的备忘录

在繁忙的生活中&#xff0c;手机备忘录成了我随身携带的“小秘书”。那些关于工作的灵感、生活的琐事&#xff0c;甚至深藏心底的小秘密&#xff0c;都被我一一记录在里面。然而&#xff0c;每次当手机离开我的视线&#xff0c;或者需要借给他人使用时&#xff0c;我总会心生担…

Vue+SpringBoot打造校园疫情防控管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 学生2.2 老师2.3 学校管理部门 三、系统展示四、核心代码4.1 新增健康情况上报4.2 查询健康咨询4.3 新增离返校申请4.4 查询防疫物资4.5 查询防控宣传数据 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBoot…

力扣刷题Days12第二题--100相同的树(js)

目录 1,题目 2&#xff0c;代码 2.1深度优先遍历 2.2广度优先遍历 3&#xff0c;学习与总结 1,题目 给你两棵二叉树的根节点 p 和 q &#xff0c;编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同&#xff0c;并且节点具有相同的值&#xff0c;则认为它们是…

数字孪生10个技术栈:数据处理的六步骤,以获得可靠数据。

一、什么是数据处理 在数字孪生中&#xff0c;数据处理是指对采集到的实时或历史数据进行整理、清洗、分析和转化的过程。数据处理是数字孪生的基础&#xff0c;它将原始数据转化为有意义的信息&#xff0c;用于模型构建、仿真和决策支持。 数据处理是为了提高数据质量、整合数…

ElasticSearch之通过search after和scroll解决深度分页问题

写在前面 通过from&#xff0c;size来进行分页查询时&#xff0c;如下&#xff1a; 当from比较大时会有深度分页问题&#xff0c;问题产生的核心是coordinate node需要从每个分片中获取fromsize条数据&#xff0c;当from比较大&#xff0c;整体需要获取的数据量也会比较大&am…

阿珊解析Vuex:实现状态管理的利器

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

[c++] c++ 中的顺序(构造,析构,初始化列表,继承)

对象构造的时候&#xff0c;对象成员变量的初始化顺序是什么样的 &#xff1f; 派生类构造的时候&#xff0c;先构造基类还是先构造派生类 &#xff1f; 构造函数中的初始化列表&#xff0c;初始化的顺序是列表的顺序吗 &#xff1f; 析构的时候&#xff0c;析构的顺序是什么…

静态时序分析:典型与非典型时序路径的约束详解(一)

相关阅读 静态时序分析https://blog.csdn.net/weixin_45791458/category_12567571.html?spm1001.2014.3001.5482 时序路径是静态时序分析中的一个重要概念&#xff0c;了解时序路径能帮助设计者更好地编写SDC脚本&#xff0c;本文旨在详细介绍时序路径相关内容。 首先给出时序…

【重制版】WSDM 2024 2023时空时序论文总结

&#x1f31f;【紧跟前沿】“时空探索之旅”与你一起探索时空奥秘&#xff01;&#x1f680; 欢迎大家关注时空探索之旅 WSDM 2024于2024年3月4日-3月8日在墨西哥梅里达&#xff08;Mrida, Mxico&#xff09;正在举行。目前官网已经放出了所有被录用论文的表单&#xff08;链接…

实现消息队列(Kafka、ActiveMQ、RabbitMQ和RocketMQ)高可用

概述 单机没有高可用可言&#xff0c;高可用都对集群来说的 要保证消息队列系统&#xff08;如Kafka、ActiveMQ、RabbitMQ和RocketMQ&#xff09;的高可用性&#xff0c;可以采取以下一些通用的措施&#xff1a; 集群部署&#xff1a;将消息队列系统部署为集群&#xff0c;包…

uniapp和vue项目配置多语言,实现前端切换语言

在uniapp中配置多语言功能&#xff0c;实现前端切换语言&#xff0c;可以按照以下步骤进行&#xff1a; 1. 创建语言包 首先&#xff0c;创建一个名为 lang 的目录&#xff0c;并在该目录下为每种支持的语言创建对应的JSON或JS文件。例如&#xff1a; lang/en.js&#xff08…

【Linux】深入理解cd命令

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;Linux ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 正文 基本用法&#xff1a; 相对路径和绝对路径&#xff1a; 特殊符号和快捷方式&#xff1a; 符号链接&#xff1a; 自动补全&…

重装系统后正版office如何安装

前言 重装系统后&#xff0c;正版office如何安装 登录官网 https://www.microsoft.com 下载office https://account.microsoft.com/services

培训机构新助力:教务管理工教务管理新境界:完善流程,高效运营触手可及具

随着科技的不断进步&#xff0c;教育领域正迎来一场革命性的变革。乔拓云教育系统&#xff0c;作为这场变革的引领者&#xff0c;正以其卓越的功能和高效的解决方案&#xff0c;为培训机构带来前所未有的教务管理新篇章。 一、高效排课&#xff0c;让教务管理更轻松 乔拓云教育…

蓝桥杯(3.7)

P1102 A-B 数对 import java.util.Scanner; public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int c sc.nextInt();int[] res new int[n1];for(int i1;i<n;i)res[i] sc.nextInt();int sum 0;for(i…

Redis基础入门

目录 目录 一、认识Redis Redis特征&#xff1a; 二、Redis数据结构介绍 三、Redis的命令 1.Redis通用命令 2.关于String类型的命令 3.关于Hash类型的命令 4.关于List类型的常用命令 5.关于Set类型的常用命令 6.关于SortSet类型的常用命令 四、Redis中的层级关系的key 五…