00:00
好,同学们,我们打开这个chapter,幺八,我们写一个。我们就把这个讲完,我们就不讲Q。啊,就把这一个呃讲完啊Q,然后呢,DEMO。这个地方我取个名字叫RQ,为什么这样叫呢?因为我是用数组来模拟的。这样大家就看的很清楚了。好,然后呢,我写一个object。好注意听,那首先首先呢,我要写一个类。首先我要写个类,这个类我们就叫R。RQ。首先你给我传一个这个数组的大小,Max size in。没问题。非常的简单。这个地方我写了一个类。啊,用使用。啊,使用数组,诶这个有问题啊,使用数组模拟。
01:01
魔模拟队列。模拟队列,那么有些底层呢,像奥的底层呢,有可能是链表做的。他也有可能用面表,我们用数组,那首先我们现在定义一个变量,就是max。Size等于什么呢?等于你穿进来值你是多大?我接收多大第二个。我要一个宿主。我底层是数组来做的,所以说我用数组,这个数组呢,我大小就用你给的类型,OK,你给我一个马克塞,我就用它。好,这个地方是我们存数据的。该数组。数组存放数据,模拟队列。模拟队all。对的。好。那同时大家都知道。我们这个数组模拟对立呢,里面有两个特别重要的指针。
02:02
因为你没有指针,就好像。你不知道什么时候。加什么时候取一样,所以说我有两个指针,这两个是变化的,经常一个是front,我初始化为负一。这是指向哪里呢?指向队列的。指向对。列。队队列。最前面的对立手的是前部,头部啊头部。再有一个。RA。初始化也为负一,它是指向队列的。队列的尾部最后啊尾部。好,这两个有了过后呢,我们现在就要开始写几个重要的方法,好,我们先写第一个方法叫显示队列的所有数据。
03:02
那怎么显示所有队列数所有数据呢?在显示之前,所有的数据结构里面都会有两个,两个重要方法就是判断队列是否满和空,这几个条件要先把它定下来。首先我们注意啊,首先要。编写两个重要方法就是判断队列是否满。那我写个方法啊。The is fool。服务,然后呢,这边呢,会返回一个不值。那什么事是满的呢?我们想一下这个图。想要图,当我们这个real不停的往后退,退退退退退退退到了我们这个mark size。那就买。明白意思吧,就是你已经到最后了,你还能买还不能走了啊说老师那不行呢,那要是前面这个取出来过后,他不是可以往前面再放吗。
04:02
这个是下一步要做的事儿。啊,你现在先不要去考虑那么多,你先把一个最简的事情,因为现在环形队列呢,它这个思路要建立这个基础上,你才能听得更明白,不然的话立马蒙圈。这个队列看起来简单啊,其实里面包含的思想也是有的,就是它有个曲模,最经典的就是说曲模算法。OK,那这个时候呢,我们先不考虑那么多,我们认为这个对立就用一次就完了。没问题,待会待会优化好优化,那这个呢,就简单了,我们就这样写,怎么写呢,就是这个real。如果它等于了mark size减一,为什么要减一啊,同学们?因为你的数值,你你数值能取到这个max size吗?取不到,好,这是判断满,我们再写一个判断队列是否空,诶同学们,那队列什么时候算是空呢?还是看这个图。什么时空啊?
05:02
什么是空了?是不是是不是这个front,这个front和这个real它相等就是空的呀。其实现在都是空的,因为没东西嘛。就说他不停的走,这个你你你想嘛,就是你这个front不停的,比如说你后面取取取,假设我front在这取了一个,这个电量取到一起了,大家都在一起了,那说明这个就就空了呗,是吧,就是我们认为两个都在一起就是空的。因为你。我我不停的追,我不停的取,取取到都取到你最后了,肯定就满了嘛,那就就空了嘛,所以说这个地方呢,要判断出什么为空了,这个条件很重要,就is imp pity。Empty is empty。N,那么这个时候呢,我们仍然返回一个波尔,注意听啊,就很快,那这地方怎么写呢?就是front。
06:03
如果它等于了这个RA。代码就写完了。那么有了这两个好同学们,我们显示队列是不是就很简单了呀?那就写个方法叫做数。手Q。OK,那修克我们怎么写呢?那首先你要是为空,是不是我就没法写是不呀?所以说我第一句话,如果is empty。我干什么呀?我怎么办呢?我是不是给他提示个信息吧,啊就说。这个已满。I空队列空队列空。空空的。空的无法影视,没有数据,没有数据。那没有数据是不是这个下面就不用走了吧,就就完事了。Return了,不走了。那如果它有数据,是不是我们就要把这个数据取出来呀?哎,取出来怎么取呢?对吧,取出来是不是要这样取啊for循环问题来了,大家想这个应该怎么取。
07:07
肯定是要从这个数组里面取,但是你不能从头取。对吧,我们要看一下它是应该这样子,从front。Two。刚才有同学说了很好啊,Real,大家看这个front我要加一,为什么要加一,大家看我初始化是不是负一,负一是不能不能取东西吧,那就意味着其实我这个方呢是,呃,其实它是指向了这个数据的真实数据的前一位,这点大家要分析出来,这点大家一定要分析出来,就是说一定要分析出来一个关键点。分析出来一个关键点是分析出哪里呢?就是front是指向。指向这个数据的前一个位置及不包含数据,就它本身这个第一个它是。
08:01
它这个是指向这个这个队列,指向这个队列,队列数据的前一个位置,指向队列数据的前一个位置,好,因此你在取的时候,你在取的时候,这个应该是加一。那么问题来了,这个real代代表有没有呢?这个RA是包含数据的。这个瑞尔是真正指向数据的最后一个,你看现在你负一是不是代表没有啊。这个地方一定要分析出来两两者的这个关键点,如果这个分析不出来,代码一定是一定会写乱,不是这错就那错。啊,我们还要分析出。分析出,在目前情况下,这个RA是指向。指向这个队列的最后这个数据。最后数据包含这个数据含就说呃,意思就是说你这个月这个指向的这个位置就就是有数据的。只要它指向这个就有数据,那如果没有的话,就是负一啊,负一肯定没有数据的。
09:02
好,那这个时候我们就应该是to就没问题了,好同学们我们打印出来哈。好,各位同学,这个任务不用换行,我们快速的走一下啊。好,我现在把它整个都打出来,二位。走百分号D等于百分D。那现在呢,我们这个D就是I,大家看懂没有,值就是里面的这个I。好,同学们,现在我们可以试一下了。大家说老师还没加没有加,我们看看能跑起来不吗?好,我们来玩一玩,现在呢,老师在这边写个简单的菜单啊,我们先写个简单菜单啊,我我定一个K。啊,我们快速把它写完。K就就这一个案例啊,K我们接收一个字符串,那么我这有个Y循环,大家看一下,我是一个死循环,是一个数。写个菜单啊。快速的写下。诶,这是不是写多了一个没有写多啊,那么现在我将它输入,比如说你输这个秀。
10:07
Show。表示显示队列没问题,那如果我让他输一个,就表示退出队列,退出程序。好,先写这两个吧,写完了过后我们来接收一下这个K,非常的简单。K带于SDD。点RA的一个呢,好,现在我们用kiss啊match匹配一下。如果它输入的是手,那么我们要用什么呢?好,同学们,现在有一个地方要做了,我们要初始化一个Q。对不对,我们初始化一个,初始化一个队列,初始化一个队列,这个队列呢,也很简单,就用它构建一个,咱们构建一个小一点的吧,三个三个元素的就放三个元素的啊,那么这样就是我们的一个队列叫做Q。
11:06
好,诶,怎么为什么错了呢?Oracle。哦,忘了一个六。是不是零六啊好OK,那现在调的时候呢,非常简单点受Q,那么如果这个人输的是一个退出指令。我们就退出这个系统。边退出。然后呢,给它一个零,表示正常退出,好,同学们现在看一下他能不能提出这个队列空没有数据,我们先跑一下同学们。快速的跑一个。啊,代码很简单,跑一个,那现在呢,比如说我直接写个show。队列空没有数据,是不是又显示个数据,对的,如果退出,所以就退出了,好,这个至少代码没问题,现在我们就完成一个。入队列,入队列,我们动脑筋了啊,现在只要你把这个结构搭好了,下面就非常简单,那写一个添加队列,If I q。
12:00
UE。UE,那这个时候呢,我们肯定要接收一个数,所以说我先接收一个NT吧。好,这地方返回什么,待会要动脑筋啊,首先我们判断判断是否满了,满了就不能加。那就加加一个,如果一。就is负满,我们就干什么呢,提示一句话对吧,满了过后呢,我们就提示一句话,就说这个满了队列满。队列嘛,无法啊,就是无法加入。无法加入,这个时候呢,就退出去了,一个就完了,否则否则我们就往里面加呗,那加的时候怎么加呢。好,刚才我们已经分析过来了,就是加的时候同学们看你一是尾部from的变化还是real变化。Rear变化非常好尔变化,而且rear本身它是指向包含数据的,所以说你现在要加的动作应该是这样做啊,同学们它是这样加的,首先让这个RA往后移动一下。
13:08
要加数据先。让这个RA后移一次。Real后裔。那后移你不用害怕,为什么呢?后移他也诶后。后羿。后羿,因为你前面已经判断他不会为空了。对吧,他他这个哦不没有满所说你才能后移的。对吧,你你肯定是没有满我才后移嘛,那满了我就移动不动,不动了,他还没满,所以他移动一次,好,那这个时候呢,我们放心大胆的让他后移,如果你前面满了,你再后移的不是越见了吗。所以为什么要先判断这个事情呢?很重要,好,那现在呢,我们就把这个数组拿到R瑞,直接把这个瑞尔写进去,把这个。N放进去,对的就加进去了,好,我们来玩一把,把这个测一下啊。
14:03
这一个,那么这时呢,如果它输入艾。我们就提示这么一个东西,好艾特,然后我们这提示他请输入数据。请输入一个数,请输入一个数过后呢,我用这个Q调用我们的,诶大家要接收一下。对吧,我就是一个number吧,就是一个value,好我就就简单写一下,然后STd.read的一个int,然后呢,我们调Q里面的一个方法叫做IQ把这个value放进去,好同学们跑一跑。看现在这个队列是否已经OK啊,好,现在我们受现在这个空的加。出一个数十。加受。我们可以看到现在,哎,这个地方显示为什么没有换行呢?哪个地方没换行呢。哦,这这这这这这收的时候我们没换行,把这个换行整一个好,重新来一下吧,要不然都不好看。
15:07
爱的,你们也写出了吗?提示哪有提示。提示符。行。第多少行,第13行这有错吗?哦哦哦对对对对对,说的很对啊,表示添加加这个数据啊,添加数据到队列,好,说的很好,我们再来跑一下。好。我们再来写啊,Show现在是个空的,爱加一个一加进去了,Show。好,现在队列里面有一个一,我们再加I。啊,再来一个二手是不是。第二个呀,好,我们再来一个,再加一个爱的。再加一个三。
16:01
好,我们再数是不是123,我们再加。这个时候他就会报一个对立板看啊89。队立面无法加入,So正确,现在我们再写一个取数据,因为我们这个队列里面呢,有先入先出,现在你进去的我先取出来,好把这个写完啊,把这写完好,我们再写一个叫做取数据。那这个是添加数据。添加数据到队列下面最后一个方法,把这个方法写完啊d get一个Q。那这个时候呢,我们要取数据就要注意这个细节了,取数据肯定要返回一个值。对吧。那这个值怎么返回呢?问题来了,因为这边有一个问题,同学们看啊,如果这个is empty。他没法返回值。为什么没法反值,你返回零,那你要还正位是零,你还负一也不行,那怎么返回呢?
17:00
你要要兼容这两者。哎,我们也可以,刚才说的是any。那any这样就有办法了,我们这直接一个六一个exception。大家知道我意思吗?我把这个错误信息绑到这个一层里面去,叫做队列空。这就是我们所说的异常,也可以参与。我们的这个。逻辑好,如果他为空,我们就返回,否则我们怎么办呢?这个时候动的是front。对front,那你首先让这个front先怎么办呢?往后移一位再取,否则取出来是错的啊,首先第一个让这个front往后移动一下。往后移动一下,诶,呃,我们看不对不对,我说错了。哎,我看看加的时候移动一下front,诶是要后移一下是吧,后一下没问题。啊是后移吧,是后移没问题,就是因为我取的时候从那个前取嘛,加是从尾部加嘛,取是从前面前面取嘛,好,这个时候我们就return一个。
18:09
我们就一个里面的这个front就可以了,好,我们来看看这个代码能否跑起来。好,我们把这个代码跑一跑啊,现在呢,就是把这个事情做了,就是叫盖子表示取出啊,取出这个队列的数据啊,接着是添加队列数据。OK,同学们,现在呢,最后一个动作把它写完。KS,如果它是一个get OK,同学们,那现在呢,我们直接就取一个结果,但这个结果呢,各位同学你是不能直接打的,因为它是N利类型。他在另类型呢,这个就需要我们要这样做一个处理,我们先拿到这个结果,用Q去get一个这个东西,因为每个我说了每个语言不一样,就是在这儿语法不太一样,这时呢,你要做一个判断。
19:02
如果res。它is instance of是一个exception,也就是说他如果是一个exception,我们就把这个错误信息打出来。怎么打出来呢?非常简单,res.as instance of,把它转成一个异常,因为你原先是N类型的,你要可以把它转成一个异常。转成一个异常过后呢,点get他的message就可以了,Else就是结果,把这个就打出来,就是取出结果是。取出数据。数据是好,打出来这个数据呢,咱们就是二,哎,这个地方OK了。好,同学们玩一把。来,走一个啊。走一个,那现在这个代码呢,我们就可看到,诶这时我们先show一下。空的哎,加一个一加一个一过后呢,我们show。
20:00
好,我们多加几个啊I2。二的三收好,我们可以看到队列已经满了,再加加不进去了,再加加不进去了,四加不进去,现在我们来get一下。第一个取出是一,我们说一下。果然是一,而且取的是第一个没问题,那么我们这个时候再get一个。Get的是二。再求一下,只有一个了,再盖一下。再概念一下,我们是不是取出来,这个时候再瘦是不是?队列空了没有了,但是这个地方这个空其实是假空,这个时候我加也,你看现在队列空其实是对的,因为没数据了,确实是空的,但是你看啊,很诡异的,我爱的一个东西,我加一个十,他说队列买。又是满的又是空的,大家知道为什么吗?因为我们这个地方有一个最大的问题,就是我们整个这个指针,它是移动,往后面移,移移,其实现在两个指针都指到这儿了。
21:02
两个指针都走到这过后呢,他认为你这个满,因为你满的条件判断的,就是说只要到这儿它就不行了。所以说这个地方就设计一个算法,怎么让他重新回来用下面这个东西,这要把队列做成环形的。知道吧。做成这个环形的呢,各位同学我们就明年讲啊,今年今天就不讲了,这个代码的核心思想已经在这儿了,同学们呢,可以去想一想,不难,自己稍微看一看,好没什么太大难度,那今天咱们就把这个队列先做一个初步的介绍,好我们就讲到这。
我来说两句