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

打开这个Vs code过后，我们新建一个文件夹叫cube。Q01，这是我的第一种啊，这是，这不是一个环形的，我们可以认认为叫single。单单一的或者单单单的一个一个一个队列，它用完就没有了，Single可好，那现在呢，我们写一个文件叫main点。命令go，好，同样我们打一个包包package主包好import肯定要输出一些东西，好，刚才我们讲过队列呢，因为这个队列它有几个数据，一个是数组本身，第二个还有前前后两个指针，或者叫前后两个标识，我们直接用结构体使用，使用一个结构体。结构体管理，管理什么呢？管理我们的对立。好，那么我们来写这个东西了啊，就是type。Type type什么呢？我就写个叫Q。Q，然后呢，它是一个结构体，里面呢，包含这么几个数据，第一个它的最大值。

比如说我们认为我们现在数组最大值为四个。为四个，第二个呢，它应该有一个真正的存放数数据的地方，叫二。这个就是数组，那么我们认为就是存十个数据，这个就是它的数组了。就是它是这个数组，它是被一个K那个包含起来的，因为你光有这个数组没有用，你光有这个数组，你没有操作它，就它就真的是个数组，只有当这个数组，当这个数组被。注入了或者加入了关联的方法，它才变成了一个队列，大家要理解啊，数组它是一种数，数组它是一种数据类型，等到我们给他了一些操作的时候，他就变成了一种结构。或者变就带算法了。那么这个时候呢，还有一个就是它的。Front。这个呢，我们表示它指向，这个呢也是个int，它表示指向，表示指向。

指向谁呢？指向数组的最前面，对对啊，指向队列啊，应该这样叫队列了。啊，这个因为这个数组呢，它是要模拟队列的。他是要模拟对应。啊，它是模拟一个对应模拟对立。好，那么它表示队列是什么呢？最前面要对对首首位首。队列首位啊，首部。好，还有一个呢，就是RA这个呢，就是表示指向这个队列的对位啊，表示指向对对尾表示指向队列的尾部。好了，有了这几个东西呢，我们现在来开始给他提供相应的方法，首先第一个我们先来给大家提供这样几个方法啊，第一个呢。我们先给他提供一个添加数据，当对立的思路啊，添加数据。

添加数据到队列最听奖。这个对呀，看起来很简单，其实你仔细想呢。反正就是有时候还是很很容易绕进去哈，那我写个方式。This。This，然后呢，Q。好，那现在我写个艾艾特Q，那你有艾特Q的话呢，肯定它这个是要给我一个值的，也就是说你往里面添加时候，你添加什么，不就添加些数据嘛，你添加一进去，添加二进去，添加三进去对不对，那得添加往里面添加数据，那添加数据的时候呢，显然你得给我传一个什么呀，直进来对不对，那么假设九个六。定制，那你添加的时候，你可不可能报错呢？完全有可能错误，打个比方，你往里面不停添加，要是队列满了怎么办，你加不进去了，所以呢，他这边是有可能有错误的，因此呢，我们写个L。因为你有可能有错误信息吗？我不知道。来，走一个，那你爱的Q的时候。

怎么加进去呢？刚才已经讲过了，队列的特点是总是从他的屁股后边往里面加，所以说呢，你现在得有一个方法。给它往里面扔进去。所以说第一步。先判断主题，先判断队列。队列是否已满？对，是否已满。郭老师要对满满，我怎么知道呢？对列没有满，怎么？其实刚才老师已经把条件写出来了，当然刚才老师讲到一句特别重要的话，什么叫做已满？说到作业，你搞一个算法的人，你就必须得研究什么叫对的隐瞒，那肯定就是你的这一个。你的这个RA，因为我现在不是环形的，就是你这个RA已经到了，你不停的往走走走走走走走走走走走到你走到这你肯定就满了吗？你不能再往前走，不是直全下去了吗？所以说这个地方呢，它肯定是通过这个RA来判断的，所以说废话不说，直接写，那就这样写了，就是如果我们这RA尔，它等于了最后这个元素马X size减一。

那么说明他已满，大家看，一旦我这么写，一旦我这么写，大家应该感觉到一种东西了，就说我这样一写，就因为这个RA其实是指向队列的最后，而且。刚好是指到最后那个元素的。有这个RA，它其实是指向对对列最后，而且包含最后元素。如果你没把这个分析出来，到时会出问题，因为下一个呢，最后那个它是不含那个里元素的，不然的话玩不玩不转，所以我这一讲你们到时间不清清楚会出问题啊，这里面有个重要啊，重要重要的东西。重要的东西东西，重要的一个提示就是，如果我这样写，就意味着我的算法是这样设计的，就是real这个。

下标，它就指向队列的最后，而且含最后那个元素就是瑞尔。因为后面那个刚好就相反了，是指向。是含是队列尾，队列尾部还有最后一位含队尾。含啊包含。喊，否则的话，你到时间听到后边就完全就蒙圈。含含最后这个元素，含最后这个元素。好，那么有了这个东西过后，他一旦有这个东西，那么就不废话了，你就直接给他来一个返回一个，就别别玩了，下面走不了。因为你加不进去，你就直接一个错误信息，注意听啊。所以让大家大脑要充分的动起来，Errors。点六，我就直接说队列嘛Q。不玩了。走，那这个就确定不要去论坛就不玩了，就q four满了，那如果没有满的话怎么办呢，各位朋友。

现在你要想你在做数据结构啊，所以你要想，诶这个对它满了怎么办呢？啊，那就这样子的，那你就先把这个RA往后挪一挪。佳佳。加加，你之所以可以加加，是因为你现在还没到这儿。因为你到这你你不可能再加价了，再加加不是调出去了吗？你加加就是将这个RA往后挪一下，后移一下能理解，那一旦后挪了过后，我就把数据放进去了，放到哪里去啊，放在这个里面去。二里面解决这个，二里面现在是，其实你想象第一个他现在还没有，所以说你现在做的工作是this。哦，写错了啊，刚才这个Z这个瑞尔实际上没例，我这整个都有问题啊，应该是Z点啊，这我都没带上啊，不好意思Z，因为我是用这个结构性来管理这个这个东西的，对不对，所以说这要带上这个好，这个地方也是this点明白，那this。

怎么做呢？点注意看啊，同学们走this.real。然后呢，等于我们加进来值加进去了。说应该提示一句话，恭喜你加入成功对吧，或者你不提示也可以啊，不提示也可以，那这个时候呢，呃，最后这个还是要打出去的，有没有成功可以通过这个error来判断成功了还是没有成功，好这个添加对列就成功了。大家看有没有问题。大家想一想啊，想一想今天这个我说了，今天听课肯定是大家肯定有人要晕的啊。我想还没有，还还没成，那个环形链表，环形链表那个东西更恐怖啊，好，那么这个就加进去了，加进去过后呢，我们现在有一个办法来证明我们到底有没有成功，说说显示一下，数一下显示队列。显示队列。好，我们先来看看显示队列，再从再写这个取队列的事，显示队列呢，咱们认识一下Q。

好的，那就受我们的队列。各位。那么你显示队列的时候，你应该怎么显示呢？各位朋友说，老师简单把这个数组直接输出来不就行了吗？不行啊。因为你将来有取啊。有可能取走了它就不能显示啊，所以在这地方呢，咱们要显示的时候应该怎么办，要找到这个它的对手。然后直接便利到对位，是这意思吧，好，所以说你这应该是找到找到对手。找到这个对的守卫，对对手。对手，然后然后便利道，然后便利道。对。便利到对比。OK，便利到对位，OK，那便利到对尾的话呢，这个东西其实就很简单了。

一句话的事儿来for，循环一下就可以了。So。For循环I。走向哪里，看这里啊，这地方问题来了，到底这个front含不含对手的问题。根据我的思路。根据我的思路，我这个是不含的啊，我不含，我不含原因是有的，因为你这个看你的设计，如果你含，你包含的话，你就想后面的代码实现起来是有比较困难的，所以说我要先说一句特别重要的话啊，就是这个front在我这front它是指向这个对手，但是不含。不含对手的那个元素，其实它相当于说在队列的最前面，但是没有包含第一那个元素啊，所以说我应该这样写的，就是Z是点。Front。加一。但有有些同学老师假设，我就想希望这个对手前面含了这个比较麻烦，大家想一想，因为你第一个元素刚刚是空的。

你空的话，如果它本身含义化说不过去，从道理上很难讲通，但也可以也可以实现啊，就是你大不了前面做一个判断。也行。好，我我现在就假定啊，我现在的设计思路是我们设计的是。好，我把这个思路写到这儿。我在这我的思路是这个对手它是不含这个元素的，这是this啊。这点front front是对手，不含不包含不好，不，不包含这个队对手。的元素。对手的元素啊，OK，那这样样子的话呢，就我就这样变异了，I小于等于。到我们的屁股后边，they.there。Re，好，I加加。阿姨，想起喜欢了。那写完过后呢，很简单，你把它给我打出来。

用格式化的形式打出来，大家看的更清楚一点，比如说我就叫。好的各位同学二然后呢2Y轴，然后呢百分D啊，百分D等于具体的值，打一勾后呢，来个吸更替。哦，OK，好，接下现在呢，咱们第一个它的下标就应该等于I，就应该等于I没问题，它的这个值就应该是Z，这写错了ay。它就应该是Z里边的这个数组。对。好，大家看能不能看懂啊。因为你这个下标嘛，下标是用I来进行这个编辑的变化的嘛，好打完一个就完事了，打完这个过后呢，他不停的打A编辑往里面就成功了，好这个呢，我们可以打印出一句话，就是队列当前的情况是。对，列当前的情况是这样子，好，同学们，这个就有了，来，现在我们可以玩一把了，来写个东西来测一下。

编写一个主函数。主函数测试一下两个函数对不对，测试一把非常简单，放。走，玩一下。好了，走起来啊，走起来，大家看这个就是相当于说我们再去往里面加，那这个地方我们怎么玩呢？非常简单，我们看看它这个先建一个Q。单位有问题是吧，待待会再调哪地方有问题。结构体有对结构体有完美初始化是吧。结构体我没说错，Type q。帅。啊，这写错了啊，这写错了非常好啊，大家同学们看到这是这个应该是第一个字段没有，我这初始化再给他一个四好，先创建一个队列。先创建。

创建一个队列啊，注意听讲一直在说队列，队列现在中于你们再看队列长什么，就长成这个样子啊，长成这个德行啊好，然后呢，咱们用个Q小写的，等于来负一个值吧。好，那就直接给他一个地址I的符号。Cube。绷起来。第一个值mark size，我们假设呢是，呃，我们根据我们这个情况啊，目前呢，老师这画的呢，就以这个为例吧，有四个，那就应该写五对不对，我应该写五，因为我目前这个地方它最多能存放五个元素嘛，所以说我应该给他一个负值为五，我就刚好给它对应上，让大家我也好讲课，嗯，第二个呢，它的宿主这个不用再去管它了，因为宿主大家都知道它是直类型。你创建的时候，它就自动全部给你初始化了，那我最终应该写直接写个五。好直接写个这样就更好啊，写个五，那这样子完了过后呢，我们下面把这个front。

初始化为负一，因为它刚开始一个元素都没有。对，它的尾部，尾部也为负一，因为它没有元素，负一写完了。好对对，写完了，我们往里面添加点数据，添加数据好添加数据呢，我写一个添加东西，我写一个简单提示啊，这是来走一个走一个菜单。这个菜单我写一次，后面我就粘贴复制了啊，简单写一下。飘然。PT评论好，快速走一下，说选择菜单第一个输入I，就这样输I啊，第一个输入I表示添加数据。输入ID。A表示表示添加数据到队列，添加数据到队列。没问题，那这个写完过后呢，我们再来第二个，比如说get，第二个get表示获取，Get表示表示从数据，呃，从数据中获取数据，表示从数据，从队列中获取数据。

获取数据就是出出队列，还有一个三呢，我们表示显示叫受，如果他输一个受，哎，这个人输了一个受呢，我们就显示这个，显示这个队，表示显示队列。OK表示形式对立。显示对没问题，好，下面呢，最后一个退出，如果你不想玩了呢，就退出是输入这个退出指令。好，现在呢，我做一个K进行一个判断啊，这后面还有一些东西要用到K，比如说我有一个k string，然后呢，这个。VR啊，初始化就这样子的VR。好，我来输出接收他一下啊，就是看。SCN，呃，L看，然后呢，我接收。这个就是它输入的这个K。输入这个K，那么我做一个小小的判断，Switch。

Switch swi iwir k，那么我就判断一下它是什么，如果呢，它是I的，好的，我们就认为它是添加数据，添加数据的话，你要提示它你添加什么东西，对，你就提示他一句话，请输入你要添加数。PT。好，请输入一个数，输入你要你要入队列的，入队列的数据。数字啊数。好的，这个呢，对我们来说很简单，我们上面再定义一个东西来VR value啊，Int，然后呢把它收一下。叫fmt点看。是看，诶是看。看L，然后我们接收它一个数，啊，V到了一个F。好输进去过后呢，我们直接调这个队列给它入入一下Q。Q，怎么入，怎么放到队列里面去呢？有个I的，刚才我们写的I的这个方法加进去，加到队列里面去，好的加到队列面去，扔进去了啊，写完了。

啊，这个地方通一个判断，看他到底有没有成功，通过error来判断搜一下。好，它这地方呢，如果成功了，它会返回一个空的错误，如果没有没有成功，会返回这个Q满这个错误信息，我们也把它打印出来。如果L不等于near好，我们就说入库成功。打一化PT就说加入队列成功。加入队列，OK。否则我们把这个错误信息打出来就可以了，错误信息是什么就是什么，我就直接输出。For mind。t.print直接把它所有信息从error里面取出来。Is，好，完事。好，那么这是添加，呃，显示我们来做一下get get现在没有做处理，不去管它。Get到，因为我还没写，就是出队列还没写啊，然后这地方呢，我们写一句话就可以了，PT。

好，就写一句话，就说盖子好。其他的另外一个手。后面这个代码就可以连接复制，直接用队列来显示啊，就是就是Q。点刚才我们写的这个事物方法。数我们的队列，好，写完了。最后呢，如果它是呃一个指令叫exit，那么我们就退出这个指令，退出这个系统EX0。好，那这个代码呢，咱们就到此OK。OK。好，整个循环就是这样子的啊啊看看还有什么需要注意的，先编一下保一下啊，看看代码有没有问题。好，Format。包没有瘾是吧？报赢了，OS帮没有，OS帮没有赢。Or帮没有ers？

好，还有哪地方有错误，看一下，呃，还有这有错误。这边有一个冒号没有写OK。好，还有哪地方有错误，我们看看。好的。啊，好像这没有提示错误信息，跑下先说跑线先说啊CD点点CD到刚才我们写的Q。我们建建了一个CAD到single。Single q DR go run一下，Me，跑。好，我们来往里面增加一点东西，爱走添加你要入的数。比如说一。报错了，在哪里报错了，我们看到第67行报了一个错误，也是应该是类似于这个空指针，好67行，67行为什么会报错，我们看看67行，它是这个地方。67行。哦，它等于现在是这样子，打错位置了，如果不等于空，这个我刚好写反，我刚好写反啊同学们，因为它这个不等于空，代表有错误，如果等于空呢，代表成功，对刚好写反，好这个是代码，刚才是写快了。

跑起来再来。好爱。好，输一个一。加入队列，OK，那么我们来看一下现在队列是个什么情况。当前队列情况是这个，那是这个地方应该给他来个换行啊，打完了过应该换个行才好，显示的时候没有换行，最后这个就看起来很难看了。好，再重新来一下。这样不然看不清楚，对看不清楚啊好来走艾特一下，第一个数加入队列成功受一个成功，第一个元素有了再来爱的第二个元素，第二个元素二。然后呢，瘦一下又成功，我就直接加了啊，看什么时候他加满。三。

爱的。四二的五好，此时此刻，我们现在队列里面有12345，如果我在家，会提示一个信息占满，果然是。那就是队列满，队列满的话呢，现在就加不进去了，就也也OK，现在有了这个队列加速购物呢，我们现在马上写一个取队列，就把这个队列一取就是一个是入入队列，一个是出队列，出队列呢，怎么做呢？好这里面呢。要来写一下这个出对点。就是从数据。从队列中，从队列中，队列中取出数据。那么取出数据的思路呢，跟前面非常的相似，非常相似，只是要改一下东西了啊，放。this.this心cube。QUE。UEUE。

Q。好，然后呢，我们叫做get q。那么get q呢？好，这地方应该也有可能有错误，所以说我也把这个错误有可能打出来，因为什么时候有错误呢？假设你在取的时候不小心，这个队列已经空了，你还在取对吧，那就不行，好，同样先判断。先。判断队列是否为空。是否为空？那么我怎么知道它为空了还是没有为空呢？一句话的事就是当什么情况下是为空的？我们来判断一下呢。对。嗯，不能够说Z有些同学老师说方等于零，是不是就等于空这个说法，这个说法不对，因为你在有时候你在不停的走的时候再取，所以说最好的情况应该是front追到了屁股后边，就是front跟它相等了。你想想是不是道理就是front走走走走走走，诶走到这个跟RA一模一样了，它两相等，那说明他们就已经为空了，因为你每取一次你就走一次嘛，所以这地方呢，要这样判断z.RA。

如果等于了this.front在这种情况下，我们就认为队列已经空了，因为取走了，因为我，我的一直在追你，我已经追到你了。啊，这个对空。对，空了。好，这个写完我会给你布置点任务做啊。好，那么这个也很简单，直接一个东西就行了，怎么写呢，叫QNPD。啊，Return什么呢？就是error是点六一个Q。什么呢？NPD空了不玩了，那如果说没有空怎么办呢？同学们，哎，没有空的话取出来呗。但是要注意啊，取的时候先要把这个往后面移一下再取。

注意听啊，因为我们刚才讲过了，From它是指向这个对手的前面一个，它不含对手。所以说这个呢，This front要后移一下。啊，要后移就是加加。加加完了过后呢，我们把这个值返回去就可以了，Y等于。好，这样子的话，我们把这个值可以直接开始返回去，返回两个东西，一个是A，一个是值。好，这样子就OK啊，大家看，那就这样写了，Value等于什么呢？Value等于你从这个队列里面取出来东西，就是this。阿瑞。走。什么东西呢？就是this.front。好，写完了，最后就把这个return回去，Return value。Whether，因为这个error啊，是因为你这返回一个，返回一个是不行的，你要吗？两个都不写，只要你写一个的话，你就两个都要写上。

啊，两个都要写上，上面这个也是一样的，你让你这一报错，他说他说33行有错误，大家看一下。他为什么，他说你不够。不够的原因是因为你只返回一个L，你这个value value6值没有改，你就写个负一就行，因为到时候我们先判断这个为为不为为为不为空，我们再去取这个值啊，如果它error不为空，那说明肯定没有拿到值，就不去取了，如果它为空，我们再去取值就完事了。但这个代码一定要看懂，好，现在我们来谈一个谈一个数出来。谈一个啊，现在你要你要取东西了，好的一句话的事儿。直接这样写。写什么呢？我们用一个值。和一个value机收下。I接收一下，等于你的这个Q。UEUE第二。Get。就。UEUE。好，写完了过后呢，我们来做一个这样的东西，把它写完了啊，写完过后，然后呢，我们来判断一下，如果。

如果这个L它不等于零，说明这个有错误，所以说把错误信息打出来可能是占满了，或者什么原因啊，不知道l.eS。好OK，那L呢，就说明它是成功的了，成功的话呢，我们把这个信息打出来，你到底做了多少东西啊，打印出多少东西，我们输出来，就是你从队列取出来数是什么。从队列，从队列中取出了，取出了一个数，这个数等于多少呢？好，把它打印出来，来，好，代码写完了。好，我们来看看现在能不能玩一把啊。好看，玩一把先输出一个退出玩一把走开始了第一个。大家现在能说有有点感受了，首先受一下，目前是个空的，爱的走加一个队列进去了，在爱的加一个二，搜一下来看，现在我有两个数了啊，一和二，现在我马上就取东西了，大家看我要取了啊。

我应该取出谁呢？显然我应该先取出一，因为一先是对手，所以说我get一下，他说从队列中取出来一个数是一，然后我再搜一下大家看。哎，果然对的，现在对手已经变成一了。紧接着我现在还能不能往里面加呢，我能加，我再加一个三。好，再加一个三，大家看对手是一和二，现在我能不能再取了，可以啊，现在我在里面再加一个。再乘四，四，好，大家可以看到现在我有三个数，234，现在我取一个，我现在取的应该是二。Get一个，取出来了再get。取到三，再数一下，现在队列里面有几个呢？只有一个就是二三，果然是只有一个，二三完全正确，现在我在里面再加一个。

五。加进去了吗？还是能加进去，再数一下，相对队列面有两个元素四和五，正确，现在我能取。我先问大家，我再加行不行，说老师你看一点，你不是大学有五个吗？你现在只有两个，你看我能加进去吗？现在应该加不进去了。队列满了，所以有些同学老师这个很乖，你队列明明有五个元素，你只能放两个，因为我们这个是单向的，就倒用完就完了，用完就完了，所以说这个时候你对内已经满了，那对点满的话，你是取不出来了，但是呃呃对点加不去取，还能取，比如说你你盖的一个。盖的时候呢，还能取出一个四，现在队列里面只有一个了，再盖还能取出来。再get没有了。队列空。往里面加也加不进去，队列是空加也加不进去，就是队内满，好奇怪的想法，取的时候他说队内空，加的时候他说队内满。

这是一种很很容易让人崩溃的一种结果，哎，取，他说对，取的时候他说队列空。因为我们是单向的。现在我要请大家思考了啊。同学们。现在呢？第一个单向的队列我们已经实现了。现在我想请同学们想一个问题啊。我们现在虽然已经实现了，实现了这个所谓的一个队列结构，但是它的问题是比较严重的。什么问题呢？大家想一想，就是你没有办法去复用我们这个队列的就是数字空间，你因为你到最后的时候，其实是这样一个情况，同学们，最后这个地方是这样子的，你原先啊加了加了最最最后变成这样子的，相当于说数，相当于是这种感觉啊，最后我们。这面数组其实什么都没有了，只是你的对手，对手。到这儿，一的对尾也在这儿。

因为你现在是这样一个情况，他一判断两个相等，所以说对吗？但是其实你还是可以前面这还可以用的。那么，我想请同学们思考。你能解决这个问题吗？就说你能不能想办法让他在加的时候会前面又加来，就说你那个对位，你对位可以往后走啊，你你你到这儿你不是出去了，出去过后你到这来吗。这就算法，你怎么把它整过去啊，其实呢，提示大家一点去模就行。但是我我告诉大家，如果这个东西同学们能够在不做任何。老师或者是不查任何资料，老师也不提起的基础上，你能够把这个把它环形给他整出来，还是有，还是要，还是要动动脑筋的。好，我先把这个东西说出来啊，然后呢，我把这个代码先发给大家消化一下，好，然后呢，我们再接着说那个问题，好，我先把这个代码给各位朋友整理一下啊，思路咱就已经说完了，这个一个最基本的一个队列咱就说完了，来整理到笔记里面去，代码具体实现呢，我先把它放在咱们的笔记里边去。

好，然后我把问题给大家剥离出来，就说这它的问题还是比较严重的啊，比较严重的来这个呢，我说明一下对上面代码的一个小结。好，说明对小结和说明，这是个基本功啊，同学们，这个呢，大家呃要。这个队列这个通道后面呢，这个我会拿时间来考察大家。还是那天早上呢，我会要求大家写两到三个数据结构，我会随机的抽，比如说我说来，同学们把笔拿出来写个队列。对吧，我可能说同学们写一个这个环形列表对不对？好，那么我们总结第一个原因是上面代码已经可以完成了，上面的。

上面的代码。上面的代码实现了实现了一个实现了基本的基本的队列结构，队列结构。结果。结构，但是但是它没有有效的利用数据数组的这个空间，但是没有没有有效的有效的利用，利用什么呢。来利用这个数组数组的空间说第二个问题呢，就要大家思考了，请思考如何如何做成一个环形的一个类理如，请思考思考。思考如何啊，如何使用这个数组数组完实现实现一个环形的环形的对立。所以环形的队列就是说，当你这个地方已经满了过后，你这个你这个可以往后面跑。然后呢，再找的时候找，再加往后找，再加往后找，在便利的时候，仍然能够完成它的一个完整的便利。

好，这是呢，给同学们留的一个作业，好，同学们，我们休息十分钟啊，休息十分钟。