当前位置：首页 > news >正文

LeetCode | 循环队列的爱情【恋爱法则——环游世界】

news 来源：原创 2024/4/26 6:08:59

兜兜转转⚪还是你❤

✒前言
- 环形队列的概念
- 拓展：生产者与消费者
一、题目描述
二、思路分析
- 🍑初次遇见她♀【是心动的感觉】
- 🍑阻碍一：队空还是队满不好区分【性格互异】
- 🍑解决方案
- 🍑阻碍二：很难获取队尾元素【我居然是第三者❗】
- 🍑解决方案
- 🍑开始好起来了【她就是我命中之人💕】
- ❤小小挫折造就永恒爱情❤
三、代码详解【爱情需要不断地磨合】
- ⌨ 结构声明与展开剖析
- ⌨ 判断队空和队满
- ⌨ 入队
- ⌨ 出队
- ⌨ 获取队头和队尾
- ⌨ 销毁队列
四、整体代码展示
- 💻C语言代码实现
五、总结与提炼

✒前言

环形队列的概念

首先要给读者普及的知识就是这个环形队列。在前面我们有讲到过顺序队列，对于顺序队列，它在入队的后让【rear】指针++，当【rear == MaxSize - 1】时，此时就会形成队满（上溢出），不能再进队元素了，可是实际上，当rear 与 MaxSize - 1】相等时，队列中可能还会有空的位置，因为前面的数据也会出队，这其实就造成了【假溢出】的现象
那我们要怎么去解决它的，这里引进一个概念叫做【环形队列】，也就是将原本队列中data数组的前端和后端进行拼接，也就是我们下面这个样子，形成了一个环状，于是就将其成为环形队列或循环队列

拓展：生产者与消费者

既然说到了环形队列，再给读者拓展一些知识，也就是在《操作系统》这一门课程中的生产者与消费者这两个概念，当然这里不会细讲，对于消费者来说，他要等生产者都生产完成后再进行消费，当这个生产者生产完成后，它就停止了它当前所处的线程，消费者便开始消费，此时只有当消费者消费完成后，生产者才可以继续进行一个生产，就这么循环往复，其实也有点像我们这个循环队列的意思。
当前生产者和消费者的概念远不如此，只是做一个引言，感兴趣的可以去了解一下

好，接下去才是正题【U•ェ•*U】

一、题目描述

原题传送门
在这里插入图片描述

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

提示

所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库。

二、思路分析

看完了题目描述，接下去我们来分析一下该如何去求解本题，经过了上两题【用队列实现栈】和【用栈实现队列】，相信你一定体会到了数据结构之前其实有着千丝万缕般的关系，只要做一个改动，就可以实现去实现某个数据结构，那对于这个循环队列，可不可以也用一个数据结构去实现呢？开动你的脑筋思考一下
可以用栈吗？栈是先进后出，似乎不太符合；可以用队列吗？这就是一个队列，直接用队列去模拟做不到；
那这个时候我们就需要去联想之前学过的数据结构：顺序表和链表

本题若是直接理论地进行讲解太过枯燥，因此给读者设置了一个情景，来帮助理解

🍑初次遇见她♀【是心动的感觉】

首先对于顺序表和链表，我们应该使用哪种数据结构来实现呢，一起来画图分析一下

乍一眼看去，你一定会觉得这不是很明显吗，肯定选【链表】呀，我们前面也介绍过了一种结构叫做【带头双向循环链表】，因此对于链表我们可以知晓其可以做到一个循环的功能，从尾结点访问到头结点；但是对于数组呢，看上去最后一个和第一个其实也没什么多大的关系，果断选择晾一边

好，接下去正式开设我们的场景

假设你现在准备前往图书馆📖，然后在路上看到了两个非常可爱又漂亮的小姐姐，左边那位小姐姐长发披肩，一声靓丽打扮，笑起来甜美可人🙆，那你一看就是心动的感觉♥；对于旁边那个小姐姐呢，虽然长得也不错，但是在一旁光鲜出众的女生旁，就不会得到旁人的关注。那对于这个左边的小姐姐，其实就相当于是【链表】；对于右边的小姐姐呢，其实就相等于是【数组】
于是你就开始追求这位漂亮的小姐姐，她呢是北方人，你是南方人；它是大四即将毕业的学姐，你呢只是一个大二初出茅庐的小青年，但是你还是义无反顾地要去追求它，于是就开始了这么一段追求之旅🚗~

🍑阻碍一：队空还是队满不好区分【性格互异】

接下去呢我们继续来看看这个循环链表的结构，看到题目的需求，我们要去判断队空/队满，这也是本题的核心所在。但是对于从下图中可以看出，当这个循环链表放满了数据后，【rear】就回到了初始的位置，和【front】相等了，此时就很难去判断这个队空还是队满

是吧，完全看不出是队空还是队满。就像这个小姐姐和你一样都是理工科的，太强调逻辑思维📏，性格不太互补，容易吵架。于是你针对这个问题想出了一些解决方案👇

🍑解决方案

有关如何去解决这个问题呢，我这里是考虑到了两种解决方案

一、在最后面加一个结点（永远保持一个结点不用）
二、加个size去解决

我们选择第一种方案去进行解决，也就是在队尾加上一个结点，此时条件发生了改变，就可以很直观地去判断队空还是队满
队空【rear == front】
队满【rear + 1 == front】
是吧，虽然这个女孩它是理工科的，当时你为了追求她你甘心作出一些改变，去学习一个文科的知识，好做一个互补，这样有了一些感性思维后就不会因为某些理论吵起来了【当然这只是你的设想】

然后此时我在这个基础上再做一些Push和Pop的操作，可以看到我进行了两个Pop和一次Push，此时【front】向后移动了两位，rear循环到了第一个位置

此时我再Pop三次。可以看到当【rear == front】的时候就符合我们的队空了

可以看到，是不是就转起来了，就形成了我们需要的环形队列的雏形
在捋了一遍思路后就觉得虽然她是北方人喜欢吃面，我喜欢吃饭，但是呢我也可以为了她慢慢改善我的伙食，多去食堂吃一些面食，争取能和她吃到一家店去，嘿嘿😆【doge】

🍑阻碍二：很难获取队尾元素【我居然是第三者❗】

但是随着这个时间的慢慢推移，你不断地去调查这个女孩，想要知道更多她的生活，于是就发现她。她。她居然后男朋友了，于是此时你就有点心慌😳

循环队列转起来了，【Push】和【Pop】完全没问题，但是呢现在我们又遇到了一个拦路虎🐅，我们尝试着去获取它的队首和队尾元素，于是可以发现，获取【Front】很容易，就是当前所指的那个元素，但是呢因为【rear】指针是在入队完元素后还有再次后移，于是想要找到队尾元素就需要找到它循环过去的那一个结点
对于链表我们知道，不是很好遍历，需要从头结点开始一一遍历过去，这就很可能会有O(N)的时间复杂度

🍑解决方案

那我们要如何去解决它呢？那就是在初始的时候搞一个【pre】指针指向【rear】的前一个结点，然后虽然入队的进行他们同步地进行一个后移，这样就可以很顺利地找到那一个队尾数据，那有同学说，直接定义成双向链表不是更快吗？你可以去尝试一下，我们是使用C语言实现，结构会复杂到你难以实现，==我们尽量是找一个简单有好理解的最优解 ==

于是此时呢，你就想着去当这个第三者，还是默默地去追求她，想着他们万一哪一天分手了自己就有机会了，但是却很担心万一被它男朋友发现了，拿着刀🔪来砍我怎么办？

于是你忧心忡忡了一个晚上🛏就是睡不着，想起了一开始她身边的另一个女孩，也就是被女神小姐姐的光环所覆盖的女孩，于是。。。。

🍑开始好起来了【她就是我命中之人💕】

对于【链队】，我们实在是很那是找到尾结点，何妨不试试【顺序队】呢
那有同学就心想，这个链表我们实现过循环的，但是数组怎么去实现一个循环呢？我们可以这样，一样是多开一个空间，此时的【front】和【rear】就不是一个指针了，而是一个下标，初始化的时候就要去置为0，然后一直入队入数据，当这个队满了之后就将【rear】重新置为0即可，获取去进行一个取模【%】运算✍

可以看出，对于数组而言，和链表差不多，就是首尾没有进行一个链接，这一点上面说过，可以通过下标进行一个弥补，而且对于访问尾结点而言，也是极其的便利，因为对于数组而言，我们只需要获取那个元素的下标，就可以获取到这个位置上的数据

你呢，吃了上次的亏，在开始追求这个女孩之前先去对其进行一个全面的调查，于是就发现她和你一样都是南方人，学文科，没有对象，那你就形象，这不是完美吗？而且长得也不错，于是又开始了你的求爱之旅🌹

❤小小挫折造就永恒爱情❤

当你开始追求她的时候，发现她的家世背景不简单，虽然长相不是特别出众，但是家中门槛很高，需要一个很优秀的女婿(′д｀ )…彡…彡

当我们使用到了这个数组后，就可以试着用它去实现题目给出的接口，首先就是队空，这个很简单，只需要判断一个【front == rear】即可，但是对于队满，我们该如何去进行一个判断呢
这里我给出了两种情况，一种是没有经历过循环，直接是第一次入队满了；还有一种则是出队了一些元素，然后由入队之后又队满的情况。那此时我们还可以使用【rear + 1 = front】吗？，很显然不行，这只能表示第一种普通的情况

那这个时候应该怎么办呢?此时就需要使用到我上面说到过的取余【%】技巧，若是队列满了，则对其进行一个取余，也就是（rear + 1）% k，其中k值得就是队列中数据的个数，在后面分析代码的时候会讲到
是吧，我们只需要切判断一下（rear + 1）% k是否等于front即可，这就是队满的情况

通过一个取余操作，就很容易地解决了我们遇上的小挫折，学习了一些知识后你也有了能力，当上了一个经理，她的父母看你就没那么不顺眼了，因此你们就开始了没羞没臊。。【呸，开始了正式的交往】

三、代码详解【爱情需要不断地磨合】

将思路分析清楚了，我们就可以开始写代码，要记住：对于程序员来说，代码并不是难事，分析好思路才是最重要的

但是呢，毕竟你们之间才刚刚认识，需要一些相处才可以更好地了解对方，因此你就假借各种理由约她出来见面，开始互相认识对方

⌨ 结构声明与展开剖析

首先还是一样，我们先来封装结构体，因为我们不知道这个队列的大小是多少，因为依旧动态开辟，然后就是【front】队首指针和【rear】队尾指针，最后的话还需要有队列的大小，也就是k

/*数组模拟循环队列*/
typedef struct {
    int* a;
    int front;      //队首指针
    int rear;       //队尾指针
    int k;          //队列数据个数
} MyCircularQueue;

接着讲讲初始化的部分，首先我们需要为一整块结构体开辟空间，然后再为存放数据的动态数组开辟空间，所以就可以想到在销毁队列的时候也要将它么【free】掉
对于【front】和【rear】记得置为0，位于数组的起始，接着就是这个顺序队的大小，函数参数中给出来是【k】，但是可以注意到，我在为数组开辟空间的时候乘了（k + 1），所以在为数组大小初始化时我们也初始化为【k + 1】，当然你也可以写成【k】，这样在后面的代码中将所有的【k】替换成【k + 1】即可，主要是用在取余的地方

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* MyCQ = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

    MyCQ->a = (int *)malloc(sizeof(int) * (k + 1));     //在数组后面多开一块空间

    MyCQ->front = MyCQ->rear = 0;
    MyCQ->k = k + 1;        //队列数据也+1

    return MyCQ;
}

⌨ 判断队空和队满

判断队空很简单，【rear == front】即可

assert(obj);
if(obj->rear == obj->front)
    return true;        //表示队空
return false;

但是对于队满的话就不一样了，除了判断【rear + 1 == front】之外，我们前面还说了，还有一种特殊情况需要进行单独判断。所以需要用到【（rear + 1）% k】
这里你其实可以带一个值进去验证一下，例如说这个【rear = 4】的时候（这里指的是下标），k为数据个数为4，最后那个是我们多开的空间，（4 + 1）% 5 = 5 % 5 = 0，所以就回到了初始位置
再看下面那个 （2 +1）% 5 = 2，和【front】的下标位置是一样的，这其实就可以证实我们的公式是正确的

assert(obj);
if((obj->rear + 1) % (obj->k) == obj->front)
    return true;        //表示队满
return false;

有了判空和判满接口后，我们就可以来实现入队和出队了，这需要建立在上面两个接口的基础上

⌨ 入队

首先已经函数就需要对这个数组进行一个判断，若是其满了，则我们就不可以入队。接着的话就是很简单的一个下标位置插入操作，你也可以将【rear++】写到[]括号里

if(myCircularQueueIsFull(obj))
    return false;
obj->a[obj->rear] = value;
obj->rear++;        //入队后队尾指针后移

最后的话就是当rear到达队列末尾的时候，就需要通过一个取余的操作将其重新回到队首，一样的操作，对整个数组大小取余即可

obj->rear %= obj->k;        //回到起始位置，构成环形队列
return true;

⌨ 出队

出队的话其实就更简单了，只需要让【front】++即可，若是到末尾了再让其回到队首，形成一个环的样子
当然在中之前你还需要判断一下队列是否为空，若是队列为空的话就无法进行出队，因为里面没有数据

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front %= obj->k;       //回到起始位置，构成环形队列
    return true;
}

和她谈了这么久，终于是相互了解了对方，接着又谈到了家庭，她的家中开出20万彩礼，你却付不起💵

⌨ 获取队头和队尾

首先我们去获取一下队头，这不难。在前面不要忘了判断一下，因为题目中是有要求的

if(myCircularQueueIsEmpty(obj))
    return -1;
return obj->a[obj->front];

但是对于获取队尾就没有那么简单了，虽然是链表简单，但是我们需要来分析一波。首先是这种普通情况，若是要取到它的队尾元素只需要让【rear - 1】就可以获取到它的位置；但是我们看下一种特殊的情况

对于第二种，就是当队列Pop了两次，然后再Push了两次的结果，我们此时需要使用【rear - 1 + k】% k来进行一个寻找，此时你就明白我初始时将【obj->k】直接设置为【k + 1】的好处了，否则这里在加位以及取余的时候都要对【k +1】进行操作，就会更加难理解，首先【rear - 1】是减去入队之后后移的位数，接着加上k相等于是走到这个数组的末尾，但是又进行取余操作的话就是因为有多种情况要讨论，这里我们直接做取余操作就不需要分来讨论了，直接进行套用
我们来带值验算一下，首先第一种【rear = 4】，k都为开出来的空间5，（4 - 1 + 5）% 5 = 3，于是就找到了【4】；第二种是 （0 - 1 + 5）% 5 = 4，就找到了队尾元素5
下面给出代码

if(myCircularQueueIsEmpty(obj))
    return -1;
// int rear = obj->rear == 0 ? k : obj->rear - 1;
// return obj->a[rear];
return obj->a[(obj->rear - 1 + obj->k) % obj->k];

可以看到，我还注释掉了一种办法，就是使用三目运算符去进行一个分别的判断，若是【rear = 0】，那就直接让其等于数组的大小个数所在的下标，若不是那就是直接让【rear - 1】其实就可以获取到了，这个取余操作在数据量小于数组个数时相当于是没做

虽然是这笔钱💴是一个不小的数目，但是在你当上了程序员之后拼搏了好几年，终于是搞到了这些钱，将她娶了过门

⌨ 销毁队列

最后来说说如何去销毁我们创建开辟出来的这块空间，这个的话其实是存在顺序的
因为obj所指向的的这块空间和a所指向的这块空间并不相同，若是我们直接先去释放obj所指向的这块空间，那么这块空间内部的a所指向的空间无法访问到了，那么这个数组就释放不掉便会造成内存泄漏
所以大家在释放申请出来的空间时也要小心谨慎

free(obj->a);
free(obj);

到这里，爱情故事也就结束了，愿你也能找到像文中这样适合你的另一半💞

四、整体代码展示

💻C语言代码实现

题目代码使用的是C语言实现

/*数组模拟循环队列*/
typedef struct {
    int* a;
    int front;      //队首指针
    int rear;       //队尾指针
    int k;          //队列数据个数
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* MyCQ = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

    MyCQ->a = (int *)malloc(sizeof(int) * (k + 1));     //在数组后面多开一块空间

    MyCQ->front = MyCQ->rear = 0;
    MyCQ->k = k + 1;        //队列数据也+1

    return MyCQ;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    if(obj->rear == obj->front)
        return true;        //表示队空
    return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    if((obj->rear + 1) % (obj->k) == obj->front)
        return true;        //表示队满
    return false;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->rear] = value;
    obj->rear++;        //入队后队尾指针后移

    obj->rear %= obj->k;        //回到起始位置，构成环形队列
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front %= obj->k;       //回到起始位置，构成环形队列
    return true;
}

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

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    // int rear = obj->rear == 0 ? k : obj->rear - 1;
    // return obj->a[rear];
    return obj->a[(obj->rear - 1 + obj->k) % obj->k];
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/