【数据结构】线性表之《队列》超详细实现

队列

  • 一.队列的概念及结构
  • 二.顺序队列与链队列
    • 1.顺序队列
    • 2.链队列
  • 三.链队列的实现
    • 1.创建队列
    • 2.初始化队列
    • 3.入队
    • 4.出队
    • 5.获取队头元素
    • 6.获取队尾元素
    • 7.队列的大小
    • 8.队列的判空
    • 9.清空队列
    • 10.销毁队列
  • 四.队列的盲区
  • 五.模块化源代码
    • 1.Queue.h
    • 2.Queue.c
    • 3.test.c
  • 六.栈和队列必做OJ题

一.队列的概念及结构

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

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

在这里插入图片描述

二.顺序队列与链队列

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

在这里插入图片描述

1.顺序队列

在这里插入图片描述

2.链队列

在这里插入图片描述

那是不是再用一个指针指向队尾就可以了呢？是的如下图：

在这里插入图片描述

这种链表结构完美的解决了尾插时效率低的问题。

三.链队列的实现

1.创建队列

先创建结构体（存放数据和先一个节点的地址）用来表示节点，再额外创建队列结构体（成员：队头指针和队尾指针），队头指针指向队列的队头，队尾指针指向队列的队尾。

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

Queue q;//q代表链队列

2.初始化队列

将队头指针和队尾指针初始化为NULL。

void QueueInit(Queue* pq)
{
	assert(pq);//断言
	pq->head = pq->tail = NULL;
}

3.入队

先是创建一个新的节点，存放数据和NULL指针，入队分两种情况：

  1. 若队头和队尾指针都为NULL，则队头和队尾指针都指向新的节点。
  2. 若队头和队尾指针不为NULL，则向队尾插入新的节点，再更新队尾指针。
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	
	//创建入队的节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)//开辟失败
	{
		perror("malloc fail!");
		exit(-1);
	}
	//开辟成功
	newnode->data = x;
	newnode->next = NULL;

	//入队操作
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

4.出队

出队也有两种情况

  1. 队列只有一个节点，先删除队头，再让队头和队尾指针指向NULL，防止队尾指针变成野指针。
  2. 队列有多个节点，先保存队头的下一个节点指针，再删除队头，最后更新队头指针。
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);//队列不能为空

	//队列只有一个节点
	if (pq->tail->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//队列有多个节点
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

5.获取队头元素

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);//队列不能为空
	return pq->head->data;
}

6.获取队尾元素

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail != NULL);//队列不能为空
	return pq->tail->data;
}

7.队列的大小

定位队头节点，利用NULL这一条件遍历队列即可。

int QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;//定位队头节点
	int size = 0;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;//更新cur
	}
	return size;
}

8.队列的判空

判断队头指针是否为NULL即可。

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

9.清空队列

定位队头节点，依次先后删除即可。

void QueueClear(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;//定位队头节点
	while (cur != NULL)
	{
		QNode* next = cur->next;
		free(cur);//逐个删除
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

10.销毁队列

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueClear(pq);
	//注意不能释放pq，这不是动态开辟的地址，而是栈区的地址，所以清空与销毁没什么区别
}

四.队列的盲区

由于队列的特殊结构，只能遵循先进先出的原则，不允许随便遍历队列，否则就失去了队列的特点，只能用以下的代码得到数据：

while (!QueueEmpty(&q))
{
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
}

五.模块化源代码

1.Queue.h

//#pragma once 防止头文件被重复包含
#ifndef __QUEUE_H__
#define __QUEUE_H__

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

void QueueInit(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);//队列判空

void QueueClear(Queue* pq);//清空队列

void QueueDestory(Queue* pq);//销毁队列
#endif

2.Queue.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);//断言
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	
	//创建入队的节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)//开辟失败
	{
		perror("malloc fail!");
		exit(-1);
	}
	//开辟成功
	newnode->data = x;
	newnode->next = NULL;

	//入队操作
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);//队列不能为空

	//队列只有一个节点
	if (pq->tail->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//队列有多个节点
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);//队列不能为空
	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail != NULL);//队列不能为空
	return pq->tail->data;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;//定位队头节点
	int size = 0;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;//更新cur
	}
	return size;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

void QueueClear(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;//定位队头节点
	while (cur != NULL)
	{
		QNode* next = cur->next;
		free(cur);//逐个删除
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueClear(pq);
	//注意不能释放pq，这不是动态开辟的地址，而是栈区的地址，所以清空与销毁没什么区别
}

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

enum //匿名枚举
{
	EXIT,
	PUSH,
	POP,
	FRONT,
	BACK,
	SIZE,
	EMPTY,
	CLEAR
};

void Menu()
{
	printf("*************队列*************\n");
	printf("****1.入队          2.出队****\n");
	printf("****3.队头          4.队尾****\n");
	printf("****5.大小          6.判空****\n");
	printf("****7.清空          0.退出****\n");
	printf("******************************\n");
}

int main()
{
	Queue q;
	QueueInit(&q);
	int select = 0;
	bool flag;
	QDataType value;
	do
	{
		Menu();
		printf("请选择您的操作：");
		scanf("%d", &select);
		switch (select)
		{
		case EXIT:
			printf("退出队列！\n");
			break;
		case PUSH:
			printf("请输入您要入队的值：");
			scanf("%d", &value);
			QueuePush(&q, value);
			break;
		case POP:
			QueuePop(&q);
			break;
		case FRONT:
			value = QueueFront(&q);
			printf("队头元素值为：%d\n", value);
			break;
		case BACK:
			value = QueueBack(&q);
			printf("队尾元素值为：%d\n", value);
			break;
		case SIZE:
			printf("队列的大小为：%d\n", QueueSize(&q));
			break;
		case EMPTY:
			flag = QueueEmpty(&q);
			if (flag)
			{
				printf("队列为空！\n");
			}
			else
			{
				printf("队列不为空！\n");
			}
			break;
		case CLEAR:
			QueueClear(&q);
			break;
		default:
			printf("输入错误，请重新输入！\n");
			break;
		}
	} while (select);
	QueueDestory(&q);
	return 0;
}

六.栈和队列必做OJ题

  1. 括号匹配问题
  2. 用队列实现栈
  3. 用栈实现队列

创作不易，如果能帮到你的话能赏个三连吗？感谢啦！！！

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

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

相关文章

解题思路：LeetCode 第 209 题 “Minimum Size Subarray Sum“

解题思路：LeetCode 第 209 题 “Minimum Size Subarray Sum“

解题思路&#xff1a;LeetCode 第 209 题 “Minimum Size Subarray Sum” 在这篇博文中&#xff0c;我们将探讨如何使用 Swift 解决 LeetCode 第 209 题 “Minimum Size Subarray Sum”。我们会讨论两种方法&#xff1a;暴力法和滑动窗口法&#xff0c;并对这两种方法的时间复…
阅读更多...
confluence集成LDAP

confluence集成LDAP

一、confluence的权限管理 在集成前&#xff0c;我们必须得知道confluence自身的权限管理是如何做的。 用户组对应空间权限&#xff0c;用户组可以是一个项目&#xff0c;也可以是一个部门或组。 一个用户组里的用户&#xff0c;可以读写本空间的页面&#xff0c;而把其他组隔离…
阅读更多...
“文本比对基础：最短编辑距离算法的原理与实现“

“文本比对基础：最短编辑距离算法的原理与实现“

最短编辑距离 给定两个字符串 &#x1d434; 和 &#x1d435;&#xff0c;现在要将 &#x1d434; 经过若干操作变为 &#x1d435;&#xff0c;可进行的操作有&#xff1a; 删除–将字符串 &#x1d434; 中的某个字符删除。插入–在字符串 &#x1d434; 的某个位置插入某…
阅读更多...
有没有将音频转文字的app？盘点5款高效的音频转文字工具

有没有将音频转文字的app？盘点5款高效的音频转文字工具

在职场的快节奏生活中&#xff0c;时间就是金钱&#xff0c;效率就是生命。 我们常常在会议中奋笔疾书&#xff0c;却错过了关键的讨论&#xff1b;在电话会议中努力记忆要点&#xff0c;却难以捕捉每一个细节。 但别担心&#xff0c;有一种工具能让我们摆脱这些困扰——音频…
阅读更多...
靶机渗透之DC-8

靶机渗透之DC-8

一、信息收集 扫一下子网段&#xff0c;发现靶机ip为192.168.145.130。 nmap -sP 192.168.145.* 进一步进行端口、系统等信息扫描&#xff0c;开放的端口为80、22&#xff0c;中间件为apache。 nmap -sT -T4 -sV -O -sC -p1-65535 192.168.145.130 再扫一下网站目录&#xf…
阅读更多...
【方法分享】如何使用WinRAR将文件夹里的每个文件压缩

【方法分享】如何使用WinRAR将文件夹里的每个文件压缩

不知道大家是否会遇到这种情况&#xff0c;将文件夹内的多个文件或文件夹压缩成一个个压缩包文件&#xff0c;这种情况除了将文件夹中的文件一个个压缩&#xff0c;还有什么批量操作的方法呢&#xff1f;今天分享使用WinRAR批量压缩文件到每个单独的文件夹的方法。 方法如下&a…
阅读更多...
一键vmp加固apk aar aab

一键vmp加固apk aar aab

简介 最近工作需要基于vpm加固封装了一套一键加固的方案,可以给apk aar aab文件实现一键加固&#xff0c;把所有的dex内容都封装到so库里面&#xff0c;加大了反编译破解的难度。 环境配置: 需要配置环境变量: ANDROID_NDK_HOME ANDROID_SDK_HOME CMAKE_PATH JAVA_HOME使用方…
阅读更多...
高考填报志愿，是选就业前景？还是选自己的兴趣爱好？

高考填报志愿，是选就业前景？还是选自己的兴趣爱好？

一、 当前的就业形式 受yi情影响&#xff0c;全国的就业处于下滑趋势&#xff0c;互联网和实体企业呈现疲软势态&#xff0c;很多企业不得不裁员。大学毕业生人数几乎每年都会上涨&#xff0c;带来的是僧多粥少的就业状态。 考得好不如报得好 就业环境如此严峻的形势下&#…
阅读更多...
如何实现数字人系统私有化部署？数字人源码部署教程简易版来了！

如何实现数字人系统私有化部署？数字人源码部署教程简易版来了！

当前&#xff0c;数字人行业的市场前景和应用潜力不断显现&#xff0c;不少创业者都想要通过学习数字人源码部署教程来搭建属于自己的数字人系统&#xff0c;以此获得进军数字人行业的入场券。而事实上&#xff0c;该想法本身当然是固然值得鼓励的&#xff0c;但就目前的实践情…
阅读更多...
深度学习Week18——学习残差网络和ResNet-50算法

深度学习Week18——学习残差网络和ResNet-50算法

文章目录 深度学习Week18——学习残差网络和ResNet-50算法 一、前言 二、我的环境 三、前期工作 1、配置环境 2、导入数据 2.1 加载数据 2.2 配置数据集 2.3 数据可视化 2.4 再次检查数据 四、构建ResNet-50网络模型 五、编译模型 六、训练模型 七、模型评估 八、指定图片预测 …
阅读更多...
超详细的Stable Diffusion WebUI 安装！

超详细的Stable Diffusion WebUI 安装！

前言 安装方式&#xff1a; 使用发行包在带有 NVidia-GPU 的 Windows 10/11 上安装 sd.webui.zip从v1.0.0-pre下载并解压其内容。 跑步update.bat。 跑步run.bat。 Windows 上自动安装 安装Python 3.10.6&#xff08;较新版本的Python不支持torch&#xff09;&#xff0…
阅读更多...
stm32cubemx，adc采样的几种方总结，触发获取adc值的方法dma timer trigger中断

stm32cubemx，adc采样的几种方总结，触发获取adc值的方法dma timer trigger中断

stm32cubemx adc采样的几种方总结&#xff0c;触发获取adc值的方法 timer trigger中断 方法1&#xff0c;软件触发方法2&#xff1a;,Timer触发ADC采集通过DMA搬运 触发获取adc值的方法 Regular Conversion launched by software 软件触发 调用函数即可触发ADC转换 Timer X Cap…
阅读更多...
英伟达GB200系列AI芯片供不应求；阿里云通义灵码上线Visual Studio插件市场

英伟达GB200系列AI芯片供不应求；阿里云通义灵码上线Visual Studio插件市场

&#x1f989; AI新闻 &#x1f680; 英伟达GB200系列AI芯片供不应求 摘要&#xff1a;英伟达GB200系列AI芯片供不应求&#xff0c;台积电和日月光等公司获追加订单。GB200芯片性能提升30倍&#xff0c;成本和能耗降至25分之一。预计2025年出货量突破百万颗&#xff0c;后段封…
阅读更多...
收藏 | SSL证书无效的原因和解决办法

收藏 | SSL证书无效的原因和解决办法

当浏览器访问一个使用SSL证书保护的网站时&#xff0c;会检查其证书的有效性。如果发现证书存在问题&#xff0c;浏览器会显示“SSL证书无效”的警告信息&#xff0c;提醒用户存在潜在的安全风险。 “SSL证书无效”的警告可能会导致用户离开站点&#xff08;并且永远不会返回&…
阅读更多...
72V转12V非隔离DC/DC电源原理图+PCB源文件

72V转12V非隔离DC/DC电源原理图+PCB源文件

资料下载地址&#xff1a;72V转12V非隔离DCDC电源原理图PCB源文件 电动车所用的非隔离DC/DC电源&#xff0c;采用BUCK电路&#xff0c;运行稳定&#xff0c;为已经在产品中使用的电路 1、原理图 2、PCB
阅读更多...
Cryptographic algorithms—(Green-Book)加密算法

Cryptographic algorithms—(Green-Book)加密算法

Cryptographic algorithms—加密算法 9.2.3 加密算法9.2.3.1 概述9.2.3.2 哈希函数9.2.3.3 对称密钥算法9.2.3.3.1 概述9.2.3.3.2 加密和解密9.2.3.3.3 高级加密标准9.2.3.3.4 加密操作模式9.2.3.3.5 消息认证码9.2.3.3.6 密钥包装9.2.3.3.7 Galois/Counter Mode9.2.3.3.7.1 概…
阅读更多...
星星历c++

星星历c++

题目描述 不管是基于太阳的阳历&#xff0c;还是基于月亮的阴历&#xff0c;或者阴阳合历的农历&#xff0c;都太复杂了。 XXX自己发明了一套历法&#xff0c;取名为“星星历”。星星历采用每年 3 星&#xff0c;每星 120 天的方式纪年。 XXX定义现实的 2024 年 1 月 18 日为…
阅读更多...
CVPR讲座总结(二)-探索图像生成基础模型的最新进展探索多模态代理的最新进展：从视频理解到可操作代理

CVPR讲座总结(二)-探索图像生成基础模型的最新进展探索多模态代理的最新进展：从视频理解到可操作代理

引言 在CVPR24上的教程中&#xff0c;微软高级研究员Linjie Li为我们带来了多模态代理的深入探索。这些代理通过整合多模态专家和大语言模型&#xff08;LLM&#xff09;来增强感知、理解和生成能力。本文总结了Linjie Li的讲座内容&#xff0c;重点介绍了多模态记忆、可操作代…
阅读更多...
碳课堂｜ISO 14064标准新版变化

碳课堂｜ISO 14064标准新版变化

ISO 14064标准是针对组织碳排放方面的管理标准&#xff0c;包括温室气体排放和清除的量化、报告与验证的国际标准。其最新版本于 2018年发布&#xff0c;标志着对温室气体管理的全球认知和实践的进一步演进。ISO 14064 作为 ISO 14060 标准系列的重要组成部分&#xff0c;将继续…
阅读更多...
C语言 指针——缓冲区溢出与缓冲区溢出攻击

C语言 指针——缓冲区溢出与缓冲区溢出攻击

目录 缓冲区溢出攻击 缓冲区溢出攻击实例 字符串的安全输入方法​编辑 防止缓冲区溢出的两个要点 缓冲区溢出攻击 网络黑客常针对系统和程序自身存在的漏洞&#xff0c;编写相应的攻击程序  对缓冲区溢出漏洞的攻击 —— 最常见  几乎占到了网络攻击次数的一半以上…
阅读更多...
最新文章

Copyright @ 2022~2023