346_尚硅谷_Go核心编程_数据结构和算法-数组模拟队列分析.avi原创

好，同学们，我们接着前面讲的内容呢，继续为大家讲解，那前面呢，我们讲了这一个系数数组的一个用法，对不对，那现在呢，我们来看另外一种比较常见的这种数据结构，也是同学们呢，在前面经常用到的一种数据结构叫队列。大家还回忆一下，我们在前面讲这个RA的时候呢，我们其实也遇到过这个队列的这么一种使用，对吧，那队列呢，它是一个也是一种经常使用到的一种数据结构。因为在我们现实生活中，包括我们在编程过程中都会存在这样一种应用，什么呢？就是以这个队列的方式来对我们数据进行一个处理，你比如说排队。对吧，在我们在做过做这个东西的时候，我们经常会有一个排队就说先进。先进的咱们就是你看，比如说进来一个人排在。

先进的就先出去。打个比方，有一个人排队了。你做一个交号系统，先来的人他应该先被服务，后来的人呢后被服务，你别整反了，对吧，整反了就先来的一直在等着，没人管他，后来的全部往上怼，那这个系统就出问题了，这个排队呢，这个案例就是这样子的，非常经典对吧？非常非常的经典的一个，这是队列的一个使用场景。那么大家想一想，在我们编程中还有哪些？会用到队列这种形式呢？还有哪些用到队列形式呢？你比如说最经典的大家还知道，就是像我们这个留言对吧，留言一般是谁先留言，总是排在前面是吧？当然是排序了就排序，那还有很多其他的用法了，很多其他用法，那队列呢，有这些用法的话呢，我们来看一个案例，这队列到底是什么？首先呢，队列它是一个有序列表，注意啊，我这儿所说的有序，并不是说它一定是按照从大到小，从小到大的那个叫排序，所以有序指的是它的这个数据呢，是按照一定顺序来排的，就是你先进去的呢，就是排在前面，后进去排在后边，这个呢，我们称之为有序列表，它可以用数组来实现，同样也可以用链表来实现。

相对来说哪种实现比较难一点呢？准确的讲，链表实现要比较简单，链表实现相对简单，数组实现其实相对麻烦，尤其是对环形，环形数组来实现一个这个队列还是比较麻烦的，待会儿大家理解起来有一定难度。啊，理解起来有定难度，那么队列还有一个最重要的特点，它是先入先出的原则啊，先入先出，就说先存入队列的数据呢，要先取出来，后存入的数据要后取出来，我画一个示意图。

我来画一个示意图，帮助同学们理解。来吧，同学们，这个示意图呢，大家看一下怎么理解这个队列呢？OK啊，郭同学，这个叫队列。对立。我们就以我们就以数组的这种方式来给大家看一下这个队列啊队列。以数组的这种形式来给大家看一下，对你比如说现在呢，我们有一个数组。各位同学，假设我们这有一个数组，这个数组我这样放吧。我这样放啊，这这样横着放，大家看起来更看起来更清楚一点，好比如说这个数组呢，呃，它是有这么一些，有有有这么一些数据在里边，它这样子的，这是个数组。那么这个数组，呃，这个数组当成队列的话呢？假设它有三个元素。它一共可以存放三个元素啊，四个元看几个啊，五个元素。

一共有五个格。有五个格，这是12345，有五个格，当我们存放数据的时候，比如说同学们假设这个小圆圈是一个数据。那么我们我们这个数，我们数组本身它，呃，数组本身它应该也是一个有顺序的，对吧？诶你可以放到这，比如说就是它的第零个。这是它第第零个元素，这是它第一第一个元素，这是它第二个元素。对，这是它第三个元素，这是它第四个元素，第四个元素就是其实就是第五个元素了，那么我们在放数据的时候，它应该这样存放的，注意听啊，首先呢，在它的第一个位置存。这是他的，对，这这个相当于是他的这个队列的对手，就他第一个最最前面的。对，然后呢，我们再放数据的时候呢，要在它的后面放。啊，又在它的后面放，比如说我又存放一个数据，要存在这后面我再存放一个数据。

又在这个后面存放，哎，又在后面存放。诶，这个没有没有粘贴复制上啊好，就是这样子不停的这样存放，那么取的时候是怎么取呢？取的时候是从最前面取。曲总。这再取一个取走。再取一个取走。再取没有了，周老师，这个数组不是后面还有吗？不行，你要那么去说的话，那就不是数，那就不是队列了，它是个数组了，纯纯的一个数组，这边有个问题啊，同学们。当我们原来数组有三个的时候，注意听听大家思考一个问题，就说我们原先这个数组里面有三个元素。当我们取走一个元素的时候。取走一个元素的时候。那么其实这个数组呢，这个数组。这个数组的这个队，队列的对手就变成它了。

就他就变成对手了。就这个是变成我们的队列，队列的这第一个第一个，那么这个这这种这种形式呢，有一个问题大家看到在默认情况下，有一个最大的问题是什么，大家看到啊，假设这个地方再取走一个对手呢，就被到这了，这个时候我们又往里面加数据，应该在哪加呢？它其实是在这个皮革后面加。它往那边加，哎，再加一个，再紧接着他又加一个。再加一个，所以它有对手和队尾，队尾呢是在哪里呢？就是它总是指向最后的。他只用这个最后。哦，最后是他的，呃，最后的这个这个元素，对尾是最后这个最最后这个元素。那么有一个问题就是说，当他这个时候都存完了时候，如果我再放一个数据。我再放一个数据，就有一个问题。

苏老师，我再放一个数据，我放哪儿呢？后面没有了。他说，队列已经满了呀。其实你前面还空了两个。怎么处理呢？这个时候就要算法了，就是这个就叫环形数组。在默认情况下，我们这个这个数组来模拟一个队列呢，这就已经这个这个数组就这个这个队列就没法用了。没法用了。说这里面有个问题，说如果我们用数组来模拟这个队列，它存在一个最大的问题，就是说你怎么有效的利用前面的这个空间，当然有同学曾经这样说过，说老师你这样做不就完了吗？你。你你这样做不就完了吗？他是这样子一个思想啊，他说老师你看啊，你这样不停的往后面推，推，推到后面你确实没法放了，但是前面还有两个空间。前面两个空间，你把它放到前面不就完了吗？你放到前面，这里面就涉及到好多东西在里面，你怎么去？怎么去找到前面，因为你你到最后面，你要去找前面，这就涉及到算法了。

你怎么能够在这编辑的时候还找到最前面这个，这是一种思路，这个这肯定要设计的算法，这是一种思路，那么有些同学老师你能不能这样子简单一点，我知道怎么做，他说这样子做，他说你看啊，你先不要这么去玩它这些元素你就先放这你现在放了一个元素精确好，第一个，第二个，第三个好了，现在呢，假设有一个人取走一个。你赶紧前面挪一下。不就后面还有空间吗？如果你这么做的话，这个效率就极为低下。这个你要这么做的话，那就彻底完蛋，假设我们这个数对立很大，你移走一个，你整体往前面移一下，你试试看。那这个就就就我们就彻底的就不是数据结构，你不你不用数据结构，没准还快一点。啊，因为你你想你将来这个速度很大，假设我们有一一千个数组，你移动一个，你把整体就19个往前面移，再移动一个整体往前面，你速度有多慢。

说这样子肯定是不行的。所以说那个这个方式是要打住啊，先跟大家说清楚，这种方式不行，那么有一个问题就是说咱们怎么去实现有效利用这个空间，比如说到这地方呢，咱们这有十，这有这有三个数据，这三个数据好，然后呢，这个地方前面还有两个空间怎么用，这个就叫环形。用环，这个就叫用数组来模拟一个环形队列。待会儿呢，我们会去重点讲好同学们，那么现在呢，相当于说我们用数组来实现对列，有两种形式，第一种比较简单。第一种简单，但是呢，它不能有效的利用数据，数据，呃，不能有效的利用这个数据，我们先把第一种实现。然后我们再说这个环形的数组，来用环形的这种这种思想来实现我们的对立啊，第二种方式呢，是比较。比较骚扰的啊，那个不是容易很好理解，那个东西相对来说有有有一点麻烦，但是呢也还好也还好好，现在呢，我把这个东西给大家分析，在这个地方，我们来整理一下这个队列的概念和它的一个介绍，好刚才呢，我们讲一下队列的一个在哪个地方有可能用到的啊，就是队列的一个应用的场景。

好，整理一下咱们的思路，这叫队列。OK，队列呢，它有一个专业的术语啊，叫Q。QUEUEQ啊Q。那这个单词就是队列的意思，那以后你看到Q的话呢，就知道人家说的是队列啊，是我们的一种数据结构，好，我把它放在这里，同学们A放在这里标题二啊标题二。来一个标题二，那我们刚才看了一个应用的场景，队列的应用场景，其实很多队列的应用场景，对，那刚才呢，我们看了一个应用场景，就是银行排队，这是最经典的案例啊，比如你们经常呃在那个，比如说一些商场里面去，对吧，经常会说诶。

呃，什么什么叫你吃饭了，以前不是那个排号吗？是吧，姥姥叫你吃饭了，外婆叫你吃饭了，外婆家不是那么干的嘛，对吧，他肯定里面就跑了一个队列，那这个队列做完了过后呢，我们可以做很多东西啊，就可以做很多有意思的东西了。好的应用场景，第一个，第二个呢，我们对它做了一个基本的介绍。哎，说了一下队列的一个介绍，还有画出了它的一个简单的用数组来实现这个队列的示意图。我们用链表啊，用用四组使用数组。使用数组模拟模拟啊，模拟这个队列的一个示意图。对的示意图。好，同学们呢，今天这个课啊，其实你要认真听还是很有收获的，那你要你要觉得这个没用，那就确实没有什么用啊，因为数据结构差一个最大的问题就是说你听完了过后，你感觉好像不像你学一个框架，比如说你要学学框架，诶我学完框架过后，我就知道他可以干什么了，数据结构呢，它有时候有时候他是感觉好像不知道在哪用啊。

好，对于我们这儿介绍的第一点。对第一点，然后呢，它的特点是有这么几个啊，第一个遵循先入先出的原则，这个必须记住啊，就说以后别人问你队列它的特点是什么，这个你必须答上来是先入先出。啊，第二个呢，你要答上来，就在我们编程里面，我们用队列一般用什么来实现呢？用数组或者是列表，这是两个基本常识，你这两个答上来过后呢，别人至少知道，诶这个人应该知道一点对立的东西，他知道你有有有一点计算机的一个底蕴，对，好，然后呢，我把这个示意图给同学们也放过来，好OK，那示意图呢，我就先画第一个。哦，画到这里来。那么一般呢，会有一个对手啊呃，时间的形式呢很多啊，对手对尾好这几个先暂时不要了。

这是它的一个简单的示意图。好，我把它截取到咱们的笔记中去。好，先把它放到这儿啊。好，同学们，我先放到这里。有了示意图过后呢，我们就要准备来写代码了，这个是我们一个示意图，下边呢，我们就来看一个具体的对不对案例。那么我们看看这个案例呢，就是数组来模拟这个队列，咱们嗯，先说第一种就是。呃，不是那个环形的，怎么来实现呢？大家看这里我有几个概有几个思想要说清楚啊。第一个我们要聊到这里，队列本身是个有序数列，若使用数组的结构来存储队列的数据，则队列数组的声明应该如下。首先呢，你应该有一个max size，就是表明我这个队列最大的容量是多少。

你想想到吗？你不管怎么样，这个队列假设只最多能存放五个人进去，五个数据你不能存六个。即使你是用环形的这种事情来做，它也是有个大小的，就好像我们这个去排队啊，排到一定程度的时候，你看那个地铁你看就得关门。对吧，不让你进去容量就已经满了。所以呢，肯定有个马赛，第二个，因为队列的输入输出是分别从前后端来处理的，因此我们至少需要两个变量来表示它的对为和对手。就第一个和第最后一个，那么我这里用的是front和real啊，Front就是前端嘛，Real就是尾部，尾部尾巴，尾巴分别来记录，注意听啊，我把我把我的思想说清楚，用这两个呢，分别记录对立的前后端的两个下标。OK，那么这个front front就是对手，对手会随着数据的输出而改变。

你输出就是把它搞出去一个嘛，那做完一个你取出来一个过后呢，Front就会往往后面移动嘛，那么RA呢，是随着数据的输入而改变，就是当我加入一个数据的时候。那么我这个RA呢，就应该往后面挪，就它其实是一个是输出，一个是输入啊一个问题，那你大家看一下这个图，大家看这个图呢，可以看到我的一个基本的思想是这样子的啊。注意听我的一一句很重要的话，就说关于用数组来模拟队列呢，思想基本上都是这样思想，但是具体实现还是略有差别，比如说以前我们在学这个大学学这个数据结构的时候呢，诶，他是这么一种方式实现，等到你参加工作过后，你发现有一个人，哎，他是那种实现的，但整体思想是差不多的，你看我的思想是这样子的啊，所以你跟着老师走，首先呢，我这是一个宿组，大家看这里是个数组。

这个数组的大小是max size。为什么要减一，因为它下标肯定不能到最大的一个值，这是基本常识，那么我这个就代表一个Q，那么它这里面呢，Front和rear呢，初始化为负，负一看清楚了，负一好，当我们往里面放一个数据，大家看这个地方代表是在放数据，扔数据扔的时候呢，你看我整个这个。Front是没有移动的。在扔的时候，这个front是没有移动的，谁在不停的移动呢，这个RA，所以大家一定要非常清楚的知道，这个RA呢，是在随着你的数据的添加而后而往后移动，而且大家注意一个重要特点。在我这个思想里面，这个RA其实就是指向这个。队列的最后，而且包含它，含它就是真真真真正正的指向了队列最后，而且RA呢，就的确指向最后一个数据。

但是大家注意，宽敞。这个front呢，它是初始化为负一，其实它在没有加的时候，它是没有动过的，所以这个front呢，它其实相当于是指向的队列的前面，而且并没有含包含第一个元素。这一点如果我们没有清楚的话，待会你看老师代码可能就看不懂了，就是一写就容易蒙圈。好，待会儿呢，我把这个说清楚啊，那么一旦取数据这个方和面移，那么大家看到当指到二的时候，其实这个数据已经取出过了。二去，去走过了，它相当于是指向这个队列的最前面，但是不包含那个元素。啊，这是我的一种设计想啊好，有了这个东西过后呢，有了这个东西过后，我们来看一下具体的这个思想，来，我们来把这个数组模拟队列的思想先说清楚。好数组模拟队列的一个思路。

先把它聊到这里来。好，大体的呢，就是刚才老师已经说过的这么两点对不对，2.1个是它是一个有序的数组。然后呢，它的变化是由这两个数据来体现的，一个是对手，一个是对尾，没问题，我把它保存在这里。好的。好，有了这个东西过后呢，我们下面就来看它的一个具体的一个案例，大家看我这我会这么设计啊，我们将数据的入队列叫做IQ。艾Q的处理需要两个步骤，第一个呢是尾指针，就那个尾部。往后移。当front等于RA的时候呢？我们认为它是空。OK。若为指针。为指针啊，这个小于指针，这个RA小于等于队列的最大下标，就是等于到这个最大下标解一时，则该数组存入的这个锐值就前面则无法接受了，就满了。

也就是说，当我们这个RA。注意听这句话。当这个real。等于这个单词写错了。但这个real，它等于到了mark。马克赛，注意听这句话啊，减一的时候我们就认为队列满。对吗？队列满了。队列嘛。那也就是说目前我这个数组模拟队列呢，其实它是一个。非环形状的就是用完就没有了，就是最多就搞五个，然后再用没有了。所以这个这个方法呢，比较简单，相对比较好理解，但是呢，它肯定不灵活。它不灵活，好，那现在呢，我们来把它代码实现一下啊，这是老师的一个思路，我们来代码这个实现，来队列模拟数组的这个代码实现，那么应用案例。

我们来说先完成一个非啊非环形的，环形的一个呃，队列。同样，我们是用数组来实现的。数组来实现的。好的，同学们，现在呢，我们把它先写到这里来，这是我们的第一个要说的东西。来给他一个标题三。好，具体来说呢，诶，这个标题三不是标题三啊呃，来一个这个不用标题三。来一个这个箭头就行了。好，然后呢，我的这个思路是这样子的，同学们看一下。这个大家要认真听啊，这听起来是有一点，就是说这这个还好，这个还好，还还还还不难。好，我们来组一下代码。戴。好，我的代码实现。我代码实现。这是代码实现，前面呢有一个思路分析。

在代码实现前面有个思路分析。思路分析，就是刚才那个图啊，刚才那个图。好，我的思路是这样子的啊，同学们再给大家再说清楚一下我的思路这样子的。待会儿呢，上来过后，我们就以这个为例。我以这个这个为例，上来过后大家不看那个幻灯片了，那个幻灯片呢，呃，说的有时候不是特别的准确，我的思路这样子的。我这儿先有两个指针。先让它指向这个负一。追听啊追听我的思路。这两个指针。我说第一下啊，就是现在用数组用使用数组，使用数组实现队列。队列。队列的这个思路。第一步。第一步，首先呢，我们要有一个结构体，就是我们本身有一个结构体，这个结构体啊，这个结构体呢，它实际上是用来里面包含了一个数组，这个结构体包含了一个数组，因为这个数组呢，它有两个指针是跟这个数组是是跟这个队列绑定的，所以说我先做一个这样的东西，先创建有一个结构体。

好，这样子吧，我们也不说结构体的事儿，我们直接这个，这个就是数组。这个就是一个数组。这东西一写出来，你感觉好像好像很很好理解，但仔细一想啊，你确认这个就是我们数组。好，这个OA呢，我这我这待会儿会设计两个两个这个它的字段啊，两个字段一个字段呢叫。一个字段叫front，就是前端。还有一个呢，就是real。他们初始化的时候呢，是等于负一。啊，就是。好，所以说第一步我们先创建一个数组。创建一个数组，这个数组呢，就是但这个这个呢，我们为了好管理呢，放在一个结构体里面的。

啊是是作为是作为作为这个队列的队列的一个字段。也就是在这个这个队列里面有一个A啊，它是它是实现这个队列的一个效果，然后第二个呢，我们有一个叫front。这个front呢，呃，是默认初始化为负一，初始化为负一。为负一，好，还有第三一个呢，就是这个RA，这个RA呢，呃，它是代表队列的最后表示，表示队列尾部。队列的尾部尾部，那么初始化也为负一。对，初始化也为负一，初始化为负一。好，呃，大体就这样子，然后呢，当加入一个数据时，我们现在要写写这个队列呢，做一个队列，它应该有这么几个基本的基本的方法完成它基本的操作。

完成就是要完成队队列的基本操作啊，完成队列的基本操作队列。队列的基本操作，哪些操作呢？我们要写这么几个，第一个是爱的。Q。就是添加一个数据进去，还有呢，我们要完成一个get q get q就是从这个数组里面取出数据，就是加入数据到队列。加入注意听加入数据到队列没问题，现在这个呢，是从队列里面取出数据。OK，这个是从队列。从队列取出数据。好，那么第三个呢，我们叫做显示历史的，就是显示一下这个队列啊，叫受受队列。受Q叫显示队列。好的。那最后呢，我们我们这个基本的思想就是这样子的，好，有了这个思路过后，我们来写代码了，那现在我们开始正式实现我们的代码啊。

大家先看一下我的思路。好，有了思路过后，我们走代码思路分析完事，好，这个呢，关于队列的一个前面的基本介绍，我们先说到这，包括我们的思路。