00:00
同学们,我们来把刚才分析的这个思路呢,用代码来实现一把,我们讲课总是这样的,先把思路说清楚,然后就写代码了,那代码呢,我们就在原先这个基础上修改哈,那这样子啊,我也不在呃这个原代码上修改,我们我们新建一个,新建一个文件,然后呢,把原先这个文件能够复制过来的部分复制过来,然后再修改,这样子呢,大家不乱好不好,好我们新建一个文件。新建一个文件,新建一个类来走一个,就叫circle。C circle啊circle,然后呢,Q。没问题吧,啊,就是环形的一个数组队列。好的,我把它勾上,我把它勾上这个DEMO吧。DEMO。DM号勾上。那勾上以后呢,有一有一些代码,肯定老师不会再重新来写一遍了,比如说前面这个队列。
01:07
其实大部分是可以用的是吧,大部分可以用好,所以说我把这个代码呢拿过来。有些地方我该改改一下这样子啊呃,为了让大家看的清楚一点呢,我这样子改这样写,需要的地方我就粘贴拷贝过来就可以了,不整体的拷贝circle。Circle r r,好,我们来看哪些需要,呃,前面这几个变量我们都是需要的。没问题吧?那么这个队列图呢?我们要分析,刚才已经分析出来这个front指向哪里呢?把这句话粘过来。没问题吧,就说就说这个方的含义,我一定要给他讲清楚,不然的话呢,后边你就看不懂老师在说在在讲什么意思了,对不对,还是指向队列头的。好,那么这个front呢?呃,说完了过后这个real的含义是什么?
02:03
注意看啊,数据结构就这么差那么一点,你就有点蒙圈,所以说我尽量给大家讲清楚。Jar的含义。Re,含义,那这个呢,含义没有变化,仍然是存放数据的,没有问题吧?好,现在我们把它的这个构造器也写一下,那构造器呢,Public。Circle a circle a里面呢,仍然给我传一个mark。Markx,对不对?人的是or max size跟上老师思路。赛制对不对?好,前面这段代码是不是我们已经写过的,我就拿来用一用。是不是验证代码呀。前面这两个我需要用。这个大家能看懂吗?因为这个front和rear呢,它初始就是你因此呢,我就这里面就不用再改了,比如说你如果要写的话,就是这样这样一个意思,就front。
03:01
等于零。数字化为0RA呢?月儿是不是也等于零了?但是大家也知道,就是这两个值默认就是零,因此呢,你这儿可以不写。完事。好,紧接着呢,我们再来写它的这一个判断,是否满,是否满,是不是刚才我已经分析过了呀。不再是这个写法了,还记得吧?是否满,就是这个队列是不是已经满了,它的它的代码呢,就不是这样写的,应该是刚才我们分析的哪一句话呀,是不是这句话。是不是这句话,这句话才是来判断我们队列是否满了,因为我现在做成环形队列了,所以我把这句话呢,就改成这句话,能看懂吗?哦,能看懂,那这这方应该是等号等号而不是负值,好这边我们也是有问题的,对吧,把它改一下就可以了。啊,改一下就可以了。好的,那这个是一负,那么下面呢,我们接着来看它的下一个是不是为空,判断队列是否为空,这个不需要变化,这边我们也分析过了。
04:11
啊,如果real等于front,就代表为空,这个没有变化,仍然是以前的代码。没问题吧,同学们。好,然后这个是否为空,写完了以后呢?下面我们来看它取出数据的代码有没有变化。哦,这是添加数据,添加数据,那我们先把添加数据写一下也是可以的,先写这个吧。那就写他吧。好,添加数据有没有变化呢?肯定是有变化的。因为你现在是环形队列了,对吧,因full这这个动作,嗯,判断不需要变化,Return也没变化,但瑞不在这了。第二在这,那应该怎么样呢?因为我们刚才讲过,RA,它是直接指向最后一个元素的后一个位置。是不是,那我们在添加手代码应该怎么写呢?肯定不是这样写呢。
05:04
应该这样写,因为RA本身就指向了后一个元素,说说直接直接将数据加入就可以了,怎么写二瑞,注意听啊,然后呢?Re,等于我们的一个N。对不对,但是你这做完以后,这个RA的指针是不是应该往后移,移动一下,对没问题啊,注意听将什么呢RA后移。后羿。注意啊,这里必须考虑取模。为什么?因为你打个比方,你这个RA已经到最后了。假设赢到最后,下面还后面,前面有空间,比如说你的瑞尔到这了。但前面是有空间的,是不是你这个要取模到前面来的呀。对不对,所以说这个往后取呢,这个RA应该等于多少呢?诶,它就应该等于real加一摩谁马塞能理解吗。
06:07
诶,这个就这个就是咱们要考虑的问题,如果你按以前的方法瑞直接加个一,那数组就有可能越见。对不对,好,这个添加我们就写完了,没问题吧,下面呢,我们接着看取出数据。取出数据肯定也有变化。是不是那么看取数据应该怎么改改改动一下呢。好,首先判断是否为空,这个动作仍然是需要的。因为他如果为空,你就不能取数据了嘛,但是这个后面这个代码肯定不对了,因为现在我们front的含义已经发生变化了。它本身就指向队列的第一个元素,是不是好,那这个就很简单,那怎么办呢?我们下面的动作应该是这里啊这里。这里。我们做点注释。这里需要分析,分析出。
07:00
这个front呢?Front是指径,是指向队列。队列的第一个元素是不是因此我们要这样做,要返回这个值的话,应该这样做的。第一步先把。Xian。先把这个front的。Front对应的值保存到一个变量,保存到一个临时变量,保存到一个临时的变量。是不是这个道理。第二步,我们应该怎么样将。将front,诶各位朋友front后移。他说,老师,你为什么要先把这个变量保存起来呢?因为如果我直接返回的话,那我front就没有往后移的机会了。对不对,第三一个动作。将临时保存的变量,临时保存的变量返回。
08:04
是不是这个道理?好,那么这个代码就很简单了,我先用一个value来保存R这个front值。因为这个只说要返回的。然后呢,Front往后移一下,注意移动能不能这样加。不能这样走了,因为你要考虑到front呢,也有也有可能是有顶,你看你front往后走走走走走走到最上面,是不是他也可能返回来呀。说你这样加加就错了,肯定会报宿主约见。肯定会报数主义,所以说这么人后移的时候要考虑起模。考虑曲模能理解我的意思吗?那front应该是写成什么样子?是应该写成front,怎么样加一个一再模上马size。这有道对不对,马克塞。因为你不考虑取模的话,那方肯定不停往上走,它最终就会越界嘛。
09:01
知道了吧,然后同学们,我们的value。搞定。好,这个就是从队列取出一个数据,好下一个方法。下一个方法来,朋友们,那下一个方法呢,就是我们显示队列数据的方法了。同学们显示队列,显示队列里面的数据,我们还能不能这样写,动脑筋。还能这样写吗?判断为空这个动作还是需要有的,这个没有什么变化,但是你这样写行不行?肯定不行了。因为你这样写实际上是把这个数组打出来,但有可能有可能前面数据都已经被取了,你这样打就没有意义了嘛,是不是因此呢,我们的思路要发生变化,下面这个就不对啊,应该怎么写呢?我们有一个思路怎么样呢?就是从应该是这样子从front。开始便秘。啊,便利的时候呢,我们要便利。
10:00
遍历,遍历多少个元素就可以了。说思路就应该变成这样子的好,现在我们需要动脑筋呢,那你想想这个应该怎么写啊,动脑筋啊动脑筋。啊,动动一下脑筋啊,思考一下,思考一下。动脑筋,那我觉得是这样写比较好,大家看啊,首先这个I呢,我们把它变成front。因为我要从开始遍历,遍历多少个呢。病例多少个呢?是不是应该这样子,Front加上。一个值,就是说这个问号就是我们实际当前这个元素有效的。元素的个数。那同学们还记不记得我在这做了一个分析,其实我在这呢,这个分析是为现在打了一个基础。队列中有效数据的个数其实是real加马size减去方的模上马size。
11:00
是不是刚才我们做做了这个分析了,那因此我们这个地方是要加这个值的。加这个值的,因此现在呢,我们需要加一个方法干什么呢?求出,求出当前队列有效数据,有效数据的个数,否则你无法遍历。否则你无法便利,能理解吗?不然的话你怎么整怎么整,因为它是个环形的呀。你不能说我上来以后就把这个数字大小吧,是不是好,那现在我把这个方法写出来,Public应该怎么写呢?刚才我们已然做了一个分析,我返回。这个大小,这个大小其实刚才我已经做了分析了,就是这句话。是不是我可以直接拿过来用?不用再写一遍了。能理解吧?马克。那也就是说real加max size减去front膜上马size。就是我们当前队列的有效个数。
12:02
那有些同学老师,我这个怎么理解呢?刚才我们不是做了一个做了一个测试吗?比如说比如说啊,RA等于一。比如说where等于方等于零。啊马,Size等于三,我们当前假设是三个,你算一算。RA加上马X等于四,四减去一个零。还是是四摩三是不是还是等于一啊,假如这个V等于零,是不是就是零个,假如面等于三啊,假这等于二不是二个,假如方等于一呢,又变成一个,是不是这个曲目它就对了。啊,对了,好,这个大家动脑筋啊,因此呢,我把这个地方就改成就完事了。啊,那么在打印的时候呢,为了好看,我们这儿给他一定的提示信息,就说你现在在打印的时候,这个信息,他要给他一个比较好看的信息才可以,那么这时我们这样写啊RID这个,呃,我看看应该怎么打比较好。
13:04
这个没问题,这个没问题,但是这个地方同学们考虑。同学们考虑。这时。他的这个下标是I吗?不一定是爱。不一定是因为你在取模了嘛,所以说现在这个下标应该是I。莫马赛。为什么?因为这个I它在做的时候,它有可能是超过这个数组的大小,因此你要取模。对不对?好,这个值应该是什么呢?显然这个地方的I就要变成它。大家看看能不能理解啊,有有一点有一点绕啊,有点绕,这个地方一定要动脑筋,就说为什么你现在便利的时候,这个下边就成I摩马塞了,因为它是个环形的。当然你这个下边是这个,那只显然对应这个就很好理解了,主要是要理解第一句话。第一句话要理解明白,好,现在我这个也写完了,写完了,那么现在显示也写了,Size也写了,我们还留了最后一个是什么呀,就是把他的这一个头元素打出来。
14:13
投元素。好,最后一个方法,我们找到最后这个部分显示投元素。显示我们这个队列的第一个元素就是对手,那么判断为空这个动作仍然是要有的,但是返回还需要加一吗?不需要加一了。原因刚才我已经讲过了,因为front本身就指向队列的第一个元素,好,同学们,那这个代码就写完了。代码就写完了,那么我们这个代码写完了过后我们能不能用呢?不知道测一下来,我们测试一把,好,现在我为了跟前面案例区分开来,我这写的是测试数组,数组模拟环形队列的案例。
15:01
是否正确,那前面这段代码我不会再重新写一遍哈,打开。是不是这个地方是可以拿来为我所用的?因为该有的这些方法我们都是一样写的吗?只是里面的逻辑发生变化了,是这意思吧?好,我把这段代码呢给同学们板书过来。好,我复制一下放到这里来。没有问题吧,同学们。好,没有,现在我把这个全屏一下啊,全屏我把这个这段代码格式化一下,因为这样看起来不好看,我格式化格式化。快捷键一下就搞定。好,同学们,现在呢,我们要在这儿还有一个地方需要改变,就是原先创建的队列是RQ,现在呢,我们要改成circle。Circle or q size呢?我们假定。还还是他啊,诶。这个累啊,没问题啊,就它吧。
16:02
好,现在这边呢,改了,这边也要做一个变化。对吧,这边有做一变化,好,现在就已经改成了一个环形队列。环形队列,那现在呢,同学们我们来用一用,看看这个环形队列是不是可以使用了,是不是可以用,我们还以三啊,注意你这个数组现在是三,其实你有效数据最多只有两个,因为我有一个空的空间,那为了好测试呢,我改成四,我这里说明一下啊,说明这里设置的是。其队列,其队列的有效数据有效数据最多。最大也可以啊,最大四级呢,13,为什么?因为我在这已经做了分析了,我有一个空间作为约定的。如果同学们不希望做这个约定呢?也可以改这个算法,只是那个代码阅读性稍微差一点。我这里。
17:01
空了一个空间出来啊,问题也不大,好朋友们,我们运行一只来测一测,看代码是否能够跑起来。好的,各位同学来玩一把。首先说一下。队列空的。没有来吧,我们添加,我添加一个十。受一下。是不是现在只打印出来第一个元素了,现在因为我第二个元素没往里面加嘛,我们再来艾特加20。我们再秀一把。是不是?20又进去了,我们再加一个吧,同学们,30。我们再秀一把。三四好同学们,如果我再加,还加的进去吗?我再加一个40。加不进去了,因为我这个三当前是处于一个预留的空间,于是我在家他会说。对里面不能加了,好现在我们取吧,我们取一下。G,请问这个时候第一个G取出来4G。
18:01
是不是死啊?应该是十对不对。看取数时,取数时我再修一下,你看现在是不是D0,宝瑞零可被取出,现在只有一和二了。那我问大家,此时此刻我在添加数据,能不能加进去?可以加了,原先是加不进去的,现在可以加。因为我现在是做成环形的,这个时候呢,它一加它会加到哪里呢?它会加到缩影为三的位置。而下标为零的位置又作为约定了,因为这个约定的位置是在动态变化的。回车我加一个30,请看。我再试一下,你看。123。好,现在呢,假如我们再加又加不进去了,为什么?因为二零现在变成了。一个预留空间,你看我再加一个70也是不行的。对吧,好,现在我多取几个啊,G我用H来测试一下,H是不是取出队列的头啊,队列头是不是20啊。是不是20好,现在呢,我们再来多取几个G,取了一个再取再取,我再取呢。
19:05
堆里为空,取不出来了。好,现在S以下这里也是空的,正确。好,现在我问大家,我往里面加能不能加是可以加的,我还又可以加三个了,50加进去了吧,再加一个60。加进去了吧,好,我们秀一下,现在应该有两个数据。我在家。70。没有问题说一下。是不是,那么我再加呢,我就加不进去了。比较就是。OK,同学们,代码就正确了,也就是说现在数据可以反复的利用了。比如说我再娶一个。啊,取一个我再往里面加。也是没有问题的。100。加进去了再修一下。好,同学们,那关于我们这段代码呢,经过验证是正确的。经过验证是正确的。好,我把代码给同学们板述一下。
20:02
那刚才讲的是分析说明,现在是代码实现,代码实现没毛病吧?同学们大家听懂了没有?如果你没有听懂,就把老师的代码好好的走一遍好不好?因为我说了有一定难度啊,其实这里面就用到了几个小算法而已,我把这个代码呢,给各位朋友板书到我们的笔记中去。板书比上去,如果不理解的地方,再把老师的视频和这一个呃,图解再看一看哦,有可能将来在面试的时候,别人会问你做一个环形队列,它的这个怎么去判断队列满,怎么去判断有多少个有效的数据?好,同学们那关于将队列做成一个环形的,用数组来模拟一个环形队列的。分析和讲解呢,就给同学们讲到这里。
我来说两句