深入了解队列：探索FIFO数据结构及队列

是Nero哦

发布于 2024-01-18 18:42:07

910

发布于 2024-01-18 18:42:07

文章被收录于专栏：c/c++学习与分享c/c++学习与分享

之前介绍了栈：探索栈数据结构：深入了解其实用与实现（c语言实现栈）

那就快马加鞭来进行队列内容的梳理。队列和栈有着截然不同的工作方式，队列遵循先进先出（FIFO）的原则，在许多场景下都表现出强大的效率和实用性

源码可以来我的github进行查找：Nerosts/just-a-try: 学习c语言的过程、真 (github.com)

1.队列的概念及结构

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

假设入队：A B C D

那么出队：A B C D

2.队列的实现

队列也可以数组和链表的结构实现，使用链表的结构来实现更适合一些，因为使用数组的结构，出队列这个操作在数组头上出数据（届时会需要全体移动），效率会比较低

2.1项目文件规划

头文件Queue.h:用来基础准备（常量定义，typedef），链表表的基本框架，函数的声明
源文件Queue.c:用来各种功能函数的具体实现
源文件test.c:用来测试功能是否有问题，进行基本功能的使用

2.2基本结构及各功能（Queue.h）

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

typedef int QDataType;

typedef struct QueueNode//节点的结构体
{
	QDataType val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size; //元素数量（空间换时间）
}Queue;

void QInit(Queue* q);//初始化
void QDestroy(Queue* q);//销毁

void QPush(Queue* q, QDataType x);//插入
void QPop(Queue* q);//删除

QDataType QBack(Queue* q);//返回最后一个节点数据
QDataType QFront(Queue* q);//返回第一个节点数据

bool QEmpty(Queue* q);//是否为空

int QSize(Queue* q);//元素数量

这两个结构体组合在一起，构成了队列数据结构的基本框架。

QNode 结构体用于表示队列中的节点
Queue 结构体则用于管理整个队列的状态和属性这种设计使得队列的操作和功能得以清晰地表现和实现

2.3各功能具体实现（Queue.c）

初始化

void QInit(Queue* q)
{
	assert(q);
	q->phead = q->ptail = NULL;
	q->size = 0;
}

将队列的头尾指针设置为 NULL，表示队列为空。
将队列中元素的数量设置为 0，因为队列此时没有任何元素

插入

void QPush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);//防止没有开辟成功(当人有点杞人忧天了）
	newnode->val = x;
	newnode->next = NULL;

	if (q->phead == NULL)
	{
		q->phead = q->ptail = newnode;
	}
	else
	{
		q->ptail->next = newnode;
		q->ptail = newnode;
	}
	q->size++;
}

首先使用 assert 确保传入的队列指针 q 是有效的
为新节点 newnode 分配内存，并设置其值为 x，next 指针指向 NULL
如果队列为空（即头尾指针均为空），则将新节点同时设置为队列的头尾节点。
如果队列不为空，则将新节点连接到队列尾部，并更新尾指针 ptail 指向新的尾节点。
最后，增加队列的大小 size。

删除

void QPop(Queue* q)
{
	assert(q);
	assert(q->size > 0);
	QNode* next = q->phead->next;
	free(q->phead);
	q->phead = next;
	//当只有一个节点时：把	q->ptail = NULL;
	if (q->phead == NULL)
	{
		q->ptail = NULL;
	}
	q->size--;
}

首先使用 assert 确保传入的队列指针 q 是有效的，并且队列中有元素即（size > 0）
通过 next 指针将队列头部的下一个节点保存下来，以备后续更新
释放队列当前的头节点
更新队列的头指针为下一个节点（如果有的话）
如果删除节点后队列为空==（只有一个节点），则将尾指针 ptail 也设置为 NULL（一个节点时，二者指向同一个地址）==
最后，减少队列的大小 size

返回最后一个节点数据

QDataType QBack(Queue* q)
{
	assert(q);
	assert(q->ptail);
	return q->ptail->val;
}

返回第一个节点数据

QDataType QFront(Queue* q)
{
	assert(q);
	assert(q->ptail);
	return q->phead->val;
}

是否为空

bool QEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}

节点数量

int QSize(Queue* q)
{
	assert(q);
	return q->size;
}

销毁

void QDestroy(Queue* q)
{
	QNode* cur = q->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->phead = q->ptail = NULL;
	q->size = 0;
}

队列的内容也整理完毕了，下一次会为大家带来二叉树和堆的相关内容，感谢大家的支持！！！

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-01-18，如有侵权请联系 cloudcommunity@tencent.com 删除

队列