数据结构：循环队列

文章目录前言一、数组实现循环队列1.1 思路分析1.2 代码的实现1.2.1 结构的定义1.2.2 构造一个有限空间的数组并返回1.2.3 向循环队列插入一个元素。如果成功插入则返回真。1.2.4 向循环队列删除一个元素。如果成功删除则返回真。1.2.5 从队首获取元素。如果队列为空返回 -11.2.6 获取队尾元素。如果队列为空返回 -11.2.7 检查循环队列是否为空1.2.8 检查循环队列是否已满1.2.9 释放循环队列二、链表实现循环队列2.1 思路分析2.2 代码实现2.2.1 结构体的定义2.2.2 队列长度为 k并返回2.2.3 向循环队列插入一个元素。如果成功插入则返回真2.3.4 从循环队列中删除一个元素。如果成功删除则返回真2.2.5 从队首获取元素。如果队列为空返回 -12.2.6 获取队尾元素。如果队列为空返回 -12.2.7 检查循环队列是否为空2.2.8 检查循环队列是否已满2.2.9 释放循环列表前言我们所了解的队列是先进先出有无限的空间而对于循环队列它是在有限的空间保证先进先出重复利用。比如说在生活中图书馆的位置是有限的当人坐满以后就必须等到有人走后才能等到下一个人使用。一、数组实现循环队列1.1 思路分析首先我们需要一个数组其次需要头和尾tail这里和栈的top一样用来指向队尾数据的下一个位置k代表数组能存放几个数据即空间大小是固定的。对于tail表示的是指向队尾数据的下一个位置分析当数组为空时tail指向下标为0的位置当插入一个数据时tail还是指向下标为0的位置就无法与空链表区分开。那这个循环队列什么时候为空为什么时候为满呢从下图可以看到我们pop三次后当head tail时为空然后push 四次后可以看出head tail时为满这就有了问题我们区分不了什么时候为空什么时候为满。这也叫做假溢出的问题因此这个问题有两种方法解决。我们可以使用size这个变量去记录如果size k就为满如果size 0就为空多开辟一个空间这里我们主要讲解第二种方法去解决这个问题。如下图所示head tail时为空当tail的下一个位置为head时就满了1.2 代码的实现1.2.1 结构的定义typedefstruct{int*arr;inthead;//指向头inttail;//指向尾的下一个intk;//数组的容量}MyCircularQueue;1.2.2 构造一个有限空间的数组并返回根据之前的分析我们需要多开辟一块空间MyCircularQueue*myCircularQueueCreate(intk){MyCircularQueue*obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(objNULL){perror(myCircularQueueCreate::malloc);exit(1);}//多开一个防止假溢出obj-arr(int*)malloc(sizeof(int)*(k1));if(obj-arrNULL){perror(myCircularQueueCreate-arr::malloc);exit(1);}obj-head0;obj-tail0;obj-kk;returnobj;}1.2.3 向循环队列插入一个元素。如果成功插入则返回真。首先既然要插入元素就得满足队列不能为满。对于下图当我们想要插入元素时tail加加后会越界因此我们得让它回到下标为0的位置。我们可以让tail%(k1)比如tail后变成了5然后%5结果等于0.就解决了越界的问题。boolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue){if(myCircularQueueIsFull(obj))returnfalse;obj-arr[obj-tail]value;obj-tail;obj-tail%(obj-k1);returntrue;}1.2.4 向循环队列删除一个元素。如果成功删除则返回真。boolmyCircularQueueDeQueue(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))returnfalse;obj-head;obj-head%(obj-k1);returntrue;}1.2.5 从队首获取元素。如果队列为空返回 -1intmyCircularQueueFront(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))return-1;elsereturnobj-arr[obj-head];}1.2.6 获取队尾元素。如果队列为空返回 -1这里我们需要注意当tail为0时取的是上一个元素也就是arr[obj-k]或者也可以这样写(obj-arr[obj-kobj-tail])%(obj-k1)intmyCircularQueueRear(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))return-1;elsereturnobj-tail0:obj-arr[obj-k]?obj-arr[obj-tail-1];}1.2.7 检查循环队列是否为空boolmyCircularQueueIsEmpty(MyCircularQueue*obj){returnobj-headobj-tail;}1.2.8 检查循环队列是否已满boolmyCircularQueueIsFull(MyCircularQueue*obj){return(obj-tail1)%(obj-k1)obj-head;}1.2.9 释放循环队列voidmyCircularQueueFree(MyCircularQueue*obj){free(obj-arr);free(obj);}二、链表实现循环队列2.1 思路分析这里的tail仍然是指向队尾数据的下一个首先面临的问题依旧是判空和判满的问题这个问题可以像前面的数组一样解决如下图所示然后这时我们会面临一个新的问题那就是取尾对于这个问题有以下三种方法。遍历一遍链表可以将循环链表改成双向链表可以在tail走的时候再记录一个tailprev对于方法一当我们每次取尾时都需要来遍历链表会很麻烦方法二双向链表会让你空间翻倍而且使用双向链表在链表不能实现再使用方法三只需要多一个指针其实是可以接受的。但实际上我们可以使用size来判断是否为空或者满让tail指向尾节点。2.2 代码实现2.2.1 结构体的定义typedefstructQNode{intval;structQNode*next;}QNode;typedefstructMyCircularQueue{QNode*head;QNode*tail;intsize;//记录有效个数intk;//有限个节点};2.2.2 队列长度为 k并返回MyCircularQueue*myCircularQueueCreate(intk){MyCircularQueue*obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(objNULL){perror(myCircularQueueCreate::malloc);exit(1);}obj-headobj-tailNULL;obj-size0;obj-kk;returnobj;}2.2.3 向循环队列插入一个元素。如果成功插入则返回真boolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue){if(myCircularQueueIsFull(obj))returnfalse;//创建一个新节点QNode*newnode(QNode*)malloc(sizeof(QNode));if(newnodeNULL){perror(myCircularQueueEnQueue::malloc);exit(1);}newnode-nextNULL;newnode-valvalue;//为空时if(myCircularQueueIsEmpty(obj))obj-tailobj-headnewnode;else{obj-tail-nextnewnode;obj-tailnewnode;}obj-size;returntrue;}2.3.4 从循环队列中删除一个元素。如果成功删除则返回真boolmyCircularQueueDeQueue(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))returnfalse;QNode*nextobj-head-next;free(obj-head);obj-headnext;obj-size--;if(myCircularQueueIsEmpty(obj))obj-headobj-tailNULL;//防止野指针returntrue;}2.2.5 从队首获取元素。如果队列为空返回 -1intmyCircularQueueFront(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))return-1;returnobj-head-val;}2.2.6 获取队尾元素。如果队列为空返回 -1intmyCircularQueueRear(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))returnfalse;returnobj-tail-val;}2.2.7 检查循环队列是否为空boolmyCircularQueueIsEmpty(MyCircularQueue*obj){returnobj-size0;}2.2.8 检查循环队列是否已满boolmyCircularQueueIsFull(MyCircularQueue*obj){returnobj-sizeobj-k;}2.2.9 释放循环列表voidmyCircularQueueFree(MyCircularQueue*obj){QNode*curobj-head;while(cur){QNode*nextcur-next;free(cur);curnext;}free(obj);}其实我们可以看出来不管是数组实现还是链表实现其实逻辑是差不多的。