C语言队列的含义与队列数据操作代码详解！

2024-05-09 19:37
算法, c语言, 开发语言
49人已看

引言：于本篇博客当中，我们将讲到数据结构——队列的有关知识。而对于这次的队列，我们将会在单链表的基础上实现。

更多有关C语言和数据结构知识详解可前往个人主页：计信猫

一，队列的含义

队列是一种特殊的线性表，它只允许在表的一端进行插入数据的操作，另一端进行删除数据的操作。

队头：进行数据删除的一端

队尾：进行数据插入的一端

所以，队列便可以用如下的图进行表示：

而正因为队列遵循FIFO原则（即先进先出），使得入队列与出队列的顺序一一对应，也就多被应用于广度优先遍历的操作。

二，队列结构体的定义

老样子，我们仍然使用三文件操作法，分别创建Queue.h、Queue.c、test.c三个文件。

因为先前提到，队列会在单链表的基础上实现，那么我们就需要先定义一个单链表结构体：

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

但是，因为在队列之中，我们只需要关注队列中队头和队尾的两个节点即可，并且为了避免二级指针的使用难以理解，所以我们选择再定义一个结构体Queue用于储存队列的队头和队尾两节点。

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;//记录队列中的节点个数
}Queue;

包含可能用到的头文件后，我们的Queue.h的代码内容如下：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;//记录队列中的节点个数
}Queue;

三，队列数据操作函数

1，队列的初始化

队列的初始化与其他数据结构的初始化别无它异，我们只需要将结构体中的指针类型初始化为NULL，整型类型初始化为0就可以了。直接上代码：

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

2，队列的尾插

对于队列的尾插，其实也就和单链表的尾插一模一样。我们只需要使用malloc函数申请一个节点的空间，然后将新创建的节点连在队列的尾部，同时将ptail指针移到新形成的队尾，最后的最后，一定不要忘记size++。这样，一个队列的尾插函数就成功写出了。

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建新节点
	if (newnode == NULL)
	{
		perror("malloc fail!");
		return;
	}
	newnode->next = NULL;
	newnode->val = data;
	//队列元素为0个时
	if (q->ptail == NULL)
	{
		q->phead = q->ptail = newnode;
	}
	//队列有元素时
	else
	{
		q->ptail->next = newnode;
		q->ptail = newnode;
	}
	q->size++;
}

3，队列的头删

因为队列只可以在队头进行数据删除，所以队列就只有一个头删函数。

如上图所示，对于队列的头删函数，我们需要首先创建节点结构体指针next记录队头的下一个节点的地址，以免队头被free掉之后导致的后续节点的丢失，然后我们再将phead指针赋值为next，最后再进行size--即可。

但是有一个特殊情况，当队列只有一个节点的时候，我们进行队列的头删之后，ptail则会变成野指针，这时候我们就需要特殊处理，将ptail也赋值为NULL，防止野指针的出现。如图：

综上所述，我们的队列头删函数如下：

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->size > 0);
	QNode* next = q->phead->next;
	free(q->phead);
	q->phead = next;
	//特殊情况：队列只有一个节点的时候
	if (q->phead == NULL)
	{
		q->ptail = NULL;
	}
	//勿忘size--
	q->size--;
}

4，获取队列头部数据

这时候，我们所创建的Queue结构体就派上大用场了，因为这个结构体直接就保存了我们的phead节点，所以我们直接使用就可以了。代码如下：

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->phead);
	return q->phead->val;
}

5，获取队列尾部数据

那么这个函数，也就跟前一个函数相差不大了。都是直接使用Queue结构体就可以了，我们直接上代码：

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->ptail);
	return q->ptail->val;
}

6，获取队列有效元素个数

在Queue结构体中，我们早就使用了size来记录有效元素的个数，所以我们直接返回size的值即可。

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}

7，判断队列是否为空

该函数的返回值为布尔类型，即true和false。

队列为空，返回：true

队列不为空，返回：false

对于队列是否为空，我们只需要判断size是否为零就可以了。所以代码如下：

// 检测队列是否为空
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
	//若size等于零，则表达式为真，则队列为空
	//若size不等于零，则表达式为假，则队列为假
}

8，队列的销毁

因为我们创建队列时使用了malloc函数，故为了防止内存溢出，我们需要创建一个队列的销毁函数，来完成释放队列申请的空间的操作。

在该函数中，我们需要再创建一个QNode结构体指针cur用于保存即将被释放的节点的下一个节点的地址，以防止地址的丢失，然后再使用free函数释放掉节点即可。最后的最后，勿忘将size置为零。

所以我们的代码如下：

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* next = q->phead;
	while (next)
	{
		QNode* cur = next->next;
		free(next);
		cur = next;
	}
	q->size = 0;
}