00:00
然后再去,有了这个基础以后再设计算法。好同学们,我们现在玩一把,看看对不对啊,来同学们,那现在呢,老师仍然把前面这一段这个测试代码我就不写了,我就直接把这个拿过来。啊,因为你这个不拿过来,你这个自己再去写一遍,太累了。OK,好,我不要粘错了啊,我看从哪粘是比较合理的。从这你看我粘代码的时候,我是这样粘的,我先定位到这个位置。我定位到这个位置有什么好处呢?我就找到它的尾部,找到尾部我再往上从这反向的截取。反向截取我截到哪,因为我知道是main函数里面,我就接到这了,有些同学解代码想这样解,他想怎么解呢,往下走。喂,齐到这这这这这几个呀。是结到这儿呢。还是觉得。一节好五分钟就浪费了,所以你有时候截代码呢,你要有一个思路啊,就是先定,比如你要第截这个命方法里面代码,你先把这个命的最后这个圆括号,大括号定下来,然后从这开始往上拉,反向拉。
01:15
拉上过去过后,然后这个就可以用了,这绝对没问题。还有包括我们在调错的时候呢,也也要用一些相应的方法,就折办法等等,好这个有了,我稍微改进改进啊,那肯定我要改了,首先我要把这个Q改成。Circle or q,这个大家应该能理解对不对?那么为了好看呢?我把这个改成四,因为三太少了。我不好测试,我也不能写的太大,周老师你写大一点,写40。那我测我我测蒙圈了呢,对不对,我就写四个。这样也比较好测,也不多也不少好,下面这个呢。秀退出I get我们都有hi是不是少了一个呀,少了一个我们我们加一个吧,诶这面还有代码有问题。
02:08
呃,代码有问题,是哪里有问题呢?哦,Head q head q,我们把它加进去吧,Had q,看看跟前面这个有没有区别呢?Hi,哦,把这个拿过来吧,同学们。我复制一个Q啊。到我们环形队列来跟上。是思路。这个地方是不是就不需要这样,是不是直接返回来就可以了,对不对。没问题吧,大家能理解吗?因为我目前这个front跟原先那个front的那个含义有一点变化,就这个front呢,它就是直接指向了队列的第一个元素,而不是指向第一个元素的前一个位置。OK。好,同学们,那现在呢,这个代码应该就可以来进行一个简单的测试了,行不行,那么就要看代码有没有。
03:04
跑对啊来各位同学,现在我们在这儿来打一个菜单啊,我们说这是对环形队列的。叫做环形队列的一个案例。好,我现在打一个提示信息,表明我们确实用的是新的代码跑一个。好,各位同学,现在我们进入到一个菜单选项了。没有任何问题。首先我们先秀一把。我发现队列有一空,没有数据,对吧?没有问题来吧。爱的添加十。收一下。没问题吧,诶这个为什么这。哪个地方没换行导致这个问题的呀。诶,前面哪个地方没有换横呢。
04:01
哦,是不是这里呀,是不是这地方我们来一个换行,怎么加一个写杠N是吧,这样好好好,看来同学们我们重新来一下。因为没有换行啊,从格式上看起来比较麻烦,来,同学们注意听来。首先我们爱的一个死受一把好,有一个死了看清楚了爱的。爱的我们再加一个20。瘦一个。好,你看这个队列的第二个元素是20,没问题,我们再来。卖的好,我们再加一个三四,注意听数一下。没问题,在第三个元素三个位置我们再加,还能加进去吗?各位同学。再加加不进去了。为什么加不进去了呢?来我们看一下啊。我先告诉大家,肯定加不进去,我一回车,他直接告诉我队列满了,为什么我明明有四个空间,但是我只能放三个元素呢?好,同学们看,因为我在刚才已经给各位同学说了,我们这个判断满的方式是这样子的。
05:09
大家看。判断满的方式,我是re加一摩马塞。那你约最先前是零。我们来看看你原先是零,原先是零的话,那么你本身就占了一个,比如说你看啊,你原先是零,我们看看这个推推一下这个逻辑啊,你原先是零。那么你加一个,比如说我们加一个元素。加了一个元素,这个RA就变成了解。是不是变成了一这个哦,这个这样看啊,当我们加一个元素过后,这个RA就等于一了,我们再加第二个元素的时候,这个RA。就变成了二是这个意思吧。好,我们再加第三个元素的时候,各位同学,这个RA就变成了三,没有问题吧?
06:02
没问题,那么这个时候当你再去取模的时候,是不是。这个因为你原先假假设这个方的没有动过,是不是你四模式就等于零了,就已经满了。这是为什么呢?因为我们在刚才已经作了一个重要的说明,就是我们预留了一个空间,作为什么呢?作为一个约定,我在这儿再做一个说明,其实在前面我已经说了,只是同学们可能忘了,大家看这里。即将队列的容量空出一个作为约定,那有些你们有些在有些同学在网上呢,也能找到有一些算法,有些算法做的也也很好,它是连一个空间都不浪费的,但是我觉得无所谓,为什么,因为一个队列,假设我们队列有20个元素,有一个空了,问题也不是很大,这个算法呢比较好理解。好,所以说对队列呢,容量我空出一个作为约定这样子的好,那现在呢,我们可以看到的确这个加不进去了,我们受现在有三个元素,现在我开始取元素了啊,各位同学们get。
07:11
取第一个,要保证取出的是十。是不是死呢?的确是十,我们数一下。现在。一二。各位,领取出来了吗?我们再来get一个。啊,这样子,我我我我们来艾特一个吧,我们来艾特一个,请问这个时候我们能加进去吗?应该可以加进去了,因为我现在就是要复用嘛,对吧,我现在来爱的,那么我想问大家一个问题,如果我加了一个事实的话,这个数据会对应这个数组的下标为几呢?零就错了吧,三才对,是不是?因为我是环形的呀。不是换环境的,虽然原先那个约定是在最后,但是当你控前面有一个可以判断的时候,取模了它不就可以用了吗?
08:03
所以这个时候加进去这个事实应该是二三对应的位置能理解,那么回车加进去了没有,加进去数一下。是不是这样子的同学们?OK,那说明是不是已经可以服用了?来,我们把它全部取出来,Get。Get。盖好,同学们,现在我们全部取出,再取这个就队列空了,我们试一把。所以现在队列为空,没有数据,我再问你讲。加我们加100能不能加进去。这个时候是又变成零了呀。好,我们再来,一样的道理啊,我就不写那么多了,爱的。200收好我们再取,就随便用了,Get这个时候get取取出来应该是100。取出100,取出来一百十五,你看这个时候我再加它,应该在二后面再加I的,我来个300。这个时候300会加在O瑞下标为二的这个空间,注意近回车试一下,诶写错了啊,这个这个不是这是我我这个大家知道我为什么错了吧,我找一个同学说一下这个原因。
09:12
是不是因为我在这地方一个都没匹配到,而我又没有写默认的匹配?是不是我们明天再讲这个match匹配的时候,老师讲过这个问题啊,啊,这个不是大问题啊,不是大问题那但是很遗憾,我这个还得重新试一遍。我再试最后一次啊,这个试完我们就我们就完事啊,来,这是我们爱的。一。爱的。二。爱的。三好,再爱的就加不进去了。加不进去了,然后呢,我们试一把。手好,正确,我们get一个。好,再get一个show一下,那么现在看到这个取到二,我们再艾特一下,再艾特一个四呢,这个时候它会加在二三的位置。好,果然是样子的。
10:01
好,那么现在我再get,我再get一个get是三。正确,那么再下瘦瘦一下。受。那么这个时候是是是我们再爱的一个,再爱的一个过呢,这个应该是放在二零这个位置,好进去竖一下,那么这个时候你看环形堆的已经出现这个感觉了,你看三三,按理说,按理说这个下面的应该比比这个大嘛,但实际你看上面的比它大了,已经缓形了,我这个再取,你看这个时取的时候呢,并并不是取的这个零,而是取的四。因为四这个时候是队列的头部,好,各位同学请看。好,同学们,关于这个环形队列呢,我就讲到这里啊,我把代码给同学们整理一下啊,把代码整一下,那上次呢,我们这个讲的内容一起给大家进行一个回顾啊,整理同学们我们上一次课讲的这个队列。
11:02
队列,我们一起将其回顾一下啊。首先。把队列这个拿过来。啊,这是队列的。部分。好对立。呃,队列呢,他在讲的时候,先给大家讲的是一个应用场景,对吧,这个场景呢,是银行排队的一个场景,而且大家感觉到还是很有用的。好,把这个去掉,这是一个场景,然后。我们先给大家做队列的介绍,队列可以用数组或者是链表来实现,那么我希望我们今天把链表讲完以后,大家呢,也可以用这个链表来实现一下队列,加强大家对队列和链表的一个应用啊后面我有一个题。队列的介绍,我们也给大家阐述到这里。OK。好,那么这地方我们总结了三点,队列,它是什么呀?是一个有序的列表,可以用数组。
12:01
也可以用链表来实现。好,然后呢,遵循的原则一定要清楚,是先入。先出排队嘛,好。这是队列的一个介绍,然后呢,我们讲了数组模拟队列的一个用法。这我没有讲链表模拟队列,是因为链表同学们还没学。如果用链表来实现队列呢?应该更容易一点啊,因为用指针来控制,只要你理解了也是很轻松的。好,我把这个给大家拿过来,那么数组模拟队列是需要同学们注意什么呢?大家看。好,这个地方我们就没写了啊,看这第一个。那么在这我们这其实是使用数组结构来存储队列的数据,主要体现在这个位置的,所以所以说你看我在构建两个队列的时候,里面都藏了一个东西,大家看到是怎么长的的看。在我写第一个队列的时候。
13:02
我这里有一个。有一个属性。在写第二个队列的时候,你看这里仍然有一个,诶在下边也有一个属性对吧,都是数组。都是数组好,所以说我们这体会体现出数组的结构来存储队列的。呃,这个数据好,第三个。啊,下面这个。好。好,同学们,你看,因为队列的输输出和输入分别是从前后端来处理的,因此呢,我始终使用两个变量,叫front和real。有些程序员呢,他喜欢把这个front取的名字叫这个也可以,有些程序员喜欢这样取名字叫hide。他把这个RA呢,它取叫tell。这个也可以,不要去纠结这个变量的名称,但是不要写AB啊,有些哥们他整个变量,他说这个前面他叫A,后面叫B,这个就很难看了啊,所以说你要么用front where对应,要么用had tell都可以。
14:08
都可以好的,那这边呢,还有一个示意图,我也给同学们阐述到这里来。这有一个示意图,这个示意图呢,也很清晰的,把它这个过程描述的比较清晰,这里面大家一定要注意哈,就说这个front Korea到底是什么含义,它到底是指向这个对立的第一个元素本身,还是指向第一个元素的前一个位置。这个要根据你的算法来变化的,所以说你会看到不同的程序员在实现这个队列的时候呢,微微微有点差距,差别就在这里,它的含义有点变化。这你自己要去分析的。好,这是我们的这个数组哦,模拟队列的一个说法,那紧接着呢,我们就实现了,用代码来实现了,用数组模拟,好,我们把这个呢,也给同学们放到这来。
15:05
好,我们用数组模拟队列,那具体来说这个思路很多,我就不一个写了啊,我把代码给他拿过来就可以了。这是我们的一段分析。那么代码呢?我给同学们摆出到这里来。这是说明。我写一个名字叫说明,好吧,说明,然后代码我给大家整整理一下,代码在哪呢?在不在这里代码实现。好的,带。代码实现OK。那具体代码实现其实就是老师写的这一段代码,就是RQ,然后DEMO,那我把整个代码给大家复制粘贴到我们的笔记中。放到这一点了啊OK。好,这是这段代码,那这段代码说完了过后,我们发现呢,这段代码是有问题的,所以说我们对它进行了优化,这写一下。
16:01
哦,对,上面代码说明对。上面代码的代码,代码的一个说明啊,第一点就说是什么呢,就说虽然实现了。虽然实现了队列。队列队列,但是数据不能复用。就是你用一次就没有了数据空间。数据空间。不能复用啊,因此呢,因此我们需要需要对其需要对其进行一个优化,优化什么呢?使使用啊,使用这个取模的方式,取模的方式实现。实现什么呢?诶这个太大了,有点稍微小一点点实现。实现这个环形队列。实现环形队列。OK。那呃,这个示意图应该是在这里呢,做了一个一点分析,我把这个呢,分析的一个示意图也给大家截过来,下面呢就是一段代码了,就没事了啊好,这是老师的一个说明,好这个说完了过后呢,我们就直接给大家写了一个用数组模拟环形队列的案例,也比较简单,好我把这个呢给大家整理一下,好吧,这是这是前面的分析。
17:25
包括我们这个思路的分析都在这儿,都在这儿,好,我把这个分析给大家放过来。OK。那具体来说,我是怎么来分析和整理的呢?这有一段分析说明啊,分析说明我用一个这样的表头啊,第一个。第一点。啊,第一点我是这样分析的。就是怎么样判断他满呢这个条件。是不是好,然后呢,怎么判断它为空呢?用RA等于方就代表为空,好,这是一个示意图,示意图就是下面老师的一个说法,好代码我们就写到这了,最后这个代码实现吧,这叫代码代码实现。
18:07
代码实现。好,代码实现,那代码实现呢,我就直接把刚才写的这段代码给同学们板书过来就可以了,叫circle r q。好。然后我们把它放到这里来。好的,就这么一段代码,最后呢,我有一个课后练习。啊,这个我已经帮你们做了,就是完成环形队列模拟队列输出,其实已经做了啊,其实已经做了,那这个呢,大家到时间把它消化一下就可以啊。这有个课后的一个思考吧,课后思考。好,同学们,关于这个队列,环形队列,我们就给同学们先讲到这里,截取一段视频。
我来说两句