【初阶数据结构】深入解析循环队列:探索底层逻辑

🔥引言

本篇将介绍如何实现循环队列并实现过程需要注意的事项，虽然篇幅较小，但是其中逻辑还是值得引人思考的，循环队列可以采用数组或链表实现，这篇将采用数组实现循环队列

🌈个人主页： 是店小二呀

🌈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 小总结

这里我们选择第二种方案进行实现，对此我们总结下，定义好的方式。

1. front == back就是为空
2. 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都为下标

这里需要注意的是:这里没有跟队列一样采用两个结构体设计，而是采用在结构体对象内开辟一块空间用于存储节点，再调用结构体成员进行头尾操作，达到循环队列的功能。

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;
}

这里需要注意的是:关于两次调用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;
}

这里需要注意的是:对于判断是否为空，不是重点，对于判断是否为满，根据取模的特点进行处理，对于数据结构处理建议画图分析

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);
}

以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二初阶数据结构笔记，希望对你在学习初阶数据结构中有所帮助！