这篇文章我们来学习一下如何实现循环队列 那力扣上呢有一个对应的题我们可以来看一下：
循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。 要求我们实现的循环队列要有以下几个接口：
那下面要实现循环队列的话，我们采用哪种结构呢，数组还是链表呢？
我们假设循环队列的长度k（当然实现好之后k传几构造出来长度就是几）为4，我们来分析一下。
首先我们来分析一下用链表行不行
链表结构分析
那链表的话我们是不是正好可以用一个循环链表啊，因为我们现在要实现循环队列嘛：
搞一个循环单链表，循环队列长度为4，所以开4个结点。
看起来好像还挺合适的。 那现在结点上来直接就开好了，如何判空或者判满呢？ 🆗，那我们可以定义两个指针front和rear，来标识队头和队尾的位置
那front和rear都指向第一个结点（），就可以表示空。 那插入数据怎么做呢？ 🆗，队尾入数据那对应我们这里的链表来说就是尾插嘛，所以，给rear指向的结点赋要插入的值，然后rear往后走指向下一个结点
所以rear就是指向最后一个元素的下一个，空队列的时候指向第一个结点。 那我们继续插入
此时我们发现一个问题，插入满了之后，rear就重新回到了第一个结点，此时front和rear又指向了同一个结点（）。 那我们发现判空和判满的条件都是（） 那这样就分辨不开了，怎么办？
那这里解决方式呢不止一种：
比如你可以增加一个size记录有效数据的个数，用size==k来判满。 但是我们这里不采用这种方法，我们还可以这样做： 多开一个结点（开k+1个），就可以解决这个问题 多开一个结点，判空呢还是，而判满则用
而且，这个多开的结点也可以存储数据，在后续的操作中，这个空余结点可能是任意一个结点。 我们继续往下看 此时满了，不能再入数据了，那如何删除数据呢——队头出数据 那就是链表的头删，当然这里我们不会真的删除结点，怎么做呢？
很简单，我们让front往后走就行了（），被“删除”的数据也不用抹掉啥的，因为后续再入数据给会他覆盖掉（我这里只是这样画） 那然后再插入呢？
那我再来pop四次删到空呢？
删到就是空了。
那走到这里我们发现这个结构好像就跑通了，用循环单链表实现好像挺棒的。
但是此时我们再来看要实现的几个接口：
我们发现构造，获取队头元素，插入，删除，判空判满这些都不难搞。 但是获取队尾元素是不是很麻烦啊。因为我们这里是一个单向循环的链表，找尾是比较麻烦的。
当然也可以解决：
可以再增加一个指针prev，记录rear的前一个，这样只要队列不为空，就可以通过prev直接获取队尾元素。 也可以解决。
链表呢我们看了这么久，刚开始感觉还不错，用循环链表刚好有这个环的感觉，非常合适，但是最后发现还是有一些缺点。
那此时呢，我们不妨来考虑一下另外一种结构——用数组实现怎么样呢？
数组结构分析
我们来分析一下，还是以K=4为例：
首先有了上面的分析经验，我们的数组也多开一个空间
但是数组的话首先看上去就不如上面的链表，因为看着根本不循环。 那如何让它实现循环呢？ 那也很简单，走到结尾的时候，我们让它回绕到下标0的位置就行了。
判空判满
那数组实现的话如何判空判满呢？
判空的话很简单
还是可以以为空（在哪个位置，就等于该位置下标值） 那判满呢？ 吗？
如果是上面这种情况呢确实是，但是： 如果是下面这样呢？
rear+1是不是就越界了啊。 那怎么办呢？那就要让它回去，给rear+1模上一个k+1（即数组的长度） 所以统一处理：如果，就可以同时处理两种情况的判满。 大家可以代入验证一下。 当然也可以给这种情况（）单独加一个判断，如果此时是满的，front肯定等于0，去判断front是否等于0
入数据出数据
那我们再来分析一下插入删除即队尾入数据和队头出数据：
首先入数据是不是很简单啊
给rear下标的元素赋值，然后rear++就行了 但是，需要注意：
如果是这种情况，rear==k再++（等于k+1)是不是就越界了。 那这种情况可以加一个判断 或者也可以用取模的方式，让它%k+1。当然如果用取模的话就不用判断，因为如果rear<k+1，%k+1之后值是不会变的。
那我们再来看一下队头出数据：
也很简单，正常的pop就直接让front++就行了
需要注意的也是front走到越界的时候
此时如果删了5之后，再++就越界了（front==k+1），得让他回到0 那跟上面一样，可以去模k+1，或者加个判断，把它置成0。
取队头队尾元素
那最后再来分析一下取队头和队尾元素：
先来看取队头元素，非常简单： 只要队列不为空（为空题目要求返回-1），直接返回下标front的元素就行了 那取队尾元素呢？ 上面分析链表就是取队尾元素麻烦，但是数组，就很简单了：
下标rear-1的元素不就是队尾元素嘛。 当然，也需要注意一下：
怕的是这种情况，rear为0，那rear-1是-1，越界了。 但是也很好处理，还是两种方法： 可以单独加一个判断，如果rear==0，把它置成k，其余情况就是rear-1 当然可以写成这样 另外一种方式就还是取模可以两种方式统一处理： ，此时rear-1是-1嘛，越界了，加个k+1，就变成k了； 而对于其它情况也适用，其它情况rear-1肯定小于k+1，所以模一下不受影响。 简化一下即
那综合分析一下，其实还是数组会简单一点，所以下面我们就用数组来实现。
画图理清思路，写代码还是很简单的：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/181374.html