[数据结构初阶]队列

鼠鼠我呀，今天写一个基于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

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

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

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

相关文章

每日五道java面试题之springMVC篇（一）

每日五道java面试题之springMVC篇（一）

目录&#xff1a; 第一题. 什么是Spring MVC&#xff1f;简单介绍下你对Spring MVC的理解&#xff1f;第二题. Spring MVC的优点第三题. Spring MVC的主要组件&#xff1f;第四题. 什么是DispatcherServlet?第五题. 什么是Spring MVC框架的控制器&#xff1f; 第一题. 什么是S…
阅读更多...
JavaScript 作用域详解：如何影响变量生命周期

JavaScript 作用域详解：如何影响变量生命周期

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

Linux系统——Keepalive群集部署及认识

目录 一、Keepalive的认识 1.Keepalive基础——VRRP 2.Keepalived工具介绍 2.1Keepalived介绍 2.2Keepalived架构 2.2.1用户空间核心组件 2.2.2WatchDog&#xff1a;监控进程&#xff08;整个架构是否有问题&#xff09; 二、安装Keepalived及相关配置文件详解 1.安装…
阅读更多...
python 输入和输出

python 输入和输出

在 Python 中&#xff0c;输入和输出是最基本的操作之一。你可以使用内置函数 input() 来获取用户输入&#xff0c;使用 print() 函数来输出信息到控制台。 输入&#xff08;Input&#xff09; input() 函数用于从用户那里获取输入。这个函数会将用户的输入作为字符串返回。 示…
阅读更多...
【C语言】终の指针（前篇）

【C语言】终の指针（前篇）

个人主页点这里~ 指针初阶点这里~ 指针初阶2.0点这里~ 指针进阶点这里~ 终の指针 一、回调函数二、qsort函数1、整形比较2、结构数据比较①结构体②-> 的使用③结构数据比较 一、回调函数 回调函数就是⼀个通过函数指针调用的函数。 把一个函数的指针作为参数传递给另一…
阅读更多...
分类预测 | Matlab基于GWO-RBF灰狼算法优化径向基神经网络的分类预测

分类预测 | Matlab基于GWO-RBF灰狼算法优化径向基神经网络的分类预测

分类预测 | Matlab基于GWO-RBF灰狼算法优化径向基神经网络的分类预测 目录 分类预测 | Matlab基于GWO-RBF灰狼算法优化径向基神经网络的分类预测分类效果基本介绍程序设计参考资料 分类效果 基本介绍 Matlab基于GWO-RBF灰狼算法优化径向基神经网络的分类预测。基于灰狼算法(GWO…
阅读更多...
和为K的子数组

和为K的子数组

题目&#xff1a; 使用前缀和的方法可以解决这个问题&#xff0c;因为我们需要找到和为k的连续子数组的个数。通过计算前缀和&#xff0c;我们可以将问题转化为求解两个前缀和之差等于k的情况。 假设数组的前缀和数组为prefixSum&#xff0c;其中prefixSum[i]表示从数组起始位…
阅读更多...
仓储管理系统(WMS) 的研发历程-PRD撰写

仓储管理系统(WMS) 的研发历程-PRD撰写

题外话&#xff1a;PRD的展现形式有多种&#xff0c;有的人喜欢在axure上直接做产品描述&#xff0c;觉得word较为过时&#xff0c;有的人认为axure不专业&#xff0c;任何展现形式都无可厚非&#xff0c;重要的达到PRD的目的&#xff0c;PRD的目标是让团队知道需求实现细节&am…
阅读更多...
Vue中如何处理用户权限？

Vue中如何处理用户权限？

在前端开发中&#xff0c;处理用户权限是非常重要的一个方面。Vue作为一种流行的前端框架&#xff0c;提供了很多便捷的方式来管理用户权限。本文将介绍一些Vue中处理用户权限的方法 1. 使用路由守卫 Vue Router提供了一个功能强大的功能&#xff0c;即导航守卫&#xff08;N…
阅读更多...
18-Java迭代器模式 ( Iterator Pattern )

18-Java迭代器模式 ( Iterator Pattern )

Java迭代器模式 摘要实现范例 迭代器模式&#xff08;Iterator Pattern&#xff09;用于顺序访问集合对象的元素&#xff0c;不需要知道集合对象的底层表示 迭代器模式是 Java 和 .Net 编程环境中非常常用的设计模式 迭代器模式属于行为型模式 摘要 1. 意图 提供一种方法…
阅读更多...
【LeetCode:2917. 找出数组中的 K-or 值 + 模拟+位运算】

【LeetCode:2917. 找出数组中的 K-or 值 + 模拟+位运算】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…
阅读更多...
国内鞋服品牌如何打造出优衣库的“零库存”运营体系

国内鞋服品牌如何打造出优衣库的“零库存”运营体系

优衣库&#xff0c;作为全球知名的服装品牌&#xff0c;以其独特的“零库存”运营体系在业界树立了标杆。对于国内鞋服品牌而言&#xff0c;如何借鉴并打造类似的“零库存”运营体系&#xff0c;不仅是提升竞争力的关键&#xff0c;也是实现可持续发展的必然选择。本文将探讨国…
阅读更多...
springboot实现多线程开发（使用@Async注解，简单易上手）

springboot实现多线程开发（使用@Async注解，简单易上手）

根据springboot的核心思想便捷开发&#xff0c;使用多线程也变得简单起来&#xff0c;通过一下几个步骤即可实现。 核心注解 EnableAsync将此注解加在启动类上&#xff0c;使项目支持多线程。 Async 使用我们的Async注解在所需要进行多线程的类上即可实现。 配置线程池 …
阅读更多...
2024/3/7—2575. 找出字符串的可整除数组

2024/3/7—2575. 找出字符串的可整除数组

代码实现&#xff1a; int* divisibilityArray(char *word, int m, int *returnSize) {int n strlen(word);int *res (int*)malloc(sizeof(int) * n);long cur 0;for (int i 0; i < n; i) {cur (cur * 10 (word[i] - 0)) % m;res[i] (cur 0) ? 1 : 0;}*returnSize …
阅读更多...
1.BOM-获取元素(获取元素、修改属性)

1.BOM-获取元素(获取元素、修改属性)

web Api基本认知 作用&#xff1a;通过JS去操作html页面和浏览器(实现浏览器中的某些功能) 分类&#xff1a; DOM(网页)&#xff1a;Document Object Model(文档对象模型) BOM(浏览器)&#xff1a;Borwser Object Model(浏览器对象模型) DOM DOM树 将网页中标签的关系以树状…
阅读更多...
[c++] c++ 中的顺序(构造，析构，初始化列表，继承)

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

对象构造的时候&#xff0c;对象成员变量的初始化顺序是什么样的 &#xff1f; 派生类构造的时候&#xff0c;先构造基类还是先构造派生类 &#xff1f; 构造函数中的初始化列表&#xff0c;初始化的顺序是列表的顺序吗 &#xff1f; 析构的时候&#xff0c;析构的顺序是什么…
阅读更多...
评估需求优先级的方法

评估需求优先级的方法

Kano模型&#xff1a; 1.前言 在大量的需求需要进行迭代时&#xff0c;由于时间、人力、财力等相关因素干扰&#xff0c;无法在有限的时间内容对所有的需求进行满足&#xff0c;此时需要我们对需求进行优先级的排列。最大化的合理的提高有限资源的使用。 在常见的产品优先级…
阅读更多...
vcomp140.dll丢失如何修复，5种修复方法轻松搞定vcomp140.dll问题

vcomp140.dll丢失如何修复，5种修复方法轻松搞定vcomp140.dll问题

vcomp140.dll文件的丢失可能会引发一系列系统运行与软件功能上的问题。具体来说&#xff0c;这个动态链接库文件是Visual C Redistributable的一部分&#xff0c;对于许多基于此环境开发的应用程序至关重要。一旦缺失&#xff0c;可能会导致部分应用程序无法正常启动或运行&…
阅读更多...
代码随想录训练营第39天 | LeetCode 62.不同路径、​​​​​​LeetCode 63. 不同路径 II

代码随想录训练营第39天 | LeetCode 62.不同路径、​​​​​​LeetCode 63. 不同路径 II

LeetCode 62.不同路径 文章讲解&#xff1a;代码随想录(programmercarl.com) 视频讲解&#xff1a;动态规划中如何初始化很重要&#xff01;| LeetCode&#xff1a;62.不同路径_哔哩哔哩_bilibili 思路 代码如下&#xff1a; ​​​​​​LeetCode 63. 不同路径 II 文章讲解…
阅读更多...
Java定时调度

Java定时调度

在Java应用程序中&#xff0c;定时调度是一项重要的任务。它允许你安排代码执行的时间&#xff0c;以便在将来的某个时刻自动执行任务。Java提供了多种方式来实现定时调度&#xff0c;其中最常用的是Java的Timer和ScheduledExecutorService。 在本教程中&#xff0c;我们将学习…
阅读更多...
最新文章

Copyright @ 2022~2023