00:00
下面我们接着给大家讲解数据结构和算法。刚才呢,给大家讲了系数、数组它的思路分析,还有代码实现,下面呢我们再看另外一种数据结构叫队列。听其名而知其对列。大家应该都在现实生活中见过,比如说你到这个电影院去买票对不对,比如说你在麦当劳去买这个吃的,那么都会排队,那么队列有什么特点呢?大家想一想,就是先进先出是不是,那这里我有我有个银行排队的案例给大家演示一下,让大家体验一下队列的这种在实际的项目中运用的一个场景,比方说我以前写的一个项目,2004年写的啊,就是很早以前了,十多年以前写的一个小项目。当时呢,也是为了让学员理解队列写的这么一个东西,用Java写的。
01:03
啊,大家看到这儿呢,一共有这么四个小方块儿,四个小方块呢,代表有四个业务员。他在等待客户。啊,来一个客户呢,他就让一个客户,呃,为一个客户进行服务,好大家看我点一下这个地方会产生一个客户的编号,比如说55号,服务完毕过后呢,我这设计了一个随机时间,服务完了过后,这个这个小圆圈呢,他就会去消失啊会去消失,好现在呢,我多点几个啊,我多点几个大家看。56号。56号被二号业务员拿过去进行这个服务,那现在呢,我再点57啊,五十八五十九。60大家看,那么这个时候,这个时候呢,我们可以看到就是每一个客户呢,每一个业务员都在为一个客户服务,现在假设我的客户很多,大家看我多点几个。
02:04
那当我多点几个的时候呢,这边就会进行一个排队,看到没有是不是67 68 69,那么这时当有一个业务员为一个客户服务完毕以后,他就会去叫号啊,你看不停的叫对吧。那服务完毕直接叫另外一个号,说这就是队列的一个应用场景。队列的应用场景就是银行排队叫号系统就会用到队列,当时呢,我们是写了一个队列来完成的。啊,应用场景,那现在呢,我们来看队列到底是一个什么东西,队列首先它是一个有序列表。它可以用数组或者链表来实现,如果用数组来实现的话呢,那么我们这个就叫顺序存储,如果链表来实现呢,就是链式存储,前面我们讲过对不对。那数队列呢?还有一个最重要的原则,就是先入先出。
03:01
就是谁先。进入到队列,那么谁就会被先调出去。即先存入对内的数据要先除去,而后存入的数据呢要后取出,这是它的一个最基本的原则,这个不能忘。那比如说同学们,我们看到。队列呢,它有两种实现方式,一种呢是数组,一种是链表。那现在呢,我们数组同学们已经知道了,因为它是一个最基本的数据结构,那现在呢,我们有一个示意图,展示了用数组模拟队列的队列的情况,大家看,我给大家放大一点,来搂一搂。同学们可以看到我这里有一个对象,有一个类叫Q。Q,那么Q呢,这里面有两个指针,一个叫RA,一个叫front RA呢就代表我们这个队列的尾部,而front呢,代表我们队列的队队对手就是队列的头部,那么初始化他们都为负一。大家可以看到,当我有数据加入的时候,你们有没有发现有什么特点?
04:07
Front并没有变化,它的位置还是负一,而real这个位置呢,在不停的往上增加。也就是说,当数据加入的时候,我们的这个real在增加,而front并没有变化。大家再看这个图,这个图,这个图呢,我们发现啊,这个红色的区域在减少,而RA呢没有变化。这个图展示的就是这个图啊,同学们看到了,这个部分的图展示的是从队列取数据的一个情况,什么意思?同学们看,当我要从这个Q取出一个数据的时候,我的front呢,是在往上面移动,而RA没有变化,这说明我们的数据在取的时候是从队列的前面取出,Front取出,而在加数据的时候呢,是RA在增加,而front没有动。
05:00
也就是说,加数据是在这个队列的尾部加,而取数据是在队列的对手取,能理解吧?好,这个呢,就是我们队列的一个最基本的一个介绍和它的应用场景。好,那么关于队列的应用场景和基本介绍呢?先给同学们介绍到这里。
我来说两句