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

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

兜兜转转⚪还是你❤

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

五、总结与提炼

  • 最后我们来总结一下本文所介绍的内容,本文讲解的是一道力扣中有队列的相关题目,对于环形队列,相比大家都听说过也接触过,但是呢提不起兴趣去研究它,于是我通过这样一个场景将你带入到题目中,在学习如何交友过程中就把环形队列给搞明白了,数据结构其实很美妙,读者要善于去发现它的美,将它融入我们的生活中

以上就是本文所要描述的所有内容,感谢您对本文的观看,如有疑问请于评论区留言或者私信我都可以🍀

相关文章:

  • Android App开发音量调节中实现拖动条和滑动条和音频管理器AudioManager讲解及实战(超详细 附源码和演示视频)
  • 电视剧里的代码真能运行吗?
  • 让我们进入面向对象的世界(三)
  • 动态域名解析
  • 《工程伦理》1-13章汇总
  • Jackson @JsonProperty重复字段处理
  • 元组啊,不就是不可变的列表吗?
  • Java练习题
  • 蓝桥杯跑步锻炼.c语言
  • java计算机毕业设计妇女健康保健系统源码+mysql数据库+系统+lw文档+部署
  • 第十四届蓝桥杯(web应用开发) 模拟赛2期 -大学组
  • 用Python代码画世界杯吉祥物拉伊卜(附代码)
  • 大规模异构图召回在美团到店推荐广告的应用
  • 在大厂工作是这样的
  • [附源码]SSM计算机毕业设计民宿客栈管理系统JAVA
  • @jsonView过滤属性
  • 【162天】黑马程序员27天视频学习笔记【Day02-上】
  • Essential Studio for ASP.NET Web Forms 2017 v2,新增自定义树形网格工具栏
  • Lsb图片隐写
  • mysql中InnoDB引擎中页的概念
  • node入门
  • PermissionScope Swift4 兼容问题
  • python学习笔记 - ThreadLocal
  • vue2.0开发聊天程序(四) 完整体验一次Vue开发(下)
  • Yii源码解读-服务定位器(Service Locator)
  • 构建二叉树进行数值数组的去重及优化
  • 如何利用MongoDB打造TOP榜小程序
  • 使用 @font-face
  • 写代码的正确姿势
  • 原生Ajax
  • elasticsearch-head插件安装
  • 摩拜创始人胡玮炜也彻底离开了,共享单车行业还有未来吗? ...
  • 智能情侣枕Pillow Talk,倾听彼此的心跳
  • ​总结MySQL 的一些知识点:MySQL 选择数据库​
  • #pragma once
  • $.extend({},旧的,新的);合并对象,后面的覆盖前面的
  • $GOPATH/go.mod exists but should not goland
  • (145)光线追踪距离场柔和阴影
  • (16)UiBot:智能化软件机器人(以头歌抓取课程数据为例)
  • (23)Linux的软硬连接
  • (8)Linux使用C语言读取proc/stat等cpu使用数据
  • (day 2)JavaScript学习笔记(基础之变量、常量和注释)
  • (poj1.3.2)1791(构造法模拟)
  • (附源码)SSM环卫人员管理平台 计算机毕设36412
  • (介绍与使用)物联网NodeMCUESP8266(ESP-12F)连接新版onenet mqtt协议实现上传数据(温湿度)和下发指令(控制LED灯)
  • (求助)用傲游上csdn博客时标签栏和网址栏一直显示袁萌 的头像
  • (十二)springboot实战——SSE服务推送事件案例实现
  • (原創) 如何刪除Windows Live Writer留在本機的文章? (Web) (Windows Live Writer)
  • .[hudsonL@cock.li].mkp勒索病毒数据怎么处理|数据解密恢复
  • .NET 6 Mysql Canal (CDC 增量同步,捕获变更数据) 案例版
  • .NET Core、DNX、DNU、DNVM、MVC6学习资料
  • .Net CoreRabbitMQ消息存储可靠机制
  • .NET MVC第三章、三种传值方式
  • .NET/C# 在代码中测量代码执行耗时的建议(比较系统性能计数器和系统时间)
  • .Net6支持的操作系统版本(.net8已来,你还在用.netframework4.5吗)