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

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

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

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

文章目录

• 1.队列的概念及结构
• 2.队列的实现
• • 2.1项目文件规划
  • 2.2基本结构及各功能（Queue.h）
  • 2.3各功能具体实现（Queue.c）
  • • 初始化
    • 插入
    • 删除
    • 返回最后一个节点数据
    • 返回第一个节点数据
    • 是否为空
    • 节点数量
    • 销毁

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;
}

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