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

数据结构初阶链式结构实现队列一、队列的概念二、单链表实现队列2.1 创建队列结构体2.11 为什么一定要定义两个结构体定义一个不行吗2.2 初始化队列2.3队尾入队列2.31 有必要单独封装一个扩容函数吗2.4 队列判空2.5 队头出队列2.6 取队头元素2.7 取队尾数据2.8 获取队列中有效数据个数2.9 销毁队列三、链表队列实现的全部代码3.1 Queue.h3.2 Queue.c3.3 test.c四、队列在生活里的运用五、总结一、队列的概念概念只允许在一端进行插入数据操作在另⼀端进行删除数据操作的特殊线性表队列具有先进先出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-pheadpq-ptailNULL;pq-size0;}队列和栈不同栈有一个top指向栈顶元素的下标但是如果想要知道队列的有效数据个数就要从头到尾遍历一遍为了方便我们直接用size表示有效数据个数。2.3队尾入队列//入队-队尾voidQueuePush(Queue*pq,QDataType x){assert(pq);QueueNode*newnode(QueueNode*)malloc(sizeof(QueueNode));if(newnodeNULL)//如果节点申请失败退出程序{perror(malloc fail);return;}//新节点创捷成功把数据插入next指针置为空newnode-datax;newnode-nextNULL;//尾插之前要判断队列是否为空if(pq-pheadNULL)//队列为空{//直接将新节点设置为队列中的第一个节点pq-pheadpq-ptailnewnode;}else//尾插{pq-ptail-nextnewnode;pq-ptailpq-ptail-next;}pq-size;}2.31 有必要单独封装一个扩容函数吗没必要因为队列只有在对尾入数据才会申请新节点。2.4 队列判空//队列判空boolQueueEmpty(Queue*pq){assert(pq);returnpq-pheadNULL;}其实这里用size成员也可以看size的值是否为零为零则为空返回true不为零则不为空返回false。2.5 队头出队列//出队-队头voidQueuePop(Queue*pq){assert(!QueueEmpty(pq));//只有一个节点时phead和ptail都置为空if(pq-pheadpq-ptail){free(pq-phead);pq-pheadpq-ptailNULL;}else//多个节点直接头删{QueueNode*nextpq-phead-next;free(pq-phead);pq-pheadnext;}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*pcurpq-phead;intsize0;while(pcur){size;pcurpcur-next;}returnsize;//第二种方式适用于频繁调用队列有效数据个数的场景returnpq-size--;//我们这篇文章的讲解的定义了size所以直接用第二种就可以。}在这里就显示出我们定义一个size成员的好处了可以减少代码量并且简洁易懂。上面的代码中也给出了如何通过遍历来获取有效数据个数。2.9 销毁队列//销毁队列voidQueueDesytoy(Queue*pq){assert(pq);//逐个释放QueueNode*pcurpq-phead;while(pcur){QueueNode*nextpcur-next;//定义一个next指针存pcur中的next防止freepcur后找不到下一个节点了free(pcur);pcurnext;}pq-pheadpq-ptailNULL;pq-size0;}要注意逐个节点释放类似于单链表定义一个next指针存pcur中的next防止freepcur后找不到下一个节点了三、链表队列实现的全部代码3.1 Queue.h#pragmaonce#includestdio.h#includestdlib.h#includeassert.h#includestdbool.htypedefintQDataType;//队列节点的结构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#includeQueue.h//初始化voidQueueInit(Queue*pq){assert(pq);pq-pheadpq-ptailNULL;//pq-size 0;}//入队-队尾voidQueuePush(Queue*pq,QDataType x){assert(pq);QueueNode*newnode(QueueNode*)malloc(sizeof(QueueNode));if(newnodeNULL){perror(malloc fail);return;}newnode-datax;newnode-nextNULL;if(pq-pheadNULL){pq-pheadpq-ptailnewnode;}else{pq-ptail-nextnewnode;pq-ptailpq-ptail-next;}/*pq-size;*/}//出队-队头voidQueuePop(Queue*pq){assert(!QueueEmpty(pq));//只有一个节点时phead和ptail都置为空if(pq-pheadpq-ptail){free(pq-phead);pq-pheadpq-ptailNULL;}else{QueueNode*nextpq-phead-next;free(pq-phead);pq-pheadnext;}/*pq-size--;*/}//队列判空boolQueueEmpty(Queue*pq){assert(pq);returnpq-pheadNULL;}//取队头数据QDataTypeQueueFront(Queue*pq){assert(!QueueEmpty(pq));returnpq-phead-data;}//取队尾数据QDataTypeQueueBack(Queue*pq){assert(!QueueEmpty(pq));returnpq-ptail-data;}//销毁队列voidQueueDesytoy(Queue*pq){assert(pq);QueueNode*pcurpq-phead;while(pcur){QueueNode*nextpcur-next;free(pcur);pcurnext;}pq-pheadpq-ptailNULL;pq-size0;}//队列有效元素个数intQueueSize(Queue*pq){assert(pq);//第一种方式适用于不用频繁调用队列有效数据个数的场景QueueNode*pcurpq-phead;intsize0;while(pcur){size;pcurpcur-next;}returnsize;//第二种方式适用于频繁调用队列有效数据个数的场景/*return pq-size--;*/}3.3 test.c#includeQueue.hvoidtest01(){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.消息队列电商订单消息、直播弹幕、聊天软件消息转发异步排队处理。五、总结队列是一种线性数据结构遵循先进先出的规则只能在队尾添加元素在队头删除元素不允许在中间位置进行插入、删除操作。它主要用于处理按先后顺序执行的任务能够实现排队等待、依次处理的逻辑是编程中常用的基础存储结构。