栈和队列的习题详解（4）：设计循环队列

用户11295429

发布于 2024-10-16 17:05:51

630

发布于 2024-10-16 17:05:51

文章被收录于专栏：王的博客专栏

前言：

这篇文章将是我写的最后一个栈和队列的习题，以后我如果遇到了一些比较好的习题的话我也会写作答方法，在讲这个题之前，小编先给各位打一个预防针，这个题目做起来是比较困难的，我会尽可能的给各位讲明白，废话不多说，开启今天的习题之旅~

正文：

1.设计循环队列

老规矩，小编先给这个题目的地址：622. 设计循环队列 - 力扣（LeetCode）

1.1.题目解读

相信各位读者朋友看到这个题目难度的时候，会和我一样心颤一下，因为这个题目的难度居然是久违的中等难度，上次小编讲解一个中等题目的时候，我还记着那个题目是叫做随机链表的复制，那个题目是我之前见过的最有难度的题目之一，这里小编把这个题也列为一个颇有难度的题目，先看看题目说的是什么，这个题目想让我们设置一个循环的队列，它和普通队列一样是遵从着先进先出的原则，但是此时这个队列的首和尾是结合起来的，并且这个题目要求我们的队列的长度是一定的，所以我们在队列满了以后是不可以在继续插入数据的，对于普通的队列我们之后就不能在插入数据了，但是循环队列不一样，我们可以在移除一个数据以后，就可以继续插入数据，因为它是循环的，所以此时我们在出队头以后，可以从队尾在进入新数据，此时这个数据就放置在原来队头的位置，不过此时的队头已经是下一个元素了，我这么说可能很多读者朋友还是不太明白，小编通过画图来带领各位去理解循环队列的样子，如下图所示：

此时上图就是循环队列的样子，此时读者朋友就可以明白为什么队列满了的回时候，我们在进行出队列操作完以后还可以插入数据，因为它的结构允许它这么做，小编当时在做这个题目的时候思路也是很模糊的，当时我是想用循环链表的方式去做这个题目，但是实操起来我确实没有半点思路，于是在我听完老师的讲解以后，便知道了这个题目的做法，下面小编也不多废话，我先来讲述一下这个题目的做题思路~

1.2.题目的主要解题思路

我讲述的这个题目的解题思路还是比较巧妙的，此时我们涉及的这个循环队列，它的底层逻辑不在是使用链表的思路来做，因为此时这个题目看似我们不确定要开辟多大的空间，但在我们初始化队列的时候，便给了我们一个确定值来确定这个队列可以存放多大的空间，此时可以看作把一个动态的空间静态化了，在我们插入数据的时候，此时我们使用链表的时候会显示的繁琐一点，因为我们在填完队列以后，在之后删除数据后还得插入数据，此时链表的操作就显的比较繁琐一点，所以小编推荐此时我们设置这个队列的底层逻辑是数组，因为使用数组会便利一些，并且我相信大部分读者朋友相比于链表的话，还是更喜欢顺序表一点，因为毕竟数组算是目前比较简单的内容，所以小编这个题目将会使用底层为数组的队列来进行解决问题。

当我们在书写队列的结构体内容的时候，也是比较有讲究的，小编设置的这个队列肯定有队头元素和队尾元素，此外还需要有一个待动态开辟的指针，并且还需要有一个变量，我们看看上面的初始化函数，此时这个函数是规定让我们开辟指定空间大小的队列，所以这个变量是用来存放队列空间大小的，从而方便之后我们求判断队列是否满了；之后我们就要进行入队列操作了，在我们入队列之前，我们自然而然的是去判断这个队列是否是满的，可能此时读者朋友会说，当队头和队尾相等的时候，这个队列不就满了吗？这个想法乍一看是对的，但是大家要知道，我们在刚开始进行初始化的时候，队头和队尾应该要求默认都是0，此时队头和队尾是一样的，但是队列却没满，所以我们首先就要先去解决这个问题，小编当时想到一个解决方案，就是我们在刚开始的结构体的内容在加一个size变量，用它来记录此时的队列是否是满的，当它等于队列长度的时候就代表队列是满的，这个解决方案自然是可行的，但是这会让结构体里面的变量会非常多，这样的算法称不上是一个比较好的算法，当然小编在听完课以后还知道了一种算法，我们可以在刚刚开辟数组的时候多开辟一个整形大小的空间，这个空间默认是不存数据的，它存在的意义就是为了判断这个队列是不是满的，当（队尾+1）/ （队列元素总个数+1）== 队头的时候，此时就可以说明此时的队列是满的，当不满时，我们直接正常的进行入队列即可，即先让队尾所在的位置插入一个元素，然后队尾向后走；本题目的主要思路便是上述，在创建数组时多开辟一块空间是这个题目的点睛之笔，以及队列用数组去做，下面小编讲带领各位去实现循环队列的部分功能~

1.3.循环队列功能的实现

首先我们肯定是要有结构体的书写，小编上述也写了，我们需要一个队头，队尾，空间大小，以及最重要的动态数组作为循环队列结构体的内容，代码如下图所示：

typedef struct {
    int* arr;
    int front;  //存放着队头元素
    int pour;   //存放着队尾元素
    int capcoaty;  //表示队列中元素个数
    
} MyCircularQueue;

1.3.1.循环队列的初始化（MyCircularQueue* myCircularQueueCreate(int k)）

刚开始，我们肯定是要对循环队列进行初始化，我们先看看此时的返回类型，是很明显的循环队列指针类型，此时我们需要先动态开辟一个循环队列类型的指针变量，在创建完以后我们需要把里面的内容进行初始化，首先是arr，此时这个题目已经告诉队列可以存放的元素个数是k个，但是小编在上面的思路就说过，为了后续判断队列是否满了方便，此时我们动态开辟数组的大小应该是整形大小*（k + 1），数组开辟完以后我们直接先让队头和队尾默认为0，对于空间大小我们设置为队列中元素个数，即k个就好，此时我们就完成了队列的初始化，代码如下所示：

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    pq -> arr = (int*)malloc(sizeof(int) * (k + 1));
    pq -> front = pq -> pour = 0;
    pq -> capcoaty = k; 
    return pq;
}

1.3.2.判断循环队列是否满了（myCircularQueueIsFull(MyCircularQueue* obj)）

我们想要实现入队列操作，就必须先判断队列是否满了，满了的话就插不进去了，此时这个操作小编也在上面说过，我们仅需判断队尾（pour）+ 1 除以 capcoaty + 1是否等于队头数据即可，如果此时相等了，那么就代表着这个队列满了，反之就没满，可能很多读者朋友不知道为什么这样做就能判断，小编分享一个我经常使用的方法来教大家如何去判断，我们完全可以通过使用一个例子来类比推出这个公式，小编当时就是认为数组只能存4个数，那样我们就开辟了5个整型的空间，此时如果数据满了的话，pour是等于4（pour要比数组的最后一个元素多1），front为5，空间大小为4，所以此时pour+1 / (capcoaty + 1) == 0就是队头，所以此时代表着队列满了，以此类推可以推出上面的式子，以上就是如何队列是否满了，下面给上代码：

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj -> pour + 1) % (obj -> capcoaty + 1) == obj ->front;
}

1.3.3.入队列操作（myCircularQueueEnQueue(MyCircularQueue* obj, int value)）

在入队列操作之前，我们首先要去判断此时的队列是不是就是满的，如果满了，那我们直接返回false即可，如果没有满，那我们就可以开始进行入队列操作，可能此时很多小伙伴认为直接让arr[obj -> pour++] = x，此时就是完成了入队列操作，小编当时也是这么想的，但是各位读者朋友忘记了这个队列是可以去循环的，所以当rear是5的时候此时这个数组就越界了，所以这个题目的正确的解题方法就是，我们先正常的书写arr[obj -> pour++]，但这个题目并没有结束，我们还需要让此时的队尾去%上arr空间的大小，也就是capcoaty + 1，完成这一步操作以后，我们就可以确保此时的队尾一定保证小于等于4，然后我们再返回true就好了，此时我们就实现了入队列操作，下面小编给出代码：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj -> arr[obj -> pour++] = value;
    obj -> pour %= obj -> capcoaty + 1;
    return true;
}

1.3.4.判断循环队列是否为空（myCircularQueueIsEmpty(MyCircularQueue* obj)）

在我们进行出队列操作之前，我们肯定是要先确定队列数据是否为空，如果为空的话，我们就进行不了出队列操作了，此时的判断条件很容易，当我们队头和队尾都等于0的时候，就代表着此时的队列为空，此时我们便实现了这个功能，这个功能算是本题比较容易实现的功能之一了，前提是我们在创建数组的时候多创建了一块空间这个操作的点睛之笔，不然此函数就和上面的判断循环队列是否为满函数产生冲突了，下面小编给出代码：

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj ->front == obj -> pour;
}

1.3.5.出队列操作（myCircularQueueDeQueue(MyCircularQueue* obj)）

在进行出队列操作之前，我们首先要去判断这个队列是否为空，如果为空的话，那么我们直接返回false就好，如果不为空，那么我们就可以实现出队列操作了，此时就类似于当时我们写顺序表的时候头删函数，我们直接让front++就好，但是此时我们真就实现了这个功能吗？各位仔细思考一下，我这么说有什么错误，还记着上面的入队列操作吗，我们还需要考虑到此时的front在数组最后一个元素的情况，如果我们继续让front往后走，此时就数组越界了，所以此时的front也需要进行%数组元素个数操作，防止数组越界，实现真正的出队列操作，这个函数这个比较小的坑我们一定要注意到，不然我们就会不自觉的入坑喽~此时我们就写完了这个函数，下面小编给上代码：

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj -> front++;
    obj -> front %= obj -> capcoaty + 1;
    return true;
}

1.3.6.取队头操作（myCircularQueueFront(MyCircularQueue* obj)）

首先我们仍需要判断此时的队列是不是空的，如果是空的，我们就没什么队头元素可取了，我们直接返回-1就好，如果队列不为空，我们就可以直接返回队头所在的数组位置的元素即可，我们就完美的实现了这个函数的功能，这个操作同样与之前相比也不是一个难的函数，下面给出代码：

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj -> arr[obj -> front];
}

1.3.7.取队尾操作（myCircularQueueRear(MyCircularQueue* obj)）

和取队头操作一样，我们首先要去判断此时的队列是不是空的，如果队列的数据为空，那么我们就不可以在进行取队尾操作，我们直接返回-1就好，如果不为空，那么我们就可以取队尾了，此时结构体里面的pour就是队列尾部元素所在的位置下一个元素，所以我们想要取到队尾的数据，我们直接让其-1就好了，但是此时有一个特殊情况我们需要留意，那就是此时队尾正好是0，如果我们直接减一，此时的话数组就越界了，所以我们就必须要判断一下此时的pour是否为0，如果为0的话我们就返回数组最后一个元素就好，此时这个函数的功能我们就实现了，下面小编给出代码：

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        int m = obj -> pour - 1;
        if(m < 0)
        {
            m = obj -> capcoaty;
        }
        return obj -> arr[m];
    }
}

1.3.8.循环队列的销毁（myCircularQueueFree(MyCircularQueue* obj)）

最后，我们在实现完一些日常使用的功能以后，我们就需要去销毁这个队列了，一提到销毁操作，我们正常的操作就是把那些我们动态开辟过的资源给free掉，此时我们首先要把结构体里的arr给free掉，然后让它指向空，养成不写野指针的良好习惯，之后再把结构体另外三个变量变为0即可（这个操作其实可有可无），此时的形参循环变量指针也是我们在前面动态开辟出来的，所以我么也需要free掉，然后指向空；这样下来我们就实现了销毁功能，下面小编给出代码：

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj -> arr);
    obj -> arr = NULL;
    obj -> capcoaty = obj -> front = obj -> pour = 0;
    free(obj);
    obj = NULL;
}

以上便是循环队列的题目实现，这个题目的难点就在于我们如何处理循环这一个功能，此时多设置出一块空间便是这个题目的点睛之笔，也是重难点，之后每个函数或多或少的都有一些小坑，如果坑少的话这个题目的难度就不是中等了，下面小编给出这个题目的完整解答，方便各位读者朋友知道这个题目的写法以及方便给各位提供思路~

1.4.代码展示

typedef struct {
    int* arr;
    int front;  //存放着队头元素
    int pour;   //存放着队尾元素
    int capcoaty;  //表示队列中元素个数
    
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    pq -> arr = (int*)malloc(sizeof(int) * (k + 1));
    pq -> front = pq -> pour = 0;
    pq -> capcoaty = k; 
    return pq;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj ->front == obj -> pour;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj -> pour + 1) % (obj -> capcoaty + 1) == obj ->front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj -> arr[obj -> pour++] = value;
    obj -> pour %= obj -> capcoaty + 1;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj -> front++;
    obj -> front %= obj -> capcoaty + 1;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj -> arr[obj -> front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        int m = obj -> pour - 1;
        if(m < 0)
        {
            m = obj -> capcoaty;
        }
        return obj -> arr[m];
    }
}


void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj -> arr);
    obj -> arr = NULL;
    obj -> capcoaty = obj -> front = obj -> pour = 0;
    free(obj);
    obj = NULL;
}

2.总结

以上便就是这个题目的讲解，这个题目看起来代码量比小编前几篇写的题的代码量小，但是它思考的东西要多，不然它的难度就不是被力扣认为中等难度，希望各位读者朋友好好的去理解这个题目。习题篇就告一段落了，希望各位读者朋友好好去领悟这四个习题，如果文章有错误，各位可以在评论区指出，小编会及时看消息并做出答复以及更正，那么，我们下一篇博客见啦！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-16，如有侵权请联系 cloudcommunity@tencent.com 删除

函数