00:00
同学们,现在呢,我们来对它进行一个优化,前面我已然讲到了,我们这个单向的队列存在的问题就是数据空间无法复用,这个问题很严重,那么我们解决的方法是通过取模的方式,将该数组当做一个环形队列来处理,那这个地方呢,就要涉及到一个算法。这里需要。需要使用到。一个取模的一个小算法,算法不难,但是你要想呢,你得动动脑筋,那同学们看,我们应该怎么去优化呢?来,同学们看,我这里写了一点东西,对前面的数组模拟队列的优化,充分利用数组,因此将数组看作一个环形的,那么我要通过取模方式实现。我先做一个说明,我有三点要说明,第一点,尾索引的下一个就说尾索引的下一个为头索引时表示这个队列满。
01:06
那什么意思呢?即我们要将队列容量空出一个作为约定。这是什么意思呢?就说我我在这儿有一个有一个空间,我是做做一个缓冲的,专门用来用来做一个约定,来判断队列满的一个条件,队列满的条件我就要这样写了,大家看tell,这个tell就是前面我们写的哪一个呢,叫做real。加一模mark size等于hi,这个hi就是前面我们写的front。什么意思,就说如果这个条件满足,我们就认为是满的。大家看一下,如果这个条件满足,我们就认为是满的。因为我。因为我这么取魔了吗?好,第二个呢,如果我们这个real。它等于front。
02:02
Front。那么我们就认为是空的。好,现在呢,同学们我画我这两个条件我们都看清楚了,大家应该能能够理解,那么现在呢,我们先把这个代码进行一个优化,这两个条件是最重要的。另外还有一个条件。就是在我们去显示和打印这个数组的时候呢,呃,打打印这个队列的时候呢,也要动脑筋。好,同学们,我们现在开始来对这个数组这个进行环形的一个改变,好,现在老师开始写代码了,注意听讲啊,稍微不注意有点有点挠头,现在我写一个新的文件,叫做circle,是不是圆的意思啊,圆形这个Q。那么这个是呢,叫环形,当然我们仍然用数组模拟,所以说我可以取个名字叫circle or q,然后呢,我们叫DEMO。看清楚了,我取个名字叫object。
03:03
赶紧做好,现在呢,我们开始写代码。那这个环形的,环形的这个队列,队列和前和前面的队列呢,和前面的这个单向的,我们叫单向吧,啊单向队列有类似的地方,有类似的地方。地方,因此我们在上面修改,因此我们修改即可。修改即可,那老师呢,有些地方我就可能要从前面地方来粘贴复制一份,首先我把这个名字写好circle。好,我们首先前面这一部分代码,就是同学们看到的这一块,我不需要做太大改变,我把它拿过来。大家注意听啊,拿过来,但是有些地方要改了,我这儿加一个。好因因为我要初始化嘛,所以说我人家叫max。
04:04
Markx sites in,我们慢点啊,那这个地方有一个改变,这时这个front和rear呢,我要做修改。我要把它改成什么呢?同学们,我要把它改成零。好,各位,我要改成零,那么一旦改成零过后,这个front呢,就指向队列的头部了。OK,就指向队列头部,那么这个RA呢,指向队列的尾部。这两个含义有变化,就是一个就是队列的头部,一个是队列的尾部。好,OK,那待会儿呢,我们可以看到这个变化在什么地方,好,这个一个是指向对立的头部,一个是指向对立的尾部。队列的尾部,那现在呢,我们来对这个进行一个处理的时候,同学们看一个is for,还有is n p,我们呢,都要做一个相应的。
05:02
相应的这个处理好,我现在开始来写这个代码啊,首先呢,我们先写这个判断队列满的一个方法。这个方法前面我已经说过了,叫is for。那这个时候什么情况,他表示满了呢,就是刚才我说的这一句话啊,就是他的他的这一个刚才不是分析出了吗?就是real加一模上马赛。等于如果这个条件满足,我们就认为它是满的。因为我涉及到一个取模的问题。好,就把这个做一个判断,如果这个条件成立。啊,其实我现在这个直接写也可以,那就直接不丁。大家看这个对不对啊,好,我们再来写一个满判断队列满。
06:00
队列满的这个条件。是什么条件呢?就是D。哦,判断对立空,对立空。判断队列空的条件,我就写示is empty,诶,这个地方。走,仍然返回一个什么字呢?不字不。那什么时候代表它为空呢?就是RA,它的尾部等于它的方子。好,那你比如说现在我两个,一个是零,一个是零,两个都为零,就代表它目前为空。目前为空,好现在呢,我往里面仍然写下面D下面的方法,下面的方法呢,我们来写一个往里面添加的操作,好我们看这个添加我们会做一个什么改变,来看一下。添加。添加数据。好,方法名我也不改了,来了一个N。拉力根,拉力根,首先我仍然判断是否为满的,如果伪满队列无法加入,直接返回。
07:06
那么这个时候同学们看,我先问大家。因为你这个re是零,是不是这个零目前本身还没有放数据,因此你在这加一就是没有道理了,你该怎么做呢?同学们,我们应该这样做。将数据。将数据加入的时候直接这样写就可以了,找real。等于我们这个N加进去了,然后往后面挪,注意听,然后向。然后将将RA后移。后移注意听啊,这个有点有点少了,我这样写大家看对不对。Real加等于这样写行不行?不行的,你这样写为什么不行,因为你这样写的话,他一直往后面走,那那你等到他走到这个队列的,就是走到这个队列的最尾部,不就是不能它就不能再走了,数据就越界了,是不是他要走的时候,他这个走法应该这样走了,就是应该是等于什么呀。
08:14
加一模我们的马克。这个能理解吗?因为你想一想这个道理,因为你后面走到最后的时候,假如前面这个数据已经被取出来了,你再一取模,是不是这个RA就可以往后面把,往后面就是把前面的那个已经取出的空间又当作新的队列的尾部。这点大家能理解吗?有点难是不是?其实这个还不算难啊,同学们,但是你们要动脑筋想想,这里必须这里必须考虑取模。取,如果你不取,魔肯定是玩不转的。好,添加改变就在这里,那同样我们取,我们现在有了这个数据过后,我们还要写一个什么呢?取数据,取数据的方法前面已经有了,我们在这方也相对来做一个,来在这稍微的改一改。
09:15
啊,因为有些呢,我觉得没有必要重完全重写的啊,就取出队列,队列的这个数据。取出对待数据仍然是要满,仍然是要这个按,按什么呢,按照先进。先进。哎,先进先出的原则,那同学们想一想。是不是我们呢,要判断为空,如果为空是不是就没东西取了,是吧,这个没问题,那我问大家方加一这个对不对。你看你原先这个为零,你能取东西吗?是不是取不出来呀,所以说你不能加一,你就应该怎么样呢,这时我们要理解,这时。
10:03
我们一定要分析出来,这里我们需要分析。分析出来就是我们的这个front已经。已经指向了,指向了这个元素,指向了第一个队列啊,应该叫队列的头元素,因此呢,你不能加一,你既然这样写,应该怎么写。你你应该怎么做呢。应该怎么做?是不是先把这个队列的头元素先保存一个变量,然后这个方的后移,是不是应该这样子的第一步先。先把这个front。对应对应的数据保存。到一个变量。变量,然后第二步将front后移。
11:01
是不是要后移?你不后移,是不是大师再取的时候取不到了吗?后羿,好,然后第三步返回。注意听啊,第三步返回前面保存的这个变量值。好,同学们看我的思路啊,看我的思路,首先我先保存这个纸拿到。比如说我取了一个值叫八六。那么我怎么取出来的呢?显然是里面的。取出来了。第二步,后移。后移,后移仍然要注意这个front,在后移的时候也要考虑取膜。你不取摩托车,那不能复用了吗?所以说这个时候呢,我们要这样去取,这样去改变,Front等于front加一。模我们的马,这点要分析出来,然后return value。那有些同学说老师,有些同学可能会想说,老师你这个有病了,你还不如直接,你直接把这个字返回就行了吗?我如果直接返回,我下面没有机会执行这个动作了,明白我意思吧,说我必须做了一个,相当于做了一个变量,先把它暂时保存,然后你再返回。
12:17
这点呢,大家要注意这种写法,好,同学们,那这个盖Q我们就写完了,现在最难的问题来了,显示队列。显示队列,这地方有点难。有点难。周老师,为什么有点难呢?因为我估计有些同学听到这已经有有点懵了,因为你想一想,它那个数据到后面又返回去了,是头是尾,自己都蒙圈了,你知道谁是头谁是尾。是不是?好,没有关系,听我讲啊,听我讲,我们还是把这个拿过来。还是拿过来我们来分析啊,郭同学。来,同学们,那你想一想,我们第一个动作是不是也应该这个,这句话需要改变吗?不需要,你是不是还是要判断为不为空吗?你不为空是不是就没法去吗?下面的问题是在这里。
13:09
你这样取还行吗?不行了,你这样取你front加一,没准这没准,这个front都大于re了,你信不信?因为你比如说打个比方。比如说你这个front取取取取到这来了,然后呢,Real再一加,啪,把数据加到这去了。好,这个时候from这个RA,这个from,诶比如说这个加上这就改变了啊,这个RA在这儿,From在这。没准你这个RA还比这个书上的小呢。说是你现在这样去肯定是不行的。那应该怎么取呢,同学们?也要取魔?也要取魔,那这个时候这个取法有一个比较关键的地方,我是这样想的啊,这种取法肯定是不行的,我我有个思路,大家看看这样行不行啊,我有个这样的思路,我们这样想,能不能说我们是仍然是从这个方开始取,这肯定不会变,我还是从分取,这个没问题,因为你。
14:16
你保证要先进的先出吗?肯定是从正方取我们,然后呢,我们四个是取从分的取,取几个取出几个元素。是不是这样就变得简单了?就说就说我现在只要从方开始取,取几个元素。不就完事了吗?在取的时候,我再把这个值进行一个取模。来操作就可以了。也就是实际上我是这样想。怎么写呢?我这样写,就说这个这个词我仍然不变化,然后呢,Front还是front,然后呢,我们这个until,比如说until取几个元素。
15:01
这肯定代表我要取几个元素。取出多少元?取出多少个?那就是肯定是front。加吗?加一个赛字。然后这些地方我们在取的时候,这边这个数据这个I这个值,我在用模的方式把它弄出来就行了,就说这样子的啊,大家看我的这个思路对不对。好,那我们就写一个队列的数据,数据。哦,我们这写数据,我们就这样写啊R。然后这个是它的下标。没问题,这个是他的词。没问题。然后我在取的时候呢,这个I。我在取的时候肯定要按模的方式来走。看看这个理解吧,然后我们在这个的时候呢,仍然这里面呢,把这个下标放进去就可以了。
16:05
这个下标对应的这个值取出去就可以了,因为你在加的时候有可能已经超过了这个马克赛,关键就是这个地方size怎么取。好,这样就涉及到算法了,我把这个先删掉了啊,同学们。我要删掉了。这里有有点骚扰啊,现在我们有一个比较重要的方法,就是如何返回,就是返回或者要求出。求出当前这个环形队列。队列由。几个元素?因为有些描述你取了多多少少,你不知道好这个地方就需要有个算法来下次。注意听,然后返回一个int,怎么算呢?怎么算呢?好,同学们看我这样写,你们看能不能理解啊?大家看,我这里有一个核心的就是尾部加上马克赛减掉头部。
17:04
尾部就是说大家看我,我把这个先拿过来,然后呢,我给他说一下。大家看到这里,我写到这写到这,我把这个改一改,改成我们对应的代码啊,那同学们看我这样写。这个尾音就是我们这儿的real。然后呢,Mark size不去改变,然后再减掉我们这个front。啊,然后再磨上这个马克size,我们来看这个能不能。正确能不能正确。好,能不能正确呢?我们来看一个实际的案例,我们先以最简单的这个零零来比较,比如说目前是零零,我们先看这个最简单的啊,就说当我们还没有做任何操作时,这一个方等于零,RA等于零,看看对不对,那就是零加上马克赛为三,就是三三减去一个零三。
18:02
整个这个仍然是三三模三等于零正确。正确,好,我们紧接着再来做一个。判断,假如我加了一个一我我加了一个数据,加了一个数据,我的动作是这样做的。是RA往后面移了一下,那这个时候,这个时候RA等于几呢?假如说加了一个数据。这个就等于一了。那么这个时候front呢?没有改变等于零,我们看对不对啊,就是零加上马克塞。那马赛当前是三嘛,大家看一看啊,目前这个马赛注意听。等于三,我们看对不对。那就是一加三减掉一个零。等于几呢?等于四,四模上这个三是不是等于一啊,正确的。肯定是正确,然后下面呢,你们再去推一下这个环形的也一样,因为环形它这取了膜了嘛,那取了膜了当然还是正确的了。
19:05
啊,还是觉得说这个地方呢,就要去考虑这个算法,这个算法呢。你要可能要动脑筋稍微想一想。好,同学们,这个size有了,那同学们这个地方我把这个包起来,好现在代码。就算是写完了再看一下啊,这是front,从front开始取,取多少个呢?就是加塞之个,而且大家注意这个on t,它是包含这个数还是不包含这个数,还有印象吗?不包含不含,不包含就对了,是不是不包含就对了,因为这才是我要的,但同时我在取的时候,我也是按照这个取模的方式来找这个下标的。因为这才是它真正的下标。这才是它真正的下标,好,我们多说无益,我们来测一下好不好,我们来测一下这个地方是要大家动脑筋的,这需要动脑筋。
20:02
这需要动下脑筋。动脑筋的这个地方呢,也需要大家动一下脑筋。动脑筋。啊,但是有些同学老师你这个为什么你这突然一一说我就我我还没反应过来,这是为什么呢?我跟大家说清楚啊,今天这个课你重点是在跟着老师的思路先走一圈。因为我我没有办法,比如说我们讲一个二叉数,这个二叉排序数,或者讲一个平衡二叉数,我还跟你讲这个东西是怎么来的。这个就讲的多的很了,就是问就说你在听这个算法的时候呢,第一步对于我们没有接触算法和数据结构的,你先跟着这个思路走。然后自己能能够干什么呢?做一点就是理解,理解完了第三步,你呢,不看老师的代码,噼里啪啦写出来,慢慢就能形成这个数据结构和算法的一个思维。
21:03
就好像所有老师,有些老师去讲这个。讲这个。这个排序,呃,排序有很多排法,比如说我们说有快排。快速排序,那快速排序这个算法它是怎么设计出来的?不是老师在讲课的时候设计出来的,是别人已经把这个算法设计出来,你只是实现而已。所以你能理解他实现就就可以等到你有一定基础了,你然后才能做这样的事情,什么呢?等到你有基础了过后,你才能做这样一个工作,当你有一定这个算法基础的时候,你才能有这个问题。才有你的这个需问题,或者是一个需求。需需求。就是当你有一定基础以后,你才能在问题和需求出现的时候自己设计算法。是这样来的,就你自己都不知道,哎,哦,原来人家还有一种这个叫做这种方式来玩取模,就是这种,当我们要把一个数组当做环形来处理的时候,其实他都是按照这种方式来处理的时候,你接触过一次,你后面再去遇到这种问题的时候,比如说。
22:14
下次又有一个问题,说你的老板或者一个实际需求就给你个宿主,但这个数据要当成环形来用,哦,你突然想起,哎,以前老师讲过这种方式,诶,你就有思路了。当你没有没有见过这个的时候,你只能先听。然后理解,然后再去,有了这个基础以后再设计算法。
我来说两句