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

同学们，我们来看一下怎么实现它这个代码，那打开我们v code，然后在这里呢，我新建一个文件夹，不要跟它写在一起了，叫环形，叫circle circle什么呢。Q。QEQE，好，我现在呢来写一个文件叫main点构。没点够啊，我们package一下主包。这个还是很多这个面试官喜欢去考的。啊，那么我们来看看怎么实现它，首先呢，还是用一个结构体，还是用一个结构体来管理，使用一个结构体，一个结构体管理，管理什么呢？管理我们这个环形队列。那当然，人家是用速度来模拟的啊，所以说我这写个type，那叫circle。对，Circle q。十个Q，然后呢，它是一个。啊，里面呢，有个数组，它有个最大值，我们把它算出来，假设我现在变成四个，啊，变成当时我们给他一个四。

呃，五个有时候不好测试，太多了，有时候然后呢，还有一个就是它里面的真正的一个数组，数组呢叫二这个没有变化，还是一个INT4。好，这个没有没有问题，这个就是我们真正的一个数据。这是一个数组啊，同学们没问题。这是一个数组。然后呢，我们接着再往下面再写一个东西，就是什么呢？它的尾部和头部，尾部和头部前面我们我们用的是front和这个real，对我们就是这个，但是呢，也也有些这个程序员呢，他喜欢用这样写，用hi和T来写也是可以的。啊，所以大家都看一下，有有些人呢，喜欢用这个head和ta头嘛尾更形象一点啊，就是头指向。指向这个队列的头。对手。对手。当然下面这个是指向这个，对对手啊，写错了对手。

那下面这个呢，是指向队列的对位。指向对尾。好的，同学们。有了这两个勾呢，我们就开始来做这个一个一一个代码方式，主函数，主函数里面的代码呢，有些可以用，所以说我先暂时不写，因为前面那个提示信息，我就可以直接从这粘贴拷贝过来了啊，像这些一系列这些信息我可以拿来用一下啊，这个我可以用。这个我就复制一下。哎，我复制一下。OK。这个没问题，这个代码我就不去重新写了。对，只是里面的调用的方法呢，会发生一点变化，比如这一方会发生变化，我先把它注销。对，怎么输入的这个地方呢，可能取的时候也会有些变化。好啊，这个呢，我们可以保留啊，可以保留名字，到时间可以领取，好，现在呢，这个价值有了，我们接着来往下面写，首先呢，让他给我提供一个呃，添加入队列的一个方法，入队列。

入对立。好入队列呢，我们还是用那个I的啊，用这个I的Q这个方法来写的Q。爱的Q。好，然后呢，初队列呢，我们仍然用get q。Get q啊，但是我要说一下啊，有些程序员呢，把这个I的呢，也直接叫push，也可以就推进去站，我们可以叫push队列也可以叫push也是可以的啊盖着。Q呢，也有些人直接叫做pop，就弹一个从对立面弹一个出来，大家看到我们在前面学的这个，呃，学这个历史的时候呢，它也是一种用法也可以啊，两个方法都行啊，两个方法都我们都换着用一下吧，好吧，好来写一下function。那我开始写了啊，This。然后呢，Circle q就是环形队列对不对，环形队列呢，我就直接写这个方法了，我就叫push吧。破线的时候呢，仍然是给我加一个加一个这个数据去，所以说呢，到时你给我一个value，因此我到时如果成功了还是失败了，我都有一个，呃，有一个具体的一个信息给你返回来。

对，返回来or好，这个呢可以写到这里。好，写到这里来。然后呢，还有一个泡泡，泡泡呢就是出战，我也把它写过来。啊，泡泡就是出队列啊，也有叫出队列泡泡。Pop也可以。啊，就是从这弹一个数出来弹数弹一个数呢，我们最好把这个值接收一下啊，有个L有个值。有个值，然后呢，诶，有个值是一个特类型的错误，还是个L。ER写完了。那现在呢，我们还迫切需要两个，还需要几个方法，特别重要的方法啊，第一个是什么判断它什么时候为空，什么时候这个满了，这两个方法是特别有用的，好判断，判断这个队列，环形队列。

环形队列为空。那那我怎么知道它为空呢？刚才我们已经分析出来了，特别重要的两个条件啊，一个是这个是代表满了。这个是代表为空。好，这两个呢，我们都来把它做一下，来开始写。放。This share。Circle啊，我就复制一份。Circle，那我们现在看它是不是是不是满的啊，一是负负。好，做一个判断啊，直接written return return，哪一个条件呢？就是它的这一个，下一个就是它要加一个，一再模上马克S是不是等于前面，那就这样写的Z是点。它的这一个什么呢？它的这个T就尾部加了一个一。括起来。括起来。这个刚才我们做了一个分析，加起来过后再模上这个Z点，它的最大的大小。

Mark says。好，如果这两个相等啊，这摸向这个等于了z.hi的就它磨完了过后呢，诶等于了这个头部，那说明他已经追上了，好但是他中间留了一个啊，他他是先判断一下加一个一再去判断一下到底对不对，好好这样子呢，就就可以判断它到底是不是满了。就直接返回，还有一个呢，就是判断环形链表对到底违背空。判断是否为空。判断环形，环形队列是否满了。啊，这个是满，这个是满啊，刚才写错了，满这个是判断为不为空，对啊，那么判断为空和满呢，这个地方区别就在这里。空空就是我，不停的取，我终于把你追上了。Em。好，这个时候怎么写呢？就是这样的，This，这个tell如果等于了this had，它们相等的。

那就说明我已经追上你了啊，就不停的走走走走，最后我给你相同了对吧，好，这个地方呢，我们返回一个布尔值。我们返回一个布尔。好，最后我们还有一个特别重要的函数，就是能够取出这个环形队列有多少个元素。取出环形队列，队列有多少个？多少个啊？多少个元素？这一点呢，也很重要，我写一下bank this。好，前面一样的道理。我写个size，直接写个size啊，Size。Size，那么返回呢是一个。对，怎么返回它的大小呢？很简单，就是this的这个T加上this点它的最大，因为我在每次都在不停的取模嘛，对吧，Max。

Size，如果这个加起来再减掉一个this.had。看它们之间的差值有多大。啊，差值呢，还要取下模啊，待会我们可以去验证这种这种写法啊，验证这种写法，然后取模上它的最大值。这个大家可能看起来有点吃力了啊，有点吃力说要是为什么这样算呢？因为大家想嘛，因为你是个环形列表，大家都不停的在后面，这个其他的害人呢，不停在涨的加加加加的时候加到要快出去的时候，加了一个max size，然后他就回去了，所以说会造成这个T在某个情况下，它的自然值它是小于这个headde的，因为你还得在后面去了，但是太阳能找绕过来一圈，所以说要把它加上，再减掉，再磨上。大家待会去推，推断一下这个算法对不对，这个地方是很关键的，同学们，这是一个关键点。

这是一个关键点。一个关键的一个算法。关键的算法，如果这个地方没有没有突破的话，同学们啊，那这个环形链，环形队列就很难把它做出来，很难把它做出来，好这个有了过程呢，一个push一个pop嘛，完事了，很简单push，那首先你得判断现在push就是加。Push就是加数据，就是入队列，入队入这个队列。入加入的啊，入队列，这个泡泡呢，就是出队列。泡泡就是初队列，注意注意，听啊出队列。那出队列和队列肯定我们要首先第一个，你既然入队列，我先判断你是不是满了对吧，所以说我第一句话if。this.is到底它有没有满呢？负哎，你满了没有啊？你满了我就我就不能再加了，所以我就直接来个error给他，给他直接给他返回，或者是做一个做一个动作是吧，就是这样子。

Return一个什么呢？As。As点661个就说叫做队列已满。那么队列就Q负满了。不玩了，不玩了，那如果说他没有满，诶没有满的话太好了，那没有满的话，我就在它的这个尾部把这个数加进去就行了。那么它的尾部是什么情况呢？它的尾部啊，它的尾部是这样子的啊，它是先加一个，先把它放进去，然后再往后面退。也就是说。也也就是说它这个尾部，它本身刚开始的时候就就的的确确是指向一个队列的尾部，它包含这个队列尾部啊，所以说我们现在要这样去做。对的，我不来了，过后就是先是这样子啊Z点。

这是它的数组元素嘛，大家看我们刚开始初始化的时候，这两个都在零。因此。呃，这个T呢，现在应该是还没有直的，所以说直接这样放进去。Tell。等于。就是在它的尾部把这个纸放进去。放进去就说相当于把值。把直给这个尾部。尾部，把这个值给尾部给完，这个尾部过后呢，我这个Z是。往后面挪一下。就是这个this点。佳佳，好，这个我们来问大家一个问题啊，大家思考一下，如果我想这样写的话，我想这样写的话。那么大家想一想，T它到底包没有包含这个队列最后一个元素，它就说在它在它运行的那一瞬间，这个T到底有没有包含它的最后的一个元素？

应该是没有的，应该是没有的，因为我待会初始化的时候呢，这两个都是零。我初始化这个是零，这个也是零，也就是说大家要分析出来，从我目前这个算法来看，这个T。这个T它是在。这个队列的最后，最后，但是它不含，它没有包含这个队列最后的一个元素。好，大家看看能不能理解啊，就这样子的话，我们分析出来，分析出来一个重要点就是分析到分析出。就是分析出这个尾部啊，就是这个。This tell this.t它并没有并在在这个队列尾部，在队列尾部尾部，但是，但是它不含，不含最后这个。不，尾部的最后那个不含有，不包含不包含这个最后那个元素，最后的那个元素。它相当于是在最后那个元素后面再移了一位。

可能有同学在想，为什么要移位呢？说老师你原先那个你前面做的那个好像就是那个尾部，就是刚好包含之后，你现在为什么不包含了呢？告诉大家啊，如果包含的话，这个就不好做，他是这样子的，大家想。我是这样子的啊，大家想。呃，他是这样子，就说我走。我走，再讲，我再讲。加到这儿的时候。加到加到这加到这个地方的时候啊，因为他其实真正的数据还在这，它真正的数据在前面这一个。好，等到我再加一个的时候，我再加一个时候，好，我到这来了，其实这个时候这个太指向这个地方，这个地方还没有真正的往里面放东西。就是这个这个地方已经是对尾了，但是这个地方就是现在看到这个第四个这个空间是没有放东西的。因为我要把这个地方留下来。当做一个标志位。

然后呢，我我再去判断哦，你现在是不是，如果我判断一下，我加一是不是已经等于一了，如果等于的话，我说明已经满了，这个最后这个要留下来。为什么要留下来呢？原因是这样子的，如果你不留下来。这个对手因为在整个这个环境里面取的时候，他的对对他的队列，他的手不会发生变化，它就是它的对对手的话也会变化，如果你中间没有一个标志位，很难处理。但是有些同学问说为什么要标注位，我跟大家讲啊，这个只是在写的过程中，你你会在写，你会发现写了好久没有这个东西，你没没办法没法弄。所以说环形链表用数组模拟环形链表，它实际的容量是这个数组的大小减一。如果你们可以去做一下，如果说你从你最后这个不留一个这个叫做这个叫做约定，或者叫做标志。这个环形列表很难实现。

就很难实现。但但是为什么要这样子做呢？这个就就是说在做的过程中，实在没办法就想来想去，没办法只能做一个约定。但如果说你有一个办法说老师我连最后这个都能用上，那你牛。啊，反正我是实现不了。那说明你真的很牛。啊，那你那你这样去试一下就再说吧，你实现了再说啊，你实现了再说。嗯。那这个判断一下，就反正时间就行啊，时间就行，可能更从逻辑上看起来可能更复杂一点吧，我估计会多一点判断，因为你这个地方这个不留这个东西的话，不知道会出什么问题，你可以试一下写出来，写出来过给大家参考一下，我这就采用了一个相对容易理解的，我就没有就留了，这个倒影响不是很大，为什么呢？比如说你这个数组，你这个数组有50个，50个元素。

有一个没有用，应该说还是能够接受的，还是能够接受的，并不是说预留了很多啊好这个呢，我就用的采用的采用的是这种方式，就预留一个，最后做一个约定，好，那现在呢，这个做完了过后呢，我们就接着往下看啊，那就是大家可以分析出来不含这个。好，这做完了过后。一个错误。那return呢，这个地方，我们这个地方那就没办法这样做了，这样肯定语法会，我看看会不会报错啊，没有应该是可以的啊，应该是push进去。好，这个push完了过后我们再看初队列，出队列快速写一下啊，如果。Z点它如果是已经满，已经空了，你就不能再出了NPT。如果它已经是个空的，那你就没有办法再出东西了，所以说呢，咱们也返回一个错误，叫做队列空N。NBD就空了，那空的时候你这样写呢，因为他要求两个范围值，你这就没办法了，所以说你就随便给他一个值吧，默认值吧，零。

当然你最后判断到底有没有弹出来呢，你可以先判断这个A到到底是不是为一个逆对吧，好，现在为空，那为空我们现在要要取嘛，现在不为空就取东西取出，那取的时候咱们怎么取呢。啊，取的时候怎么取呢？非常简单哈，因为你上面已经判断它是不是为空了。所以说你直接从那个hide里面弹一个出来就行，然后把hide在后后面移一下。好好，现在就取出来了啊，Value。Value等于认识点。Z，四点什么呢？就是我们的这个，呃，就是它的这个，呃。里面有一个this.had。那这样子从如果我这样写的话，大家应该知道对手它是指向队列的前面第一个，而且还包含这个元素，对吧。

啊，它是包含的啊，这说明这个害呢，它是这个地方对手把这个分析出来，害是指向指向对手的。对手，并且并且。并且包含含这个元素，含这个元素。含这个元素。含第一个元素，含对手元素，含对手元素。对手的元素好了，那这样把它扔进去过后，取出来过后呢，这个value取出来了，取出来过后这个Z就往后面移动一下了，因为你已经弹出来了嘛，说他应该往后面对手就发生变化，往后面弹了一下，好hi就加加。好，佳佳，然后return。啊，Return，好，看看这地方有什么问题，Empty this，把它取出来交给他，交给它过后把this had加加，然后return。

好保存一下。写完了，写完写完过后，我们看看这边有什么问题啊，它有好多哦，这是指针哈。他说这个NPDNPT没有没有定义啊，Is is is is啊，Is npd，好把代表先编一下。好，Errors没有引包，应该是没有引包，把它引一下ers再保存一下。好，这边还有一个错误，他说hands这个，那么我我定的是把这个单词写错了A。好保存一下。好，还有哪地方错误，还有一个错误啊，还有一个错误，最后一个错误调一下，最后错误是OS me OS谬。好OS没有啊。好OS面过后呢，现在我们这个有push，就是入队列有出队列，现在我们还差一个非常重要的方法，就是显示它。显示的时候怎么显示呢？就说显示最队列哦，显示队列。

显示这个环形队列有点有点意思了，大家动脑筋了。显示队列能不能就是说把这个同学会可能会想显示队列多简单呀，你不就是从这个。你你不是有一个对手吗？有个对尾吗？那我就从对手开始遍利，遍利到这儿不就完了吗？不对不对，因为因为你现在已经变成环形的了。环形的话，就有可能出现这个情况，什么情况呢？比如说我这个对尾走走走走走好，你这取了一个到这儿来了，取了一个到这来，突然因为种种原因，我往前面加了一个，那也就是说这个对对为它的这个下标有可能是小于。对手的。所以说你现在不能那样子说，我就给他一个方，然后便利，那便利的根本就不对了，跑不起来，没准一直接一起就跑了。说这地方呢，不能再用那种方式了啊，要显示队列，队列我们要写一个新的方法，这个思路大家想想怎么做啊，新。

然后呢，我说我的思路吧，我说我的思路啊，那就受历史的讲历史的这个队列。Q。QUEUE啊，然后呢。那张怎么显示呢？首先你要看到它先不违背空，如果为空的话，就不要显示了，就是空对点就不显示了，就懒得走了啊，那现在首先我们看到这个大小我们是有的。哎，如果我们通过大小来做不就完了，首先啊。刚才分析的已经不能不能说对尾到对尾直接看了啊啊首先不能这样做，所以说我们先取出，取出当前，取出当前队列有多少个多少个元素能理解吧，那就是size吗？Size呢，我就认点size就取出来了。那现在只有两种可能性，一种S，那就直接等于零，它等于零的话，那就空的，就提示它说当前队列是个空队列，无法显示。

是队列为空，队列为空，完事。啊对列现在是为空的，那如果不为空呢，我们就负循环，For循环，那for循环咱们怎么负循环呢？就是从它的应该是这样子做啊，应该是找到他的对手。然后呢，对手加加加加的时候呢，每加一次要加一个一再取一下那个马赛，这样才能找到它的位置。所以说我是要写的啊，大家看我的思路。等于零，大家看这地方我就不直接说了啊，小于S。A加加，看清楚了啊A加加。然后呢，我就把这个队列打出来。我就格式化一下啊，格式化我我我取出来了。二瑞把它的下标打出来，等于它的一个值，然后呢，我这地方也不去换行了，直接斜杠T，斜杠T完了过后呢，这个这个D肯定就是它下标，这个没什么可说的，下标我们不要从零开始。

下标就先暂时不从，我看看下边哦，下边还是得从他的这个对对头开始走啊，还是得这个对头开始走，This第。害。害的。OK，那么呃，他一共走多少次呢？哎，他他就说他有一个，哦，对对手这样子做啊，咱们这样说。他上来过后有一个temp，先让他指向这个，指到这个对对头去，他知道怎么走，然后呢，走七次。走七次，走七次的话呢，相当于说一共有七次啊七次零。好，我这样写，我这样写比较好一点，你思路更清晰一点，这样子啊，大家看我的这个思路，大家看你能不能理解，我来一个辅助，我做一个辅助的变量。

我设计设计一个辅助变量。辅助变量。辅助的啊辅助。辅助的这个变量让它指向哪里呢？让它指向指向这个head，这个没问题，这个我头我不去动它，头我不去动它，我做一个辅助变量temp步。Temp，临时的一个头吧，临时头它等于什么呢？Had？好，这个时候我就让他跑七次，跑七次的话我这样做。首先这个hide还是他。没问题，就是这个这个I就是用来控制777次的，就打多少次，然后把它写出来，然后取这个值呢，就是Z点，大家看能不能理解。里面呢，把这个head放进去，就是他的下标。就代表它是第几个，它的值是多少，打一次就就做样子，然后呢，把这个temp做一个处理temp had。等于什么呢？按理说它应该加加。

但是如果仅仅是加加就要出问题，因为你现在是环形的，所以说你要这么做。应该等于这这个啊temp hide加一个一再模上最大值，这样才可能它是到最后再再又跑回来了。啊，这个呢，大家看怎么理解。好，如果你不这样处处理的话比较麻烦啊，Mark size。好，马赛，等到它循环了七次，它就出来了，最后我们打出一个换行。然后呢，我们这边给大家提示一个信息，就是说就说下面的这个打一个消消息，就说环形队列情况如下。环形队列情况如下。对的如下。怎么如下法呢？来跑一个代码就写完了。好，这个错误，This啊，Max size啊，这少了一个曲模。少了一个曲目。好，52方，我们这儿还有一个动作啊，少了个this this head。

This，害的。好，再来看一下。好，再看看有没有什么问题啊。好，我们先试一下吧，现在我们整个玩一把，那这个时候它这个调用入往里面入队列呢，思路跟这个很像，所以说把方法换一下就可以了，他这边还是我们把这个初始化一下。我们初始化一个队列。初始化，一个环形队列初始化。初始化啊，一个环形的对立。那么环形作业咱们怎么初始化呢？简单一点啊，就这样写。呃，Circle c啊，就叫K嘛，懒得写了啊，大家知道是个环形队列就可以了，然后呢，爱的符号，爱的符呢，我们环形队列的它的结构体叫这个名字。好，看清楚了啊。看清楚。啊，但是这个地方能不能成功，我们还得拭目以待。

好，然后里面呢，有几个值，先初始化一下，第一个就是它的大小，我们就写就写五四写写写十写五个吧，因为五个实际上他也才能用四个。好好写五个好，然后呢，它这个数组，我们也把它改一下数组，因为这写的是四，要改成五，好hi和T。初始化为零。Hi，和ta出示外围。好，来一个，走hide。好，初始化，给他一个零字，Tell。也给他一个名字。好，这是我们队列。好，然后呢，在调的时候，这个方法肯定就不是他了，就换成我们的这个push。入入队列不是好，下面没有什么变化。下面变成变化，然后呢，Get get呢是从里面取一个东西出来，我们也把它打开，这边呢叫做pop。

没问题。好出队列显示队列呢，我们叫做。好像叫利利是什么玩意儿啊，叫。找这个啊，显示的是list q list q，好，同学们我们试一下。历史的Q，好，同学们试一下，好保存了啊，保存了玩一把，现在呢，我们就是环形队列的情况不一样了啊，同学们C，我先退出来。EXCD点点C到circle quick，然后呢，Go run，我们的命点够好。那么跑起来过后呢，我们先来往里面看看目前这个队列是个什么情况，说一下。队列为空，正确的。往里加东西了，爱的。第一个数一看一下里面有什么东西，数一下。哦，确实有一个元素下标为零，这方有个一，紧接着在I。

在爱的过不去呢，我们说一个二搜一下哦，里面有个二没问题，我就直接加了啊爱的走三。爱的。是。好，同学们，可以看到此时此刻我现在已经有12344个数了，那么这个时候我再往里面加就加不进去了。因为我们有一个呢，是要留下来做一个约定的，说在家呢，他应该报告我们上门啊，队列嘛，爱的再来五。他说。Queen。负正确的啊，我们要的就是这个效果，那么这个时候呢，你再show一下是没问题，现在我要取东西了啊，再往里面加是加不进去的，但是我取一个出来get一下，我应该取出这个一。因为现在它的这个对手呢，是在这一取出弹出来一个一正确，我们搜一下目前这个队列手变成它了，没问题，这个时候我能不能再加东西了呢。显然我就可以再加了，因为你是个环状的是吧，我再加一个爱的。

我再加一个五。加族队列成功了没有？成功了吧，加入这也成功了，我再搜一下，现在我问大家对手是不是还是二啊。对手是不是还是。它是它是234对尾是不是变成四了，这个你看这2345正确吧，正确的，那这个时候我如果再再往里面加，我还能加进去吗？我又加不进去了，因为它已经有四个了啊，你看再加一个六。他又说。那么这个时候我再取一个出来，取的是谁呢？取的是哪一个呢？二。二因为现在是对手了嘛，我再去他弹出一个二，好，弹出一个二的话，同时同时大家看现在又变成三个，我再弹一个出来。弹出的是三，我再弹一个出来，弹出四，再弹一个出来五。我在谈呢。

我在谈是现在先，大家想要对立面是什么？空了吧。然后我再谈，他就给我说什么呀。弹不出来。QNBD，但是我现在往里面加。我是还可以加的，加十。好，这有问题了。这个有点小问题了。这种问题在什么地方？哪地方出了问题了？我现在对列，我现在对的是什么地方？是在第这个24行是不是有问题，好，我们来看看24行的问题是什么。解决一下，好，同学们看问题的原因呢，我们刚才已经发现了，他在这地方报了一个24的错误，24的错误其实就是在这里。好，原因就是因为我们这完全没有对它进行一个处理，那应该怎么处理呢？等于Z。第二，它加一个一，然后再对它怎么样取模就可以了。

OK，走上我们的z.max。Max max。Size，同样的道理，同样的道理，我们push这么做，我们的pop泡呢也得这么做，对不对？因为你只考虑一个方向，你没考虑别的方向了，Hide同样这方也要写成害。好，这边也没变化，你看我这这这个地方是做了的啊，这方是做的，其他都没问题。其他都都处理了啊，好，这个应该就不会错了，这个方形肯定不会再错了啊好同学们，那关于这个环形队列呢，我就说到这儿，环形队列是很多，这个好一点的啊，就是那些公司很喜欢考这个，其实要把这个东西做出来，还是要烧下脑的。就你突然让你自己突然让你自己写一个出来。你还真不一定把它写的对。啊，还是要动动脑筋的啊，还是要动动脑筋，所以这个任务呢，一个任务啊，就是我们这个环形列表是要求大家能够默写下来的啊，原因就不再解释了，那么下次上课的时候呢，我们要求默写环形列表。

啊，环形环形队列，环形队列，好，我把这个给同学们展示到我们的笔记里面去。好，那么代码的实现呢，我们就放在我们的笔记中去了，好的。好，同学们，那关于环形链表的，呃，环形队列的一个实现啊，我们就给大家讲解到这里。