【数据结构初阶：链式结构实现队列】

一、队列的概念

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

二、单链表实现队列

• 队列可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，需要把后面所有数据都往前挪一位，效率会比较低。所以这篇文章我们讲解用链表实现队列。

2.1 创建队列结构体

• 我们使用单链表实现队列，所以要先构造一个节点的指针结构体

typedefintQDataType;//便于后面修改存储数据的数据类型//队列节点的结构typedefstructQueueNode{intdata;//存储数据structQueueNode*next;}QueueNode;

• 但这还不够，因为队列的特性是队尾入数据，队头出数据，所以我们还要构造一个队列的结构，定义两个结构体指针，分别指向队头和队尾。

typedefstructQueue{QueueNode*phead;//指向队头，用于出队QueueNode*ptail;//指向队尾，用于入队intsize;//队列中有效数据个数}Queue;

2.11 为什么一定要定义两个结构体？定义一个不行吗？

• 理论上来说是可以的

typedefintQDataType;//便于后面修改存储数据的数据类型typedefstructQueueNode{intdata;//存储数据structQueueNode*next，*phead,*ptail;intsize;}QueueNode;

• 但这样写有很多不好的地方
• 1.两个结构体管理更加严格，一个结构体管理类似于单链表，比较松散。单链表可以进行尾插、头插、任意位置上的插入、删除… …但是队列严格要求队尾入，队头出，所以有两个结构体指针管理它们会好一些。
• 2.方便传递参数。如果不构造两个结构体，调用函数时就要用两个参数（phead, ptail）,但是有了Queue把phead和ptail 封装起来就方便了。
• 3.不用使用二级指针了。在单链表的实现中，我们想要对链表中的数据插入删除时都需要传phead或者ptail这类结构体指针的地址，要用二级指针接收，但是现在我们有Queue，只需要访问它的成员phead和ptail就可以了，也就是说只需要Queue的地址，用一级指针接收就可以了。

2.2 初始化队列

//初始化voidQueueInit(Queue*pq){assert(pq);//判断是否传了空指针pq->phead=pq->ptail=NULL;pq->size=0;}

• 队列和栈不同，栈有一个top指向栈顶元素的下标，但是如果想要知道队列的有效数据个数就要从头到尾遍历一遍，为了方便，我们直接用size表示有效数据个数。

2.3队尾入队列

//入队-队尾voidQueuePush(Queue*pq,QDataType x){assert(pq);QueueNode*newnode=(QueueNode*)malloc(sizeof(QueueNode));if(newnode==NULL)//如果节点申请失败，退出程序{perror("malloc fail");return;}//新节点创捷成功，把数据插入，next指针置为空newnode->data=x;newnode->next=NULL;//尾插之前要判断队列是否为空if(pq->phead==NULL)//队列为空{//直接将新节点设置为队列中的第一个节点pq->phead=pq->ptail=newnode;}else//尾插{pq->ptail->next=newnode;pq->ptail=pq->ptail->next;}pq->size++;}

2.31 有必要单独封装一个扩容函数吗

• 没必要，因为队列只有在对尾入数据才会申请新节点。

2.4 队列判空

//队列判空boolQueueEmpty(Queue*pq){assert(pq);returnpq->phead==NULL;}

• 其实这里用size成员也可以，看size的值是否为零，为零则为空返回true，不为零则不为空返回false。

2.5 队头出队列

//出队-队头voidQueuePop(Queue*pq){assert(!QueueEmpty(pq));//只有一个节点时，phead和ptail都置为空if(pq->phead==pq->ptail){free(pq->phead);pq->phead=pq->ptail=NULL;}else//多个节点，直接头删{QueueNode*next=pq->phead->next;free(pq->phead);pq->phead=next;}pq->size--;}

2.6 取队头元素

//取队头数据QDataTypeQueueFront(Queue*pq){assert(!QueueEmpty(pq));//队列为空无队头数据returnpq->phead->data;//队列不为空直接返回phead所指数据}

2.7 取队尾数据

//取队尾数据QDataTypeQueueBack(Queue*pq){assert(!QueueEmpty(pq));returnpq->ptail->data;}

2.8 获取队列中有效数据个数

intQueueSize(Queue*pq){assert(pq);//第一种方式：适用于不用频繁调用队列有效数据个数的场景QueueNode*pcur=pq->phead;intsize=0;while(pcur){size++;pcur=pcur->next;}returnsize;//第二种方式：适用于频繁调用队列有效数据个数的场景returnpq->size--;//我们这篇文章的讲解的定义了size所以直接用第二种就可以。}

• 在这里就显示出我们定义一个size成员的好处了，可以减少代码量并且简洁易懂。上面的代码中也给出了如何通过遍历来获取有效数据个数。

2.9 销毁队列

//销毁队列voidQueueDesytoy(Queue*pq){assert(pq);//逐个释放QueueNode*pcur=pq->phead;while(pcur){QueueNode*next=pcur->next;//定义一个next指针存pcur中的next，防止free（pcur）后找不到下一个节点了free(pcur);pcur=next;}pq->phead=pq->ptail=NULL;pq->size=0;}

• 要注意逐个节点释放，类似于单链表，定义一个next指针存pcur中的next，防止free（pcur）后找不到下一个节点了

三、链表队列实现的全部代码

3.1 Queue.h

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefintQDataType;//队列节点的结构typedefstructQueueNode{intdata;structQueueNode*next;}QueueNode;//队列的结构typedefstructQueue{QueueNode*phead;QueueNode*ptail;intsize;//队列中有效数据个数}Queue;//初始化voidQueueInit(Queue*pq);//入队-队尾voidQueuePush(Queue*pq,QDataType x);//出队-队头voidQueuePop(Queue*pq);//队列判空boolQueueEmpty(Queue*pq);//取队头数据QDataTypeQueueFront(Queue*pq);//取队尾数据QDataTypeQueueBack(Queue*pq);//销毁队列voidQueueInit(Queue*pq);//队列有效元素个数intQueueSize(Queue*pq);

3.2 Queue.c

#include"Queue.h"//初始化voidQueueInit(Queue*pq){assert(pq);pq->phead=pq->ptail=NULL;//pq->size = 0;}//入队-队尾voidQueuePush(Queue*pq,QDataType x){assert(pq);QueueNode*newnode=(QueueNode*)malloc(sizeof(QueueNode));if(newnode==NULL){perror("malloc fail");return;}newnode->data=x;newnode->next=NULL;if(pq->phead==NULL){pq->phead=pq->ptail=newnode;}else{pq->ptail->next=newnode;pq->ptail=pq->ptail->next;}/*pq->size++;*/}//出队-队头voidQueuePop(Queue*pq){assert(!QueueEmpty(pq));//只有一个节点时，phead和ptail都置为空if(pq->phead==pq->ptail){free(pq->phead);pq->phead=pq->ptail=NULL;}else{QueueNode*next=pq->phead->next;free(pq->phead);pq->phead=next;}/*pq->size--;*/}//队列判空boolQueueEmpty(Queue*pq){assert(pq);returnpq->phead==NULL;}//取队头数据QDataTypeQueueFront(Queue*pq){assert(!QueueEmpty(pq));returnpq->phead->data;}//取队尾数据QDataTypeQueueBack(Queue*pq){assert(!QueueEmpty(pq));returnpq->ptail->data;}//销毁队列voidQueueDesytoy(Queue*pq){assert(pq);QueueNode*pcur=pq->phead;while(pcur){QueueNode*next=pcur->next;free(pcur);pcur=next;}pq->phead=pq->ptail=NULL;pq->size=0;}//队列有效元素个数intQueueSize(Queue*pq){assert(pq);//第一种方式：适用于不用频繁调用队列有效数据个数的场景QueueNode*pcur=pq->phead;intsize=0;while(pcur){size++;pcur=pcur->next;}returnsize;//第二种方式：适用于频繁调用队列有效数据个数的场景/*return pq->size--;*/}

3.3 test.c

#include"Queue.h"voidtest01(){Queue q;QueueInit(&q);QueuePush(&q,1);QueuePush(&q,2);QueuePush(&q,3);QueuePush(&q,4);QueuePush(&q,5);while(!QueueEmpty(&q)){printf("%d ",QueueFront(&q));QueuePop(&q);}}intmain(){test01();return0;}

• 需要注意，队列是不适合被打印的，因为打印需要遍历队列，而队列是队头出的性质，所以要遍历的话就要一边取队头元素，一边出队头元素，降低了复用性，导致数据丢失。

四、队列在生活里的运用

1.生活排队

• 银行窗口、食堂打饭、医院挂号、排队安检，先来先服务。

2.计算机任务调度

• 操作系统进程排队、线程任务队列、打印机任务排队，按顺序执行。

3.广度优先搜索 BFS

• 二叉树层序遍历、图的广度遍历、迷宫寻路，都要用队列存待访问节点。

4.缓冲区缓冲

• 键盘输入缓冲区、网络数据收发缓冲区、音视频数据流缓存。

5.消息队列

• 电商订单消息、直播弹幕、聊天软件消息转发，异步排队处理。

五、总结

• 队列是一种线性数据结构，遵循先进先出的规则，只能在队尾添加元素，在队头删除元素，不允许在中间位置进行插入、删除操作。它主要用于处理按先后顺序执行的任务，能够实现排队等待、依次处理的逻辑，是编程中常用的基础存储结构。