（超详细）数据结构——“队列”的深度解析

 

目录

 

前言：

1.队列的概念   

2.队列的实现 

3.代码实现队列 

3.1 队列的初始化 

3.2 插入 

3.3 删除 

3.4 队列的队头，队尾和大小

3.5 判空 

3.6 销毁 

3.7 测试 

 

前言：

    队列与栈都是线性表，它们的结构也非常类似，都是一头进一头出，那么它们有什么区别吗？答案是有的，虽然它们同为线性表，但是栈的出栈入栈方式为后进先出，而队列的出栈入栈方式为先进先出，具体我们在正文讲解。

1.队列的概念   

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

2.队列的实现 

    队列与栈的结构类似，所以它和栈一样，使用链表和顺序表都可以实现队列，但是由于队列遵循先进先出的顺序，如果使用顺序表进行头删实现出队列的话，整个队列的数据需要频繁向前移动，代码效率相对较低，而使用链表的头删实现出队列的话，只需要将头节点删除即可，所以综上所述，我们将使用链表来实现队列。

3.代码实现队列 

    为了方便管理，我们还是将队列分为三个文件实现，分别是Queue.h （queue中译是队列的意思），Queue.c和test.c，由于我们选择使用链表实现队列，所以我们要先使用结构体实现一个单链表的节点，这个节点包含数据和下一个节点的地址，存储数据变量的类型由我们将来要存储的数据决定，所以我们使用typedef队对数据类型进行改名，在这里我们将int作为测试类型，所以我们要对int重命名：

typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;


}QNode;

   基于队列先进先出的原则，我们需要得到队列的头和尾，必要时还需要知道队列的大小，所以我们额外创建一个结构体来存储队列的首地址，尾地址和队列的大小：

typedef struct Queue
{
	QNode* Qtail;
	QNode* Qhead;
	int size;

}Queue;

3.1 队列的初始化 

   我们现在有两个结构体，我们该如何初始化呢？是对两个结构体都初始化，还是对其中某一个初始化呢。答案是对存储有队列首地址和尾地址的结构体初始化，因为代表链表节点的QNode结构体的初始化是在我们在堆上开辟新的空间时初始化，所以我们这个时候的初始化是对Queue初始化：

void QInit(Queue* pq)
{
	assert(pq);
	pq->Qhead = pq->Qtail = NULL;
	pq->size = 0;

}//初始化

3.2 插入 

    我们这里的队列使用的是单链表，所以插入要使用尾插，删除使用头插，单链表的这两个操作完美的符合队列的先进先出的特性。在插入数据前，我们要先开辟一个新节点，如果这个节点有效，我们就对它初始化，让它的next指针指向空，将x赋给val。将新节点初始化完了之后，我们就要考虑插入的问题了，如果队列里没有任何成员，我们要插入的新节点就要同时赋给头指针和尾指针，如果队列里有成员，我们插入的新节点就只需要给尾指针的next指针，执行完插入操作后让size加1：

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->Qhead == NULL)
	{
		pq->Qhead = pq->Qtail = newnode;
	}
	else
	{
		pq->Qtail->next = newnode;
		pq->Qtail = newnode;
	}
	pq->size++;
}//插入

3.3 删除 

    删除操作我们在前面讲过要使用头删，我们需要考虑队列是否为空，如果队列为空，则让程序无法执行删除操作，我们选择使用断言来限制队列为空使用删除的情况，与插入相同，我们需要考虑两种情况，如果队列中只有只有一个成员，那么这个成员同时被头指针和尾指针指着，如果我们要删除这个节点，那么我们要将头指针和尾指针同时置空，这样做是为了防止出现空指针的现象。第二种则是正常情况，我们用一个指针存储头指针的下一个节点的地址，将头指针指向的那块空间释放后（删除节点），再让头指针指向我们之前存储的地址，这样删除操作就算完成了：

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->Qhead);

	if (pq->Qhead->next == NULL)
	{
		free(pq->Qhead);
		pq->Qhead = pq->Qtail = NULL;
	}
	else
	{
		QNode* next = pq->Qhead->next;
		free(pq->Qhead);
		pq->Qhead = next;
	}
	pq->size--;
}//删除

3.4 队列的队头，队尾和大小

  队列的队头和队尾只需要将头指针和尾指针指向成员的值返回就可以了，而队列的大小也比较简单，只需要返回size就可以了：

队头：

DataType QueueFront(Queue* pq)
{
	assert(pq);
	return pq->Qhead->val;
}

队尾：

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	return pq->Qtail->val;
}

队列大小：

int Queuesize(Queue* pq)
{
	assert(pq);
	assert(pq->size >= 0);
	return pq->size;
}//大小

3.5 判空 

  我们有时会频繁对队列进行删除插入操作，这时我们可以使用这个方法来决定是否删除，如果队列为空，则不进行删除操作：

bool QEmpty(Queue* pq)
{
	assert(pq);
	assert(pq->size >= 0);
	return pq->size == 0;
}//判空

3.6 销毁 

  我们链表的节点都是从堆上开辟的，所以要手动将这些空间释放：

void QDestroy(Queue* pq)
{
	assert(pq);
	Queue* cur = pq->Qhead;

	while (cur)
	{
		QNode* next = cur->Qhead->next;
		free(cur->Qhead);
		cur->Qhead = next;
	}
	pq->Qhead = pq->Qtail = NULL;
	pq->size = 0;
}

3.7 测试 

  到这里队列所有的方法都已经实现了，实现完之后不要忘记测试一下代码的有效性，我们来测试一下我们实现的方法：

我们插入了四个数字，然后使用判空，队头和删除方法来打印队列，可以看到都是没有问题的，讲到这里，队列就到此结束了，代码放在下面，感兴趣的小伙伴可以试试哦。

Queue.h :

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

typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;


}QNode;

typedef struct Queue
{
	QNode* Qtail;
	QNode* Qhead;
	int size;

}Queue;

void QInit(Queue* pq);//初始化

void QueuePush(Queue* pq, QDataType x);//插入

void QueuePop(Queue* pq);//删除

int Queuesize(Queue* pq);//大小

//头尾数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
//判空
bool QEmpty(Queue* pq);

void QDestroy(Queue* pq);//销毁

Queue.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"

void QInit(Queue* pq)
{
	assert(pq);
	pq->Qhead = pq->Qtail = 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->Qhead == NULL)
	{
		pq->Qhead = pq->Qtail = newnode;
	}
	else
	{
		pq->Qtail->next = newnode;
		pq->Qtail = newnode;
	}
	pq->size++;
}//插入

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->Qhead);

	if (pq->Qhead->next == NULL)
	{
		free(pq->Qhead);
		pq->Qhead = pq->Qtail = NULL;
	}
	else
	{
		QNode* next = pq->Qhead->next;
		free(pq->Qhead);
		pq->Qhead = next;
	}
	pq->size--;
}//删除

int Queuesize(Queue* pq)
{
	assert(pq);
	assert(pq->size >= 0);
	return pq->size;
}//大小

//头、尾数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	return pq->Qhead->val;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	return pq->Qtail->val;
}

bool QEmpty(Queue* pq)
{
	assert(pq);
	assert(pq->size >= 0);
	return pq->size == 0;
}//判空

void QDestroy(Queue* pq)
{
	assert(pq);
	Queue* cur = pq->Qhead;

	while (cur)
	{
		QNode* next = cur->Qhead->next;
		free(cur->Qhead);
		cur->Qhead = next;
	}
	pq->Qhead = pq->Qtail = NULL;
	pq->size = 0;
}

test.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void test()
{
	Queue q;
	QInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);


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

	QDestroy(&q);

}
int main()
{
	test();
	return 0;
}

 

 

 

 

 

 

 

 

 

 

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

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

相关文章

备份SQL Server数据库并还原到另一台服务器

备份SQL Server数据库并还原到另一台服务器

我可以将SQL Server数据库备份到另一台服务器吗&#xff1f; 有时您可能希望将 SQL数据库从一台服务器复制到另一台服务器&#xff0c;或者将计算机复制到计算机。可能的场景包括测试、检查一致性、从崩溃的机器恢复数据库、在不同的机器上处理同一个项目等。 是的&#xff0c…
阅读更多...
DevExpress WinForms磁贴导航面板 TileBar组件，让桌面应用触摸更友好！

DevExpress WinForms磁贴导航面板 TileBar组件，让桌面应用触摸更友好！

界面控件DevExpress WinFormsTileNavPane被设计为位于应用程序窗口的顶部(就像Ribbon一样)&#xff0c;可以被认为是Windows桌面应用程序中传统导航元素的触摸友好版本。 P.S&#xff1a;DevExpress WinForms拥有180组件和UI库&#xff0c;能为Windows Forms平台创建具有影响力…
阅读更多...
使用高斯混合模型识别餐厅热点

使用高斯混合模型识别餐厅热点

使用 GMM 识别加拿大多伦多的直观餐厅集群&#xff08;附 Python 代码&#xff09; 聚类算法&#xff08;例如 GMM&#xff09;是一种有用的工具&#xff0c;可帮助识别数据中的模式。它们使我们能够识别数据集中的子组&#xff0c;从而提高你的理解或增强预测模型。在本文中&a…
阅读更多...
LVM核心概念

LVM核心概念

1. LVM简介 LVM是逻辑盘卷管理&#xff08;Logical Volume Manager&#xff09;的简称&#xff0c;它是Linux环境下对磁盘分区进行管理的一种机制&#xff0c;LVM是建立在硬盘和分区之上的一个逻辑层&#xff0c;来提高磁盘分区管理的灵活性。 优点&#xff1a; 可以灵活分配…
阅读更多...
postgresql命令行基本操作指令

postgresql命令行基本操作指令

文章目录 前言一、psql下载安装二、未配置环境变量连接方式1.可视化工具2. 命令行操作连接到postgreSQL 三、配置环境变量四、常用操作指令1. 连接数据库2. 查看数据库3. 创建数据库4. 切换数据库5. 创建数据库表结构6. 查看表结构7. 查看所有的表8. 插入数据9. 查看数据10. 更…
阅读更多...
YOLOv8改进 | 主干网络 | C2f融合动态卷积模块ODConv

YOLOv8改进 | 主干网络 | C2f融合动态卷积模块ODConv

&#x1f4a1;&#x1f4a1;&#x1f4a1;本专栏所有程序均经过测试&#xff0c;可成功执行&#x1f4a1;&#x1f4a1;&#x1f4a1; 专栏目录 &#xff1a;《YOLOv8改进有效涨点》专栏介绍 & 专栏目录 | 目前已有40篇内容&#xff0c;内含各种Head检测头、损失函数Loss、…
阅读更多...
Open3D 点云CPD算法配准（粗配准）

Open3D 点云CPD算法配准（粗配准）

目录 一、概述 二、代码实现 2.1关键函数 2.2完整代码 三、实现效果 3.1原始点云 3.2配准后点云 一、概述 在Open3D中&#xff0c;CPD&#xff08;Coherent Point Drift&#xff0c;一致性点漂移&#xff09;算法是一种经典的点云配准方法&#xff0c;适用于无序点云的非…
阅读更多...
Top 5 免费 PDF 转 Word 转换工具

Top 5 免费 PDF 转 Word 转换工具

PDF 是可移植文档格式的缩写&#xff0c;是一种文件格式&#xff0c;用于独立于软件、硬件或操作系统可靠地呈现和交换文档。PDF 不是为编辑而设计的&#xff0c;因此如果您想更改某些内容&#xff0c;可能需要将 PDF 转换为 Word/Doc 转换器。 Top 5 免费 PDF 转 Word 转换工具…
阅读更多...
OFDM关键技术——ICI消除技术

OFDM关键技术——ICI消除技术

ICI消除算法可以分为以下几类&#xff1a; 1、OFDM符号长度和载波间隔的最优选择&#xff0c;较短的符号周期更有利于降低ICI 2、OFDM基信号的最佳选择&#xff0c;选择频域衰减更快的OFDM基带脉冲 3、自干扰消除技术&#xff0c;将信息调制到一组子载波上 4、频域均衡器&a…
阅读更多...
电影交流平台小程序的设计

电影交流平台小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;电影类型管理&#xff0c;留言反馈管理&#xff0c;电影中心管理&#xff0c;系统管理 微信端账号功能包括&#xff1a;系统首页&#xff0c;电影中心&#xff0c;留言反馈 开发系统&#xff1a;Window…
阅读更多...
Rust Eq 和 PartialEq

Rust Eq 和 PartialEq

Eq 和 PartialEq 在 Rust 中&#xff0c;想要重载操作符&#xff0c;你就需要实现对应的特征。 例如 <、<、> 和 > 需要实现 PartialOrd 特征: use std::fmt::Display;struct Pair<T> {x: T,y: T, }impl<T> Pair<T> {fn new(x: T, y: T) ->…
阅读更多...
iptable精讲

iptable精讲

SNAT策略 SNAT策略的典型应用环境 局域网主机共享单个公网IP地址接入Internet SNAT策略的原理 源地址转换&#xff0c;Source Network Address Translantion 修改数据包的源地址 部署SNAT策略 1.准备二台最小化虚拟机修改主机名 主机名&#xff1a;gw 主机名&#xff1…
阅读更多...
WPF布局控件

WPF布局控件

目录 Grid StackPanel WrapPanel DockPanel UniformGrid Canvas&InkCanvas Canvas InkCanvas Border Grid 属性 ShowGridLines&#xff1a;显示边线 ColumnDefinitions 列集合 表示有几列下面就写几个ColumnDefinition Width 宽&#xff1a;如果写具体数字则表…
阅读更多...
【面试题】IPS（入侵防御系统）和IDS（入侵检测系统）的区别

【面试题】IPS（入侵防御系统）和IDS（入侵检测系统）的区别

IPS&#xff08;入侵防御系统&#xff09;和IDS&#xff08;入侵检测系统&#xff09;在网络安全领域扮演着不同的角色&#xff0c;它们之间的主要区别可以归纳如下&#xff1a; 功能差异&#xff1a; IPS&#xff1a;这是一种主动防护设备&#xff0c;不仅具备检测攻击的能力&…
阅读更多...
UNet进行病理图像分割

UNet进行病理图像分割

数据集链接&#xff1a;https://pan.baidu.com/s/1IBe_P0AyHgZC39NqzOxZhA?pwdnztc 提取码&#xff1a;nztc UNet模型 import torch import torch.nn as nnclass conv_block(nn.Module):def __init__(self, ch_in, ch_out):super(conv_block, self).__init__()self.conv nn…
阅读更多...
JVM原理（十）：JVM虚拟机调优分析与实战

JVM原理（十）：JVM虚拟机调优分析与实战

1. 大内存硬件上的程序部署策略 这是笔者很久之前处理过的一个案例&#xff0c;但今天仍然具有代表性。一个15万PV/日左右的在线文档类型网站最近更换了硬件系统&#xff0c;服务器的硬件为四路志强处理器、16GB物理内存&#xff0c;操作系统为64位CentOS5.4&#xff0c;Resin…
阅读更多...
Android Studio 解决AAPT: error: file failed to compile

Android Studio 解决AAPT: error: file failed to compile

1.找到项目下的build.gradle 2.在android语块中添加下面代码 aaptOptions.cruncherEnabled false aaptOptions.useNewCruncher false 12
阅读更多...
Linux中的库

Linux中的库

什么是库&#xff1f; 库是一组预先编译好的方法/函数的集合&#xff0c;其他程序想要使用源文件中的函数时&#xff0c;只需在编译可执行程序时&#xff0c;链接上该源文件生成的库文件即可。 库分为两类&#xff1a;静态库和动态库 在Linux系统中&#xff0c;以.a为后缀的…
阅读更多...
力扣热100 哈希

力扣热100 哈希

哈希 1. 两数之和49.字母异位词分组128.最长连续序列 1. 两数之和 题目&#xff1a;给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数&#xff0c;并返回它们的数组下标。你可以假设每种输入只会对应一个答案。…
阅读更多...
【NOI-题解】1326. 需要安排几位师傅加工零件1228. 排队打水问题1229. 拦截导弹的系统数量求解

【NOI-题解】1326. 需要安排几位师傅加工零件1228. 排队打水问题1229. 拦截导弹的系统数量求解

文章目录 一、前言二、问题问题&#xff1a;1326. 需要安排几位师傅加工零件问题&#xff1a;1228. 排队打水问题问题&#xff1a;1229. 拦截导弹的系统数量求解 三、感谢 一、前言 本章节主要对贪心问题进行讲解&#xff0c;包括《1326. 需要安排几位师傅加工零件》《1228. 排…
阅读更多...
最新文章

Copyright @ 2022~2023