00:00
同学们,我们来看一下,回顾一下上次课我们讲到哪里了,上一次课呢,我们讲到了这个队列,那当时呢,我们讲队列呢,是用数组来模拟了这个队列,这个队列呢存在一些问题,大家还一下,我们把上一次课讲的代码先给大家运行一下,看看问题是在什么地方,然后呢,对这个数组这种数据结构进行一个优化,好同学们,我们先打开这个。软件好,我们来看看上次课的这个问题,上一次课呢,我们用数组模拟队列的时候,存在这么一个问题,什么问题呢?大家可以看到。就是当我们给这个数据,这个队列里面存放数据的时候,在入站在这个往队列里面添加数据的时候呢,存在这么一个问题,就是我们这个数据到达了这个队列的最后的时候,这个数这个数据空间不能复用对吧?不能复用好,那么为什么不能复用呢?我们把这个代码给它跑一跑,看看问题在什么地方,来看一下。
01:10
大家回忆回忆啊,慢慢慢慢就回忆起来了。我们先把那个段代码给大家找到,我们是CHAPTER18里面的队列。队列呢,我这取的名字大家应该还有印象,是叫R这个。Queen q,这个为什么叫这个呢?因为我们当时用数组来模拟队列的,这个队列存在一个问题,那我们看看这个队列,当时呢,这个队列。存在的问题是存在的。问题是数据空间怎么样啊,不能复用,不能复用什么意思呢?就是你用完一次过后,诶它就不能再用了,我们来看看问题在什么地方,我们再跑一跑,运行一下。好,同学们一边老师在讲呢,大家一边也回忆好不好回忆一下。
02:04
来,我们运行一下这段代码。我们来运行这个代码。当时呢,我们实现了这么几个功能,一个就是显示队列。一个就是退出程序,一个就是添加。数据到队列中,还有一个就是从队列的这个头取出数据,对吧?好同学们我们来看,首先我直接用so的话呢,这个队列是空的对吧,哎,对吧,那么这个时候呢,我往里面添加数据,它让我输入一个数,我就先输一个十。输了一个十过后呢,我再试一把,我们发现呢,在它的第零个下标的时候呢,有一个数据为十正确的,因为它默认的是往这个队列的头部,呃,尾部添加,这是因为它是为空嘛,所以说第一尾部就是下边为零的这个数据空间。
03:01
紧接着呢,我们又往里面添加数据,OK,我们添加一个20也没有任何问题,Show一下。没有任何问题,然后呢,我们又往里面添加数据,添加一个30 OK,我们再秀一把也没有问题,我往里面继续添加40。好,这时呢,他说队列已满,为什么队列已满呢?打开我们这个代码,我们看一下,因为我们这个队列我设置的大小为三。对不对,那大小为三呢,我们在去构建这个队列的时候,我们指定这个大小为三,那么它最多只能存放三个数据,所以说在这时呢,他就报告一个这样的信息叫什么呢?队列已满,这个队列已满提示信息是对的。紧接着呢,我们来获取这个队列的数据,大家都知道队列这种数据结构呢,是先进先出对不对?所以说当我去get数据的时候,它优先从队列的头部返回一个数据。
04:08
那今天我们这个课程哈,还是非常重要的,包括今天和明天的数,这个数据结构都是对大家非常有用,但是咱们还是今天有几个同学没来,大概。十个左右啊,那还是比较多了,对不对,那没有关系,他们还可以看视频对不对,但是现场版和视频那那是不一样的,对不对。好,我们继续来看,那现在呢,我get一下,我们就取出。第一个就是队列的头部的,队列的尾部的数据,队列的尾部数据是哪一个呢?啊不队列的头部啊,刚才说错了,因为这个队列是从头部开始取,然后呢,我们再来数一下,我们发现呢,的确这个十就被取走了,紧接着我们再获取。OK,然后呢,我们取出的是20,我们试一下。A发现20被取走了,我们再获取。
05:03
好,这时呢,它取出来给我们再秀一把,我们发现队列是空的了,因为你都取出来了吗?但是出现一个很奇怪的现象,它告诉你队列是空的,但是我往里面添加数据的时候呢,诶,它又提示你队列是满的。是不是很矛盾呢?哎,那么这个问题是不是我们在上一次课已经给大家分析过了,因为你在这个地方做处理的时候,这个队列它是怎么长的呢?来同学们,这个队列,我们要把这个队列目前这个情况画出来,然后呢,我们进行一个优化,也需要画一个图,我们目前这个队列是这样子的,同学们。怎样子呢?假如这是一个队列,我这为了省事啊。我就这么画一下,因为它只有三个空间。所以说我把这个呢画小一点,同学们看一下。你你这个队列在存的时候呢,是这样子的,就是比如说你存那个数据进去。
06:04
存在一个一。然后呢,你又存了一个二,存了一个二过后呢,这个数据往后面挪。啊,假如说我们有一个尾指针。那么你又存了一个三,他又往后面挪。挪到这个地方的时候,我们这个尾指针就到最后了,那么我们在判断这个时候你你还有一个指向我们这个队列头的一个指针,大家应该还有印象,我们分别取的名字叫一个叫front。把这个稍微放大一点,同学们大家好看,一个是方是它的,我们叫做头指针吧,还有一个呢,就是尾指针,这个维指针当时我们取的名字叫real,还有印象吧,OK,那这个时候在取的时候呢,我们显然是从这个。这个位置开始取,于是我取一个过后,诶取到这,我把这个一取出来了,然后再取又在这取,再取又在这取,等到我们取到这的时候呢,这两个相等的时候,我们说这个时候这个队列已经为空了,但是。
07:07
这两个空间,这些空间呢,你不能再复用,因为我们在判断的时候呢,存在一个问题,大家看我我们原先写的这个伪满是。只要这个为指针等于max s减一就满了,而它为空呢,是用这个front等于RA来判断的,那这样就意味着你只要用了一次前面这个空间,即使你取出来了,你也用上了,对吧?好,现在我们有了这样一个思路过后呢,我们来谈优化的问题,好,大家现在思路慢慢的就打开了啊,打开了。OK,那么怎么解决这个问题呢?来同学们看一下,因为你现在的问题就是因为就是因为什么呀,就是因为这个数据你不能复用,那么我们现在呢,要考虑一个复用,就要用一个取模的方式,我现在写一下。
08:03
啊,分析分析问题,分析问题是因为我们没有考虑考虑数据空间的空间的复用。啊,下面呢,我们可以将将这个数组,数组通过通过什么呀,通过取模的方式,通过取模的方式将。将其。将该数组数组当做当做一个环形,环形的队列来处理。啊,环形的队列处理。诶,因为你在取过取模嘛,那到这地方我再取取模。我我用一种取模的方式,当当然这个取模怎么取模,我们待会再说一取模这个指针指针它就可以往前面再再往前面跑了。那这样就可以复用嘛,所以说我们把这个思路已经有了,那在讲这个之前呢,我们看一下啊数组。
09:08
用数组模拟这个队列,我们刚才已经写了初队列的操作,写了显示队列操作,我们还差一个操作呢,把这个写完我们再优化啊,现在我说一下,现在呢,我们我们将。我们将这个原来的,原来这个队列的一个查看,查看队列头头元素,头元素的这个代码写完啊写完。因为我们在上节课呢,没有写这个方法,有一个方法呢,还是比较重要,我们上次课没有写哪个呢,就是查看头元素,这个查看头元素的意思是只查看,但是不取出来。不取,只是查看一下图,这个队列的全部元素是什么,但是不取出来,就是不是真正的把这个数据取出来,只是看一下,好,我们把这个方法写完,我们再来谈这个优化啊,然后再优化,然后再把它优化成这个环形的一个队列,好打开我们的代码,同时呢,大家回忆一下应该怎么写啊,好,我们现在增加一个方法,在这我们增加一个方法什么呢?查看。
10:21
查看队列。队列的头元素。变数,但是注意啊,但是不是从不是从这个不是不是,但是不是改变改变这个这个队列。就是我只看这个数据,图片数是什么,那我写一个方法。而D,我们叫什么呢?Hide had q。QOK,那这个时候呢,我们也可以返回一个值,但是呢,注意这个时候返回呢,只是呃,不会改变这个队列,那么我们仍然返回一个值,Any。OK,好,那我怎么写啊,同学们看。
11:03
我首先判断它是不是空的,如果为空,咱们就不能取了,所以说还是老规矩。判断是否为空,如果为空,我们跟前面一样。返回一个异常。就说队列怎么样为空,否则呢,我们就return。Return什么呢?这个头元素大家还记不记得这个头元素应该怎么返回啊?啊,我们看一下是不是所有的数据都是存在这个RA里面的,对吧?OK,那现在呢,我们返回这个后面这个下标我们应该怎么写。各位还记得吗?啊,同学们现在呢?迷茫的表情告诉我,好像已经有点想不起来了,对不对,我们还记不记得我们在老老师在讲前面的时候,我们取的时候,你看原先是怎么取的,是get q,是不是先把这个front加一再取啊?
12:00
但现在我能,我能这样加吗?我不能加,因为这样加的话会改变这个方针是吧。那那你下次再取的时候,是不是就取不到原来那个图表数量,那我应该怎么取,是不是直接再这样写这个front加一就可以了,是不是。这样子,是不是我并没有去把这个front改变,只是取到这一个头元素的。这个元素,但是没有改变队列本身是不是好回忆一下啊,注意这里很关键,这里请大家注意啊,注意注意不要使用这个,不要不要去改变,去改变这个front的值。啊,值我没有改变,值我只是取出这个front,就是front加一,这个不就指到它的队列的头部了吗?啊,因为这个front,我们在前面讲过,Front呢,我在这写一句话啊,看一下front它这个含义是什么,它指向对立的头部。
13:04
而且大家知道我们分析出来,Front是指向队列数据的前一个位置,就它本身呢,因为初始化为负一嘛,大家想一想负一,实际上这个负一它它并没有指向这个数据的那个头部,而是指向这个第一个元素的前一个位置,所以说你在取的时候呢,总是要先加再取,所以说我这就这么去写的。好,现在呢,我们把这个加进去。好,我们把这个加进去看一下啊,同学们,我在这儿加一个逻辑叫什么呢?我们叫had。Head,好,这叫叫查看啊,查看队列头。的数据。啊,我这做一个注释,但是不改变队列。啊,不改变,不改变队列看清楚了啊,那现在我们把这个逻辑加进去,怎么写呢?各位来case好,如果他写了一个hi。
14:05
对吧,我们可以模仿原先这个写法,那就。返回一个结果,用这个队列去害的一个Q,然后呢,我们做一个判断,如果这个结果它是一个异常,对不对,Exception。如果他是一个异常,我们就把这个异常信息打出来,就是显示这个错误信息。对吧,我我们来一起回忆一下,那么怎么写呢?R也是点,先把它转成一个异常。我们在SC里面呢,Is instance是转换一个类型,然后点get。哦,连get message。啊,这写错了,同学们S。好,然后呢,这边我们写get message就可以了。好,否则我们就认为这个只是返回来了,那么我们就去打印一句话就说队列。
15:02
队列头元素值为多少呢?A值为多少?等于加上我们这个二,今天这个课呢,咱们后面这个内容啊,都比较烧脑啊,这这都是比较简单的,我们待会儿讲的一些这个比如说环形的链表,还有占,还有递归,都比较烧脑,但是呢,还是比较有用,你听完过后你感觉诶好像。有点感觉了对吧,所以说今天这个课呢,大家要认真听好,我们来试一试吧,我们来试一试,走一个来跑一跑,同学们运行一下。好。我们先来直接试用这个害的,我问同学们,如果我直接输害的,它应该提示什么信息,各位同学。他是不是告诉我队列为空,是不是现在我没往里面放数据对不对,是不是他告诉我队列为空,没问题吧,没问题,我挨着一个数据十。
16:01
各位,然后呢,这个时候我在害的,请问它返回一个什么。他是不是就返回个屎?他说队列头元素为十,那么我再问大家,如果我再秀的话,这个十还在不在?在不在在的,OK,在的,因为我没有去取,对不对,好,那么我问大家,如果我get一下。它返回一个十对吧,这个时候我再秀一下会有什么效果。是不是他告诉队列为空啊?诶对的,所以说这个害呢,咱们没有写错,好同学们关于这个害的这这个这块的这个回顾,包括对上一次课这个。这个就说单向的一个队列呢,我们就先回顾到这里,我截取一段。
我来说两句