【数据结构和算法】--队列

目录

  • 队列的概念及结构
  • 队列的实现
    • 初始化
    • 入队
    • 出队
    • 其他一些队列函数
  • 小结
  • 队列相关题目

队列的概念及结构

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

  • 入队列:进行插入操作的一端称为队尾
  • 出队列:进行删除操作的一端称为队头

队列结构联想起来也非常简单,如其名,队列就相当于银行办理业务的柜台前一条长长的队伍,排在队伍前面的人(队头)可以先办理,而在队伍最后面的人(队尾)只能最后办理,如果继续有人来办理业务就只能排在队尾,这样的模式就是队列且遵循队头出队列,队尾入队列的原则。结构大致如下:

在这里插入图片描述

队列的实现

队列的实现同样有两种方式–数组队列,链式队列

  1. 数组队列:
    如果用数组实现队列:这样队头就只能指向下标为0的位置,那么队尾就指向队列最后一个元素的后一个的下标,基于此结构,想要出队操作,时间复杂度就会升高为O(N)且十分不方便。因为每当要将下标为0的元素出队,后面的所有元素就要前移并改变队尾指向。大致如下:

在这里插入图片描述

还有一点就是,如果使用数组队列,在前期有大量数据入队列,动态开辟了很大的空间,到后期可能很多数据都出了队列但动态开辟的空间并不能释放,那就造成了严重的空间浪费。

  1. 链式队列:
    如果使用双向链表: 这与栈为什么不用双向链表实现一个道理,虽然可以实现,且入队/出队的时间复杂度都为O(1)但结构较为复杂,实现起来并不是很实用;
    那么我们这时会选择结构更优得单链表,虽说单链表尾插得时间复杂度是O(N),但我们可以定义一个变量(QNode* ptail)来记录单链表的尾节点,这样每次入队时便不用再遍历单链表找尾节点,时间复杂度也降为O(1)。结构如下:

在这里插入图片描述

这样按需开辟空间,出队列就释放节点,进队列新建节点,也大大减少了空间的浪费。我们便可如下定义队列的每个节点:

typedef int QDataType;
//队列节点
typedef struct QueueNode
{
    QDataType val;
    struct QueueNode* next;//链接下一个节点的指针
}QNode;

因为我们要记录队列的头(QNode* phead)和尾(QNode* ptail)(下文称这两个指针为头指针和尾指针),且基本每个函数都要用到这两个变量,甚至一些函数还要修改这两个变量对应的值,那就不得不传二级指针了,这也就大大增加了代码的难度!为了解决这个问题,我们可以定义一个结构体,并将这两个变量放到结构体中,每次函数调用时,只需传这个结构体地址即可
为了方便统计队列里面的节点数,我们通常还会定义一个整型变量size,有元素出队列时size--,入队列时size++
此结构体定义方式如下:

typedef struct Queue
{
    QNode* phead;
    QNode* ptail;
    int size;
}Queue;

初始化

初始时队列中无节点,所以pq->size = 0,头指针(pq->phead = NULL)尾指针(pq->ptail = NULL)都指向空。

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->size = 0;
	pq->phead = pq->ptail = NULL;
}

入队

入队操作首先要新建一个节点(类型为QNode),然后通过尾指针指向的节点链接此节点pq->ptail->next = newnode),并更新尾指针的指向pq->ptail = newnode),将记录节点数的值加1(pq->size++)。
在链接时还要考虑到队列为空的情况,此情况下直接将头/尾指针指向新建的节点(pq->ptail = pq->phead = newnode)。

//入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//新建节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush()::malloc");
		return;
	}
	//新建的节点初始化
	newnode->next = NULL;
	newnode->val = x;
	//判断,链接
	if (pq->ptail == NULL)
	{
	    //1.原队列无节点
		pq->ptail = pq->phead = newnode;
	}
	else
	{
	    //2.原队列已有节点
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

出队

出队列操作首先要确保队列有节点才能出队,那么断言一下就可(assert(pq->phead);)。需要注意的是出队是头删,可以先定义变量记录头节点QNode* del = pq->phead;),然后再将头指针指向下一个节点phead = phead->next;),最后将原头节点释放free(del);),并将记录节点数的值减1pq->size--)。
当队列只有一个节点时,删除后队尾和队头指针都应该指向空,但上述操作并不能达到此效果,所以要单独判断一下,将尾指针指向空。

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	//队列不为空
	assert(pq->phead);
	QNode* del = pq->phead;//记录头节点
	pq->phead = pq->phead->next;//头指针重定向
	free(del);//释放原头节点
	del = NULL;
	//队列是否被删空判断
	if (pq->phead == NULL)
		pq->ptail = NULL;
	pq->size--;
}

其他一些队列函数

  1. 队列有效数据个数:
    上面也讲过pq->size记录的就是队列的有效数据个数
//数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
  1. 队列是否为空:
    两种判断方法:1.当头指针指向NULL,2.pq->size的值为0
//队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
	//return pq->size == 0;
}

  1. 返回队头数据:
    首先要判断队列不为空,然后返回头指针指向的节点的val即可。
//返回队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
  1. 返回队尾数据:
    同上,首先要判断队列不为空,然后返回尾指针指向的节点的val即可。
//返回队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->ptail->val;
}
  1. 释放队列空间:
    遍历队列直到头指针指向空,每遍历一次释放一个节点,最后将头/尾指针指空,pq->size0
//释放
void QueueDetroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	//遍历,释放
	while (cur)
	{
	    //记录下一个节点地址
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

小结

  • 队列是一种先进先出的结构,与栈相反;
  • 队列是头部删除尾部插入一般使用链表实现,且与栈结构一样不支持随机访问
  • 在实现队列时一般定义两个结构体,一个结构体用来记录每个节点中所需要的值,另一个用来记录队列的队头,队尾和节点数。第二个结构体的使用避免了二级指针,且在函数调用时一般传第二个结构体的地址

队列相关题目

  1. 下面关于栈和队列的说法中错误的是( A B
    A.队列和栈通常都使用链表实现
    B.队列和栈都只能从两端插入、删除数据
    C.队列和栈都不支持随机访问和随机插入
    D.队列是“先入先出”,栈是“先入后出”

这题主要考察对队列和栈的性质的区分,思路如下:

  • A错误:是尾部插入和删除,一般使用顺序表实现,队列是头部删除尾部插入,一般使用链表实现

  • B错误:是后进先出,尾部插入和删除队列是先进先出,尾部插入头部删除

  • C正确:栈只能访问栈顶元素,不支持随机访问,队列也不支持

  • D正确:栈和队列的特性

关于队列还有一个知识点就是循环队列,因其结构复杂就单独拿出来讲。

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

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

相关文章

2023 巅峰之作 | AIGC、AGI、GhatGPT、人工智能大语言模型的崛起与挑战

文章目录 01 《ChatGPT 驱动软件开发》内容简介 02 《ChatGPT原理与实战》内容简介 03 《神经网络与深度学习》04 《AIGC重塑教育》内容简介 05 《通用人工智能》目  录 2023年是人工智能大语言模型大爆发的一年,一些概念和英文缩写也在这一年里集中出现&#xff…

Java反射(2)

我是南城余!阿里云开发者平台专家博士证书获得者! 欢迎关注我的博客!一同成长! 一名从事运维开发的worker,记录分享学习。 专注于AI,运维开发,windows Linux 系统领域的分享! 本…

Docker-compose单机容器编排

YML文件是什么? YAML文件是一种标记语言,以竖列的形式展示序列化的数据格式。可读性很高类似于json格式。语法简单。 YAML通过缩进来表示数据结构,连续的项目用-符号来表示。 YML文件使用的注意事项 1、 大小写敏感 2、 通过缩进表示层级…

代码随想录刷题题Day11

刷题的第十一天,希望自己能够不断坚持下去,迎来蜕变。😀😀😀 刷题语言:C / Python Day11 任务 ● 理论基础 ● 递归遍历 ● 迭代遍历 ● 统一迭代 1 二叉树理论基础 1.1 二叉树的种类 (1&…

Linux----内核及发行版

1. Linux内核 Linux内核是操作系统内部操作和控制硬件设备的核心程序,它是由芬兰人林纳斯开发的。 内核效果图: 说明: 真正操作和控制硬件是由内核来完成的,操作系统是基于内核开发出来的。 2. Linux发行版 是Linux内核与各种常用软件的组合产品&am…

这些Pads技术问题,你还在继续犯错吗?

随着时代发展,Mentor Pads很快成为国内半导体公司的常用EDA软件之一,也就是说起码有数万个电子工程师在使用Pads设计PCB,当然也有很多工程师在使用Pads时遇到了很多问题,下面来看看有哪些技术问题仍然还在继续犯? 1、走…

9:00面试,9:05就出来了,问的问题有点变态。。。

从小厂出来,没想到在另一家公司又寄了。 到这家公司开始上班,加班是每天必不可少的,看在钱给的比较多的份上,就不太计较了。没想到12月一纸通知,所有人不准加班,加班费不仅没有了,薪资还要降40…

1840_emacs org-mode babel的语言支持

Grey 全部学习内容汇总: GitHub - GreyZhang/g_org: my learning trip for org-mode 1840_emacs org-mode babel的语言支持 主题由来介绍 Babel是org-mode中支持文学式编程以及可重现研究的一个核心模块,之前看过这个插件的优点是功能完善且支持的语…

20分钟部署ChatGLM3-6B

准备工作 1.下载源代码: https://github.com/THUDM/ChatGLM3 2.下载预训练模型: https://modelscope.cn/models/ZhipuAI/chatglm3-6b/files 可以创建一个py文件,直接使用如下代码下载到本地: from modelscope.hub.snapshot_dow…

出现 Error:Unable to access jarfile xxxx\target\nacos-server.jar 解决方法

目录 1. 问题所示2. 原理分析3. 解决方法1. 问题所示 执行Nacos中的startup.cmd的时候出现闪退,于是在该脚本的最后一行添加pause,查看因为什么原因闪退 出现的bug如下所示:Error:Unable to access jarfile xxxx\target\nacos-server.jar 截图如下所示: 查看内部文件夹,…

壹家人温暖宁夏中卫,34个孩子收到壹基金温暖包

这个12月,2023年度壹基金温暖包在宁夏中卫的发放活动顺利开展,镇罗中学的4个孩子和山羊场小学28个孩子领到了这份温暖的冬日礼物,后续还有丰台村2个孩子也会领到这份冬天的礼物。 2023年壹基金温暖包共筹集温暖包34个,经过我们…

Linux基本操作指令

哈喽小伙伴们,从这篇文章开始,在学习数据结构的同时,我们开启一个新的篇章——Linux操作系统的学习,这将会是又一个新的开始,希望小伙伴们能够认真细心,不要掉队哦。 目录 一.什么是Linux 二.为什么要学习…

QT用户界面隐藏管理员界面部分功能

效果预览 QT用户界面隐藏管理员界面部分功能 GITHUB网站 QT版本 qmake QT core gui sqlGitHub代码获取链接 GitHub代码获取链接

HAT(CVPR 2023):Hybrid Attention Transformer for Image Restoration

HAT ​ 论文地址:HAT: Hybrid Attention Transformer for Image Restoration ​ 代码地址:XPixelGroup/HAT: CVPR2023 - Activating More Pixels in Image Super-Resolution Transformer 摘要 ​ 通过归因分析attribution analysis method - Local …

智慧燃气让城市能源系统高效运行

关键词:智慧燃气、燃气数字化、智慧燃气平台、智慧燃气解决方案、智慧燃气系统 随着我国城镇燃气行业的发展,燃气行业管理及服务从简单的手工运作阶段迈入数字燃气阶段,大量采用信息化手段管理燃气业务,智慧燃气应运而生。它既是…

Web漏洞分析-文件解析及上传(上)

随着互联网的迅速发展,网络安全问题变得日益复杂,而文件解析及上传漏洞成为攻击者们频繁攻击的热点之一。本文将深入研究文件解析及上传漏洞,通过对文件上传、Web容器IIS、命令执行、Nginx文件解析漏洞以及公猫任意文件上传等方面的细致分析&…

k8s-Pod

1、Pod 简介: (1) 概念: Pod 是 Kubernetes 中创建和管理的,最小的可部署的计算单元。Pod中存储了一组(一个或多个)容器,以及怎样运行这些容器的声明,这些容器共享存储、网络和环境&#xff0…

简易的JS逆向解码

在实战的漏洞挖掘中阅读JS有以下几个作用: 1.JS中存在插件名字,根据插件找到相应的漏洞直接使用 通过控制台大致阅读网站JS代码发现此网页引用了北京的一家公司的代码,并且使用了h-net的框架,接下来我们可以百度这家公司或者是这…

智能优化算法应用:基于水循环算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用:基于水循环算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用:基于水循环算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.水循环算法4.实验参数设定5.算法结果6.参考文…

【精选】SpringMVC简介及其执行流程,参数获取方式

SpringMVC简介 MVC模型 MVC全称Model View Controller,是一种设计创建Web应用程序的模式。这三个单词分别代表Web应用程序的三个部分: Model(模型):指数据模型。用于存储数据以及处理用户请求的业务逻辑。在Web应用中&…