【手撕数据结构】循环队列

目录循环队列概念结构分析队列初始化队列已满队列为空入队列出队列取队头元素取队尾元素销毁队列循环队列概念我们前面已经介绍过队列他的基本操作就是在队头出元素在队尾如元素。今天介绍的循环队列与前面的队列有所不同他可以一直利用申请的空间进行循环的出队列入队列等操作。结构分析现在定义两个指针一个指向队头一个指向队尾我们在front位置进行入队列。队列初始化typedefstruct{int*arr;intfront;//队头intrear;//队尾intcapacity;//存储空间个数}MyCircularQueue;这里我们不再用单链表作为队列的底层结构而是采用数组来作为底层结构。原因是循环队列需要重复利用一块空间地址而如果使用单链表作为底层结构那么就不能直接释放头节点达到出队列的操作那么再次使用这快空间要判断当前节点是否为空。而使用数组就可以直接移动front指针而不直接删除空间如果需要重新利用删除的空间直接将front指针指向原来的空间直接覆盖就行MyCircularQueue*myCircularQueueCreate(intk){MyCircularQueue*pst(MyCircularQueue*)malloc(sizeof(MyCircularQueue));pst-arr(int*)malloc(sizeof(int)*(k1));//多申请一块空间用于判断循环队列是否满了且不为空pst-frontpst-rear0;//如果用frontreat判断队列满了但是队列为空时也符合这个条件pst-capacityk;returnpst;}这里我们需要多开辟一块空间,因为我们需要判断循环队列是否满了这时候就有人说了直接判断rear和front指针是否相等就行了啊.但是遗憾的是我们队列为空的时候front也与rear相等。所以我们多开辟一块空间利用,(rear1)%(capacity1)这个表达式来判断队列已满boolmyCircularQueueIsFull(MyCircularQueue*obj){return(obj-rear1)%(obj-capacity1)obj-front;}上图已经解释队列为空boolmyCircularQueueIsEmpty(MyCircularQueue*obj){returnobj-rearobj-front;}入队列boolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue){//判断队列是否满了满了不能插入数据if(myCircularQueueIsFull(obj)){returnfalse;}//队列没满obj-arr[obj-rear]value;obj-rear%obj-capacity1;//这里就体现了多申请一块空间的好处,当是rear1时%capacity1就等于0,再插入数据就是1,例如:1%5还是为1,位置插入returntrue;}如果队列满了就不能再进行插入没有满则再rear指针处插入数据注意rear的作用如:出队列boolmyCircularQueueDeQueue(MyCircularQueue*obj){//队列为空if(myCircularQueueIsEmpty(obj)){returnfalse;444}obj-front;//这里删除只需要与栈删除只需要--一样的因为是数组可以直接覆盖这个原来的元素,不需要像链表一样释放空间(因为链表物理结构不一定连续)//有可能front会越界所以需要重新进循环obj-front%obj-capacity1;returntrue;}取队头元素ntmyCircularQueueFront(MyCircularQueue*obj){//队列为空if(myCircularQueueIsEmpty(obj)){return-1;}returnobj-arr[obj-front];}取队尾元素intmyCircularQueueRear(MyCircularQueue*obj){//队列为空if(myCircularQueueIsEmpty(obj)){return-1;}intprevobj-rear-1;if(obj-rear0)//rear为0时如果直接返回obj-[rear-1]会越界{prevobj-capacity;}returnobj-arr[prev];}销毁队列voidmyCircularQueueFree(MyCircularQueue*obj){free(obj-arr);//底层数组空间连续所以只释放首地址free(obj);objNULL;}