文章目录数据结构6队列队列的概念及结构队列的实现环形队列数据结构6队列上一章我们了解并实现了栈这个数据结构本章节开始了解队列和实现队列这个数据结构。队列的概念及结构队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)入队列进行插入操作的一端称为队尾出队列进行删除操作的一端称为队头栈和队列就是完全相反的数据结构栈是先进后出队列则是先进先出。队列的实现队列也可以数组和链表的结构实现使用链表的结构实现普通队列会更优一些因为如果使用数组的结构出队列就是在做头删操作并且在后续数据量上来了每一次扩容其实都有可能对空间进行浪费。队列是先进先出的结构只能从一端进从另一端出。之所以用链表结构来从当队列的子结构是普通队列链表插入和删除都是O(1)的而数组只有尾插和尾删是O(1)其他的插入和删除都是O(N)需要多少节点就 malloc 多少不会像数组那样固定死或需要扩容。数组队列出队后前面的空间浪费链表不存在这个问题。#includestdio.h#includestdlib.h#includestdbool.h#includeassert.htypedefintQDatatype;typedefstructQueueNode{structQueueNode*next;QDatatype data;}QNode;typedefstructQueue{QNode*head;QNode*tail;intsize;}Queue;结构设计介绍head指针只管出队列tail指针只管入队列互不影响size是为了获取当前队列的有效数据个数可加可不加实现函数接口// 初始化队列voidQueueInit(Queue*pq);// 销毁队列voidQueueDestroy(Queue*pq);// 入队列voidQueuePush(Queue*pq,QDatatype x);// 出队列voidQueuePop(Queue*pq);// 获取队列有效数据个数intQueueSize(Queue*pq);// 判断队列是否为空boolQueueEmpty(Queue*pq);// 获取队头数据QDatatypeQueueFront(Queue*pq);初始化队列// 初始化队列voidQueueInit(Queue*pq){pq-headNULL;pq-tailNULL;pq-size0;}空队列就是两个指针都为 NULL表示链表里一个节点都没有。队列判空// 判断队列是否为空boolQueueEmpty(Queue*pq){assert(pq);// 因为我们这个结构也可以用size进行判空returnpq-headNULL;}为什么这里只判了head因为head NULL 和 tail NULL在正确的实现里永远同时成立空队列两个都是 NULL。非空队列两个都非 NULL。使用链表实现的好处这里是其中之一链表实现不需要判满但需要判空而数组都需要判断。入队列// 入队列voidQueuePush(Queue*pq,QDatatype x){assert(pq);QNode*node(QNode*)malloc(sizeof(QNode));if(nodeNULL){perror(malloc fail);return;}node-datax;node-nextNULL;// 入队列有两种情况// 1. 空队列if(QueueEmpty(pq)){pq-headpq-tailnode;}// 2. 非空队列else{pq-tail-nextnode;pq-tailnode;}pq-size;}新节点的 next 必须先置 NULL它是新的尾节点。空队列是特殊情况因为此时 tail 是 NULL不能写 q-tail -next node空指针解引用会崩。必须让 head和 tail 同时指向新节点。非空时先把旧尾的 next 接到新节点再更新 tail 。两步顺序不能反出队列// 出队列voidQueuePop(Queue*pq){assert(pq);assert(!QueueEmpty(pq));QNode*curpq-head;pq-headcur-next;// 如果出队列后head为空了此时tail同样要置空if(pq-headNULL){pq-tailNULL;}free(cur);curNULL;pq-size--;}注意如果出队列时需要获取出队列的数据需要将数据先保存再free。获取队列有效元素个数// 获取队列有效数据个数intQueueSize(Queue*pq){assert(pq);returnpq-size;}因为我们这里队列最开始声明了size变量所以实现了该函数接口如果没声明可以不实现。获取队头数据// 获取队头数据QDatatypeQueueFront(Queue*pq){assert(pq);assert(!QueueEmpty(pq));returnpq-head-data;}这里需要对队列进行判空如果不进行判空当队列是空队列时指向的是NULL此时会导致未定义从而导致程序崩溃。销毁队列// 销毁队列voidQueueDestroy(Queue*pq){assert(pq);QNode*curpq-head;while(cur!NULL){QNode*nextcur-next;free(cur);curnext;}pq-headpq-tailNULL;pq-size0;}最后记得要置空 head 和 tail并将 size 置零环形队列拓展了解环形队列。实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现也可以使用循环链表实现。环形队列和普通队列最大的区别就是环形队列的长度是固定的那么环形队列的长度是固定的那岂不是在实用性上不如普通队列。并不是环形队列它主要用于处理临时数据比如程序运行的日志缓冲区等。判满和判空如果图方便的话可以向我们上面实现普通队列一样定义一个size因为环形队列的长度是固定了那么size 0 就是空队列size MAX_SIZE(MAX_SIZE是define定义的)就是满队列所以环形队列的实现通常是数组因为方便管理。完
