【初阶数据结构】深入解析循环队列:探索底层逻辑
🔥引言
本篇将介绍如何实现循环队列并实现过程需要注意的事项，虽然篇幅较小，但是其中逻辑还是值得引人思考的，循环队列可以采用数组或链表实现，这篇将采用数组实现循环队列
🌈个人主页：是店小二呀 🌈C语言笔记专栏：C语言笔记 🌈C++笔记专栏： C++笔记 🌈初阶数据结构笔记专栏： 初阶数据结构笔记
🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
一、循环队列的概念
循环队列是一种用数组实现的队列数据结构，与普通队列不同的是，循环队列允许队列的头尾相接，实现循环利用数组空间。它解决了普通队列在出队操作频繁时需要大量元素迁移的效率问题。循环队列通常通过两个指针来实现：一个指向队列的头部（front），一个指向队列的尾部（rear）。当队列满时，rear 指针可以绕回到数组的起始位置，实现循环存储；当队列为空时，front 和 rear 指针指向同一个位置。
二、实现循环队列的知识铺垫(核心实现逻辑)
2.1 队列满足什么条件为空
当front==back时不一定为空。这里是循环队列，如果出现front= =back时会出现下列两种情况
back通过循环与front相遇，此时front==back，则队列满了一开始back没有移动，back和front在同位置，此时front==back，则队列为空对此我们无法通过front==back区分开空和满的情况，需要重新定义为空或满的标志
2.2 解决何时为空何时为满的方案
关于front和back初始位置，front指向对头，而由于back指向队尾会很难看，需要手动back置为-1，对此这里back指向队尾的下一个元素(跟栈中top定义问题是类似的)
判断满的两种方案:
增加一个size，当front== back并且size= =0就为空，size！=0就是为满多开一个空间，这样的好处就是back+1==front为满（不要存储数据，这样又回到了不能判断空或满）2.3 小总结
这里我们选择第二种方案进行实现，对此我们总结下，定义好的方式。
front == back就是为空back + 1 == front就是为满2.4 循环队列中如何保证闭环
如果遇到循环相关问题，可以考虑取模(解决问题上十分巧妙)。我们想要达到的目的是当back到达空位置时，就是相当于到了头位置。
同时取模中，如果左边小于右边，没有改变。如果左边大于左边，就会删除右边的倍数，直到左边小于右边(这里就是取模的逻辑，如果很难理解，可以通过图来理解下)
这里需要注意的是:这张图我们需要关注的地方back + 1和 head的位置，k +1是空位置，下标为4和0位置重叠处三处。这里size为有效元素个数，这里只多开一个空间并没有算上有效元素，然后k + 1到达空位置，我们想要的结果是我们想要达到的目的是当back到达空位置时，就是相当于到了头位置，这里(obj->back+1)%(obj->size+1)==obj->head;就满足了这种情况，相同数据取模模为0，意味着下标为0
2.5 计算循环队列的数据个数
如果是计算队列的数据个数，通常就是back - front，但是这里是循环队列可能会出现back在front前面的特殊情况。
解决措施:(back+(k+1)-front)%k+1。这里担心back - front出现负数，个数不是存在负数这种情况的。那么可以将back + (k + 1) - front % k + 1这样保证了back - front + (k + 1) % k + 1当back - front出现负数，增加k + 1保证了正数再取模保证数据没有超过循环队列的长度，那么这样得到数据个数是否正确呢？通过画图在整个循环中的代表位置是相同的。
只要理解上面相关知识，模拟实现循环队列也变得简单起来了，让我们模拟实现起来吧！
三、实现循环队列相关步骤
3.1 循环队列的搭建
typedef struct { int *a; int size; int head; int back;//元素的下一个位置 } MyCircularQueue; //head 和 back都为下标 12345678这里需要注意的是:这里没有跟队列一样采用两个结构体设计，而是采用在结构体对象内开辟一块空间用于存储节点，再调用结构体成员进行头尾操作，达到循环队列的功能。
3.2 构建器(设置队列长度为 k)
MyCircularQueue* myCircularQueueCreate(int k) //为结构体开辟空间 { MyCircularQueue *obj=(MyCircularQueue *)malloc(sizeof(MyCircularQueue)); if(obj==NULL) return NULL; obj->a=(int *)malloc(sizeof(int)*(k+1));//多开一个空间 if(obj->a==NULL) return NULL; obj->size=k; obj->back=obj->head=0; return obj; } 1234567891011121314这里需要注意的是:关于两次调用malloc函数开辟空间，第一次malloc开辟空间，用于为该结构体对象开辟空间，第二次malloc开辟空间，是为了队列元素开辟空间(包含了不存放数据的空间)，这空间是关联在一起的，对此需要搞清楚需要开辟多大的空间和交给什么数据类型维护
3.3 判断循环队列是否为满和空的情况
bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->back+1)%(obj->size+1)==obj->head; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { assert(obj); return obj->head==obj->back; } 12345678910这里需要注意的是:对于判断是否为空，不是重点，对于判断是否为满，根据取模的特点进行处理，对于数据结构处理建议画图分析
3.4 检查是否能插入数据和删除数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj->a[obj->back]=value; obj->back++; //防止越界 obj->back%=(obj->size+1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj->head++; //防止越界 obj->head%=(obj->size+1); return true; }
这里需要注意的是:这里无论是插入还是删除数据，需要对x %= (obj->size+1);防止超过队列长度，而且这里需要注意顺序问题
3.5 获得队首元素和队尾元素
int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[obj->head]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; if(obj->back==0)//插入的时候 return obj->a[obj->size];//表示尾的情况 else return obj->a[obj->back-1]; //return obj->a[(obj->back-1+obj->size+1)%(obj->size+1)]; }
这里需要注意的是:这里获得队首元素和队尾元素，都需要先判断循环队列是否为空。在获得队尾元素中，一般情况下 obj->a[obj->back-1]是没有问题的，但是如果在插入一个数据，back回到首元素位置上，back-1就会出现问题，会导致越界访问，对此obj->a[(obj->back-1+obj->size+1)%(obj->size+1)]; 可以将这个循环队列展开一段，加obj->size+1再取obj->size+1模，这里同计算循环队列有效数据长度的方式是一样的。
3.6 循环的销毁
void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); } 12345
Ongwu博客 版权声明：以上内容未经允许不得转载！授权事宜或对内容有异议或投诉，请联系站长，将尽快回复您，谢谢合作！