00:00
那么找到这个队列呢?我们先看一下这个系数,课后我希望同学们把它存盘完成,就是虽然我这没写呢,同学们在老师基础上把悉数数组的存盘把它写下,好吧,这个呢完就是其实要不了多长时间,你们在学Java的时候应该学过文件吧。学一个文件,那稍微找点资料就就能搞定,因为文件这个你你你就完成了一小截,就是能够把我们的这个这个load load啪。一行一行的存到那个文件里面,读的时候就一行行读,读完了过后一个split把它恢复到一个no并不难啊,如果这现在连这点能力都没有的话,嗯,那应该说不过去了啊,因为你们现在不是说没有基础的同学了。你们现在是有基础的,你的脑海里面想要想我,我现在一个是一个准程序员了哈,OK,好,下面我看队列,队列呢我们先看一个应用场景。队列的应用场景呢,很多。你比如说我们叫号系统银行排队的一个案例,前面我给大家演示一个,我们再来看一下这个案例,来体会一下它的一个用法,好,我还找到我们的队伍。
01:13
OK,同学,看这有个my bank,我们再看一下这里面这个底层呢,就是用队列来实现的。来,我们运行Java。Java my bank。银行走跑起来,同学们看这个地方呢,我们就做了一个这样的效果,其实当时花了很多时间做这个界面啊,其实现在想起来意义也不是很大,但是呢,但是当时学生他作为有个界面,他认为更有应用价值,对吧,因为嗯,很多学生他希望看到一个界面,所以说花了一点时间画这个界面啊,就还是很这个界面其实不好画的,你看啊,你看我这画一个图,诶这个我们重新来一下。它这个有一个小的bug。Bug。但不影响使用啊,因为这个版本兼容就是好好早以前写的了啊。
02:05
My bank。Okay。哎,找不到那个是M大小。好,跑一个来看点一下。好,你看诶。哎呀,这个为什么比刚才还惨呢?他不对呀,这个不应该错的。这个不应该错,再来看一次,他为什么老这样子呢?来看一个。啊,Java。Java my bank走。好拉一下看看点慢一点,等一下一点是不是又又爆了。喂,你看了没有?啊,这个你看这写有点问题是吧,什么两个一号,两个一号啊,这个这个好我们再来看,好再来看,现在正常了二号。好,三号业务员为二号服务,刚才这个地方一和一同时写,这说明这个并发程序有点问题,好,并发程序有有点问题,好我们再来找一个两个三个四个,诶这个两个五号都同时抢了啊。
03:16
这说明这个代码的这个,呃,当时兼容性做的不够好。好,我们看这个时候呢,他在不停的为他服务,看这方就是一个队列,它从这个队列里面取一个啊,取一个为他服务,服务过后再买,那这个图片是这飘过去的啊,这边也很清晰,好,那么这就是一个队列,那这个队列它的价值呢,就是我能从队列手取一个节点,然后为他服务,然后再往后面,往后面往前面。对就行了,好,这是队列,那队列呢,我们来完了后,我们来看一下,看一下它的使用的一个实现。队列呢,是一个有序的列表。可以用数组或者是链表实现,就是有些呢是用数组实现,有些是用链表实现。
04:04
它遵循的是先入先出的原则,即先存入的队列的数据要先取出,后存入的数据要后取出,那么这个示意图呢,我在后面有一个,大家看一下。我这个图,这个图呢,我们先都一样。好,同学们看。这个这个队列啊,我刚才已经讲过了,我们先看用数组模拟队列。用数组模拟队列,那这个队列呢,我们有这么几个操作,大家看。因为队内的输入输出是分别从前后端来处理的,因此需要两个变量,一个是from。一个是,呃,就是一个一个头啊,一个尾。那么分别记录它的前后下标,它的一个front呢,随着数据的输入而改变,而这个RA呢,随着数据的输输入而改变,就是如果我要取数据这个头。
05:05
就就会有变化,如果我要输入数据,就会这个real就会有变化。那整个队列呢,就是这样动的,就是存一个数据。A,然后呢,再存一个数据,再存一个数据,再存一个数据,取的时候怎么取呢?从这个。头。取一个,然后它相当于这个索引呢,往侧面移动一下。我再取一个呢,诶,它又移动一下。就这么一个东西。那么这个队列里面呢?有几个问题,如果我们用数组来实现,这个队列最大的问题是要控制什么呢?它的重复使用。因为大家看,如果我们这个队列在处理的时候,它不是做一个环形队列来处理,就会出现一个什么问题呢。就会出现,如果你不停的取,最后数组全部取空了,但是你也用不了前面的这个就用不了了。
06:06
也就这个数组用一次就没有了。只用一次就没有了,这个是宿主要避免的,因此呢,第一种方式,我们先来一个简单的,然后再把它改写成一个什么呢?改写成一个环形队列,这个环形队列呢?稍微要动脑筋点,这个环形队列不是那么好想的。环形队列,你要说在没有任何提示的情况下直接能想出来还还是有点聪明的,我们先来看一个最简单的队列啊,这个队列的复用性不高,但是呢,也是我们的第一个队列,我们来看一下。先做一个用数组模拟队列的操作,我们将数据存入队列时,称为I的Q就加入队列。它有两个步骤。第一个,它的尾指针向后移动。诶,为什么向后移动呢,因为你加了一个嘛。那这里面我有一个判断,就是front如果等于RA,就代表空,就是我们先要分析出来的,也就是说现在我要做什么呢?我要做思思路分析。
07:09
这点是同学们要动脑筋的哦。就是说如果这个我这个加了一个数据,我这个尾部往后面移一下。那么移动的时候。我怎么判断它有没有空呢?就是front和rear都相等就为空,还有一个若为指针小于等于对列的最大下标,则可以存入如果这个RA尔所指的元素中,它如果啊,如果它小于等于是可以放的。但是呢?如果满了,队列满了,我们就存不进去了。好,现在我们有了这个思想过后,我们先完成一个队列的。编写好,同学们动脑筋呢,现在老师一边写,你们一边要动脑筋,这个有时候不是很好说,脑海里面要记住,记住这个图啊。
08:01
好,我现在开始写了,我们用代码来说话,这是我们的对立的一个分析。先就。
我来说两句