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

好，我们来看一下啊，我们来看一下。我们来看一下，那么刚才实现的这个队列的结构呢？呃，它有一个缺陷，就是没有有效的利用数组的空间，它用一次就完了，就好比是一次性的队列一样，对吧？就跟我们到餐馆里面去吃这个东西，一次性的用完就没有了，这肯定是不合理的。不合理，那怎么办呢？那么我们现在呢，就要用使用数组来实现一个环形的队列，那我们先做一做它的一个思考和它的一个分析。好，那么现在我们看一下数组模拟环形队列。数组模拟环形队列，我们先谈一下自己的一个思路啊，谈一下自己的一个思路和他的一个想法，那大体是这样子一个思路。前面的数组模拟队列的队列的优化就是在这上面进行一个优化，充分利用数组，因此呢，将数组看成是一个环形的，就把它看成一个环状。

那么通这个环状怎么来形成这个环状呢？它关键点是在于要取模。因为你到最后诶再往下面走。它虽然不能往出，但是我加一它不就回去了吗？你打个比方，你看啊，同学们，比如说我们两个都跑这来了。啊，如果一到这来，大家想一想，我们怎么让这个RA，就是让它这个尾部能够到前面去呢？你看啊，它现在比如说到这地方，我举个例子，Real，它目前是等于四对不对。那等于是我怎么能够让它的下边又重新回到一呢？那你看一个最简单的方式，就是让这个RA。加上一个一，加上一个一，再模上它的最大值。就是max嘛。Size这样子一模，哎，你当然这个这个要括起来对吧，就是它的RA加上一再取模，这样不就变成零了吗。

诶，这样子就有效的让他又回到了前面去。啊，就这样一一个思路，这个这个思路就分析出来了。好啊，所以说我们这个地方的关键点，第一个就是可以通过刚才的一个取模的方式来实现，就是刚才大家看到T，我我就叫T了啊，T加一模上这个max等于head，这个可以往后走。那这里面有一个问题，就是怎么去判断环形列表？就是环状的这个，环状的这个这个数组它满了呢。他买了什么时候买呢。他要这么去加一模上max size等于he的时候就满了，那也就是说其实这地方有一个约定，就是做用这个数组来模拟一个环形列表，有一个特别重要的约定，就是这个队列要队列的容量要要空出一个，做一个约定。

这点不是特别容易分析出来。就是他一定要空一个，他如果一个都不控的话，很难实现。那我说一下这个是什么含义啊，同学们。什么含义呢？你比如说吧，同学们，假如我们这个地方这样这样满了啊，比如说叫满了，比如说我们这个尾部，尾部第一步front在这。加了一个。好，又加了一个。加了一个。好，如果是如果这个时候，如果这个时候呢。我们继续往前面再走一下。再走一下，那么我们就先要去探测一下。还能不能往后走，因为我们要留一个做一个空间，你比如说呃，它原先这个初始化的时候，这个A，它初始化在在这个零这个位置，你这个位置T呢，在这个位置。

在这个位置，如果我加一个，一加一个这个胎这个，最后这个尾部再加一个，一发现已经等它相等了，那就不能再往里面加东西了，再加的话，那你这个就加不进去。所以说在这地方有一个约定，就是什么呢？我们再要去T加一模上这个max size的时候呢，我们要去看它到底还能不能往里面加，所以我们要留一个这个容量，做出一个空留，留出一个这个容量做一个约定。哎，还有一点什么时候为空呢。什么是为空呢？就是它的尾部和它的头部相等的时候，我们就认为它是空。啊，跟那个原先一样的道理，就是不停的追追追追追到最后他们追到相同了，好这个呢，我们就认为是空。好，那现在呢，大体的这个思路有了过后呢，我们就来实现它一下啊，这个实现起来呢，呃，跟前面有一些微小的差别，微小的差别，但大体还是差不多的，好，我把这个思路先给同学们放到这来，然后呢，我们把它实现了。

好，这是我的一个思路啊，同学们。这是刚才的一个大体的思路，这有几个重点，一个呢就是队列的容量空出一个作为约定，这个呢，用来判断队列满的时候需要一个加一，就是这个T加一，如果发现它等于的话，就就不能再再往后面走了啊，不能再往后面走了，好把它放到这来。好，这是我的一个思路，那现在呢，我们就来直接走一下代码啊，思路就大体的就说到这儿啊，关键点这里面我们分析出来几个重要的地方啊，我们分析出来几个重要地方第一点。说明一下这个分析出来的内容。分析思路。分析一下这个思路，他的思路呢，我们总结出来有这么几几个比较重要的地方，第一点呢，第一点就是我们分析出来它的尾到时验初始化的时候啊，啊，它的满度就是什么时候满了。

什么时候表示满？什么时候时候表示表示这个队列满。那么它的条件呢，就是刚才老师说的这个尾部加一个一把它加起来过后再磨上一个马size。摸上它的最大值。啊，如果这个呢，它等于了，Hi，这就就要满什么时候啊，什么时候为空呢？什么时候为空呢，就是tell等于了，这个had的时候就表示空。就他们两个呃，下标相等了就表示空，还有一点要分析出来，还有一点分析出来就是。我们在刚开始的时候怎么初始化的问题？就是刚开始这个tell还等于多少。

好，那么当刚开始的时候呢？初始化时，初始化时。这个呢，我们这个T和这个had呢，都等于零。都要给他分一个零。都等于零，那等于零的情况下呢，实际上就是这方有点不好理解哈，就它等于零的话，就相当于直接指到了我们这个数组的最前面。这个跟刚才有点区别。有一点区别就是他这方指到最前面的，就是他们刚开始都指到最前面。啊，直到最前面。好，这个是需要同学们呃知道的第三点，还有一点就是指到这个前面啊，还有一点就是我们要知道它到底有多少个数据，一共有多少个数据，怎么计算出来，就是还有一点就是说怎么统计。啊，怎么统计，统计该数组一共有多少个元素该队列吧，该队列有多少个元素？那么倒行是这样算的，就是它的tell。

加上max size，再减去。然后把它包起来，抹上马克塞。啊，这个魔上马克塞。那有些同学说，老师为什么这样算呢？因为这样子的啊，你太理论上来说，尾部总是应该比头部要大的。理论上应该是这样子，因为你你你的队列嘛，你的队列为肯定比你害的要大嘛，但是因为我们这个队列它在最后的，他反过来跑到后面去，所以说我在统计的时候，我把它那个最大值加上。再剪掉它，再磨上这个就对了。那你举个例子啊，你举个例子，你比如说咱们有这么一个情况，哎，比如说这个数据我们不停的走，哎，他原先它原先这个这是这是它的front初始化为零，我们看看对不对啊，初始化为零，它是零的，然后我加了一个元素走这。

我加了个一，我加了过之后，我尾部往后面移下，你看大小我一共有多少个元素呢。尾部嘛，他头部这方，头部这个地方现在还没有数据啊，他现在还没有还没有数据呢，对，就头部这方是相当于是还没取。还没有取，所以说这个时候你看按照这个公式来算的话，按照这个公式来算的话，就应该是怎么算呢？诶看一下这个地方，它就是这样子的，尾部现在变成了一一加上这个它的大小假设是五吧五。再减去头部为零。头部为零，那就是五减一加五减零等于六，六模上一个五，诶刚好等于一啊是这样算出来的啊这样算出来的，那当然这个呢，大家可能还去想一想啊好呃，待会儿我把这个数据调小一点，调成四，不然的话不好做测试啊，不好做测试。

好，还有一点就是这个多少个元素有了过后，基本上咱们就可以可以来玩一下了啊，咱们来玩一下。好，下面呢，我们就来代码实现。代码实现好。代码实现。好，现在呢，我们已经做了一个思路分析，先把这个给同学们说，说到这儿。