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

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

更多有关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#include#include#includetypedef 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;}