00:00
同学们,我们继续来看数组模拟环形队列,那前面刚才我们已经分析过了,就说如果按照上面的这种方式来模拟队列呢?存在的问题是不是数组使用一次就不能用了,没有达到复用的效果?那现在呢,我们希望这个数组能够复用,也就是说如果我们从这个数组里面取出了数据,那么取出的这个空间呢,能够再次使用,就这个意思,好,那现在呢,我们先来做一下这个数组模拟环形队列的它的一个思路分析。思路分析好,那现在呢,我们还是老规矩啊,同学们,我们打开打开我们的这个图解,我们一边讲呢,我们一边做一个小小分析,来看一下是怎么来完成这个思路的。OK,来一个。那现在呢,我们写写上这样一个字,就是数组。
01:02
就是使用啊,就是使用把这个做成100%的,这样好看一点,使用数组模拟,模拟环形队列的一个思路分析。是不是好?首先我们把这个图拿过来。这个图呢,还是以数组的方式来模拟的,对不对,那现在呢,我们来做一个分析。好,思路如下。思路如下。第一个第一个首先呢,我们来把这个做一个改进。做一个改进,因为目前呢,目前我们希望当这个real这个指针指到,比如说这个real指针指到这个最后的时候。走到最后的时候,那么他要判断它的前面有有没有空闲的空间,也就是说,也就说这个front它是不是已经不在原先的这个位置了。
02:06
是不是因为他已经可能弹出来的有数据嘛,所以说我的思路是这样子的啊,首先呢,我们把这个front。Front的这个概念。front就是。Front。这个指针或者这这个这这个这个变量吧,变量的含义,含义做一个调整,做一个调整。那么我要把它调整成什么样子呢?就是这个front。就指向指向指向什么呀?数组就是应该指向队列的第一个元素了。原先这个front是指向队列的第一个元素的前一个位置,现在我们让front指向队列的第一个元素,也就是说front,也也就是说啊,这样说,也就是说。
03:00
A front。Front就是就是队列,队列的第一个元素,为什么我要做这个调整,为什么我要做这个调整,大家一会儿就知道了,一会儿就知道了,第二点呢,我们把这个RA的含义呢,也做一个调整。这个变量的含义呢,我们也做一个调整,注意听啊,如果这个地方你没有听懂,后面它的一些算法你就看不明白了,明白这意思吧,这个RA的变量的含义的,我要做的是什么呢?这个real。RA。它指向指向队列,队列的最后一个元素。哎,注意听啊,元素的后一个位置。那有些同学说,老师为什么你要做做这样的调整呢?原先这个RA是指向队列的最后一个元素,现在是RA指向最后一个元素的后一个位置,为什么我要这么做,因为我希望,因为啊,因为我希望,希望流控流控出。
04:10
空出。供出一个空间,作为什么呢?作为一个约定,作为这个约定。好,大家这两点要明白,说老师,那你你这样调整,我不这样调整,我还按以前那个思路做,可不可以也可以,但是那就跟我的思路不一样了,就说用数组模拟环形队列呢,思路也有很多,这是韩老师的一个思路,明白啊,就说我空出一个空间作为约定,那一旦这这个front和real的含义发生变化过后呢,我们现在要。来判断就是什么呢?就是当数组为空,呃,当数组当队列满时,队列满时。那么这个条件我们就要分析出来了,条件是什么呢?同学们能想起来吗?
05:00
如果是。当我们把B和RA的变量含义做了调整,那么队列满的条件就会跟以前不一样。我们以前这个条件是这样写的,还记得吧,是real等于max size减一。原先是这样子的吧。为什么原先是这样子?因为原先没有考虑到复用,那现在如果我们考虑到复用,又根据front和RA的含义做了调整,那么满足队列,队列满的时候,它的条件应该是这样子的。加一。加一括起来,注意听啊,加一括起来。过来磨。模ex exercise。磨一个size,如果这两个条件相啊,磨上一个size以后,如果它等于front。这个就是满的条件。大家看看能不能理解啊,这有点小算法。那有时候你为什么这样子就可以呢,大家想啊呃。
06:02
你,你想,你这为什么要去寻魔?因为你将来这个real条件,它是可能一直增长的。而你你这个,因为你原先是没有考虑到这个复用嘛,那现在当这个real直到这个时候,直到这个时候,假如前面有空间,是不是这个RA是有可能指到队列的。前面来的,所以说我这取了一个模。取完你这个蘑菇呢,再跟front进行一个比较,看它是不是跟front重合了。这大家能不能看懂。啊,大家想一想好不好,那么这个是满足条件那。当队列空的条件是什么呢?当队列为为,注意听啊,为空的条件没有发生变化,仍然是这样一个条件,就是如果real,它直接等于了。Front,这个就是空。你看啊,打个比方,我们原先嗯,当原先这个front和rear没有任何数据的时候,它们两个相等是不是就是空的呀。
07:08
明白啊好,还有刚才老师在这分析这个front和real的时候呢,我还我还忘了一个还还还忘了一句话就是front初始值,我们要写出来front的。Front,注意听,这个有点绕。front的初始值是多少呢?我们默认为零。就是默认为零,不再是负一了。月,我的含义发生变化了,这里大家好好想一想好不好?然后呢,RA尔呢?它的初始值是什么呢?瑞尔的初始值也等于零。啊,根据这两个条件,你们再来看是不是就就有点意思了,你看如果这两个RA和方相等,它们都为零,肯定就是空的。那么如果这个RA不停的往后走,走走走,假如啊,假如这个轴RA已经走满了。
08:00
走满了,那呃,走满了过后呢,因为我要留一个空间来判,留一个预留的一个空间做约定,假如我们这个real指向的数组的最后。最后这一个,呃,倒数第倒数第一第二个这个位置,我因因为我要预留一个嘛,所以说我让这个瑞尔加一再磨RARA,如果因为我这个空间我是要留出来的,我总是要预留一个空间。这个空间是在动态变化的啊,同学们,那你看我预留空间,假设real指向了这里。指向这这里,而front呢,在没有动的情况下,它是指向零的。这个时候我让瑞尔加一再磨size子,是不是就等于零,就等于零的话,实际上就刚好就等于front。那这个时候呢,这个队列我们就认为是满的。这点大家动动脑筋好不好?有些我说了数据结构和算法呢,有些地方是需要动脑筋的。再说一遍,假如real尔指向了这个,我们这个里面模拟的这个数组的倒数第二个位置,而front呢,目前还指向最前面,就说这个队列一个还没取的时候。
09:13
而我要预留一个空间作为约定。大家看,如果re,再加一。魔。马size是不是等于零等不等于零等于零吧,那么而front目前是不是也等于零?那么这个时候我就认为队列是满的了。因为我要预留一个空间,做一个约定,我留出来一个空间,有些算法呢可以,呃,不预留,我这是为了让大家好理解,我预留了一个空间,这个空间肯定是变化的。为什么呢?因为假如你这呃这个方取一个,那这个就不等于零,那么我这个RA呢,就有可能这个RA可能指到最前面来了,那预留的空间就始终是在RA的后面这个位置。能理解吗?好,那根据刚才老师这个思路,我们就分析出来说,这是最重要的一个思路。还有一点,同学们。
10:06
当。当我们这样分析后,分析后请大家思考。这个有效的就是队列中,队列中有效。有注意听这句话啊,队列中有效的这个数据的个数,大家能不能把这个给我想起来。就说如果我们把front和real。它的含义做了变化,而且初始值都为零,那么请同学们能不能写一个公式出来,就是这个数组中有效的个数是多少个?应该是多少啊,是不是应该是这样写的,应该是real。加上马。马减去front,诶这写错了啊,减去front,然后把这个减起来的结果,各位朋友,各位朋友。
11:03
括起来模上mark。这个就是队列中有效的数据的个数。为什么那边要取模?因为你做成环形了。你是这个real,它是有可能跑到他原先是大的,又可能跑到最前面来了。所以说我要取模,打个比方吧,你看假如现在第一个是零,第二个也是零,那么零。零加上三,假设我们是三啊,零加三减,减去一个零就三,三模三还是等于零,是不是假如?你看假如现在我的re w RA等于1FRONT。啊,Front没有取东西,Front呢,等于零,大家看是不是现在只有一个数据啊,以此类推,它总是对的。这个地方是需要动脑筋的,我说了就说你可能会觉得,诶老师怎么你你怎么一下就看出来呢,这就是经验,就说你这些就是小算法,等到大家多学几个这样的数据结构和算法过后呢,你的脑海里面也会有很多小的算法在里面。
12:15
就是说只要是涉及到像这种队列的这个曲模复用,一般来讲都会遇到这种RA加一个什么。这个数组的最大容量减去前面的一个索引,再取模,这个是一个就是大家经常用到的一个小算法。那因为老师做开发做了一段时间嘛,对不对,讲课也讲了很长一段时间,所以说这个呢。我们一下就反应过来了。你要做一段时间开发,不管你是做一年,做两年还是做十年,你经验就会越来越丰富,对不对?好,那有了这个12345这么几个思路过后呢,下面的代码就自然的很好改,也就是说当我这个思路完了过后呢,我我们我们就可以在原来的原来的这个队列上。
13:06
修改得到。得到,得到什么呢?得到一个环形队列,这是老师的一个思路,好,我把这个思路放到我们笔记中,下面呢,就用代码来实现了。好,刚才呢,我们已然把这,哎这是这吧,对吧。已然做了一个分析,就是这里。其实这个地方就是刚才我分析的一个过程,分析的一个过程。好的,那现在呢,我们把它放到这里来。对。我们怎么说的呀,通过取模的方式来实现。对不对,那么这边是老师的一个分析。OK,这是我的分析的一个过程。对,然后这个地方呢,我们还分析出来为空是个什么样的条件。这个示意图,我把这个分析示意图给大家拿过来分析示意图,这个图呢,就是刚才老师在哪里画的呀,就在这画的。
14:08
一目了然,好,这几句话大家要有一个印象。好,我把这个图直接拿过来吧,好不好,诶这样子我把这个图拿过来。哪个?这是大家一看就明白了,一看就明白了,好有了这样一个分析过程以后呢,下面我们就用代码来对它进行一个改写,好,我们把代码改写放到下一个视频。
我来说两句