leetcode——设计循环队列-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode——设计循环队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

leetcode——设计循环队列,leetcode,算法,职场和发展
设计循环队列

leetcode——设计循环队列,leetcode,算法,职场和发展
这个题目在这里小编只分享一个解题思路，因为还有一个思路小编还在尝试，一直过不了，还在这里不断尝试，等我试出来的时候我在分享给大家，首先我们在这里给出的是数组的形式，后面在分享单链表的思路，因为数组在内存上是连续的，这里给出的思路是多开出一个空间的内存，然后我们在进行插入和删除，下面给一个图来给大家来看看。
leetcode——设计循环队列,leetcode,算法,职场和发展
我们可以看到我们这个数组其实是来存储四个字节大小的，但是我们多存储一个int类型大小的空间，如果tail+1 == head的话我们就当空间是满的。但是当我们的head是和tail相等的时候我们就可以认为是空的，所以这里多开一个空间的作用就出来了，就是可以保证这两个有区别，如果我们不是多开一个空间的话，我们怎么来保证他是满的还是空的。

leetcode——设计循环队列,leetcode,算法,职场和发展
因为我们是tail是指向数组有效空间的最后一个元素的，所以我们这里不多开一个空间的话，就无法来区别什么时候为空，什么时候是满的时候。我们先来看看他的一个接口函数。

leetcode——设计循环队列,leetcode,算法,职场和发展
让我们来定义这个循环队列是什么个样子的，首先我们得有一个数组来存储，然会k就是题目说的循环队列里面要存储的数据个数，还有我们得有两个来指向head和tail，其实也可以是指针，但是我们这里用数组下标的方式才是最好的。
有了结构体之后下一个就是给的初始化的函数接口，首先肯定就是结构体中a这个指针，我们得给他malloc一个数组空间出来，其次就是head和tail这两个得初始化为一个值，因为我们后面是有判空的一个接口函数，所以这里并不难分析出来一开始的时候就得给初始化成一样的值，所以这里给0是最合适的，是刚开始的时候没有一个数据存储在里面。

leetcode——设计循环队列,leetcode,算法,职场和发展
这里大家可能对这个结构体会有疑问。

leetcode——设计循环队列,leetcode,算法,职场和发展
我们一开始就得开辟空间给obj这个指针，他得指向一个有效空间，大小刚刚好就是结构体的大小，然会a在这个结构体中其实就是一个指针大小，因为我们后面只需要让他指向一个数组空间大小就行了。

后面的判空函数就显得格外简单了

leetcode——设计循环队列,leetcode,算法,职场和发展
只要是相等的时候，就是空，不只是第一次，我们可以看后面的插入和删除如果出现head和tail是相等的时候这个时候也是为空的

进行下面的操作之后就是head和tail相等的时候，和我们判断空的时候是一样的，然后需要进行的下一个接口函数就是我们来判断是不是满的时候，因为我们设定的时候tail就是指向后最后一个元素的后面一个元素，所以满的时候就是tail+1 == head的时候，但是我们这个是个循环队列，比如在下面这个图的时候，满的时候进行+1就是越界的行为
leetcode——设计循环队列,leetcode,算法,职场和发展
就是这个时候，如果我们进行+1就是5，那我们这里进行的操作就是用一个取模的方法才是最好的，我们知道当我们一个数模上一个比他大的数的时候还是自己本身，所有这里我们可以先让tail+1因为大多的情况下的时候tail是在中间位置，满了的话head就是他的下一个，所有我们这里还需要进行的操作就是在加上一个k+1，这样的话那就可以保证tail是最后位置的时候取模也不会是0.我们在模上一个k+1就可以解决了。

leetcode——设计循环队列,leetcode,算法,职场和发展
所以我们写成这样就可以解决问题，这里取模的好处就是刚刚好满足循环，我比你大了，我取模就又可以回来了，解决了如何给他循环起来的问题，如果我们用单链表的就写一个循环链表我们来存储数据就可以解决了。

下一个接口函数就是如何进行插入和删除。我们这里插入就是让我们的tail位置放入数据，然后进行插入就可以解决问题，但是插入之后我们tail得往后移动，但是这里最大的问题就是如果tail到尾巴的时候，我们再进行++又就是越界，那leetcode就会给你一个越界访问的提示，所以这里最好的办法还是取模就可以解决这个问题了，首先就是我们tail得+1，然后因为取模的话我们得先给他加上一个数，这个数要不影响最后的结果，取模的最大左右就是当我们给出一个超大数的时候，最后的结果也是模的那个数和0之间，比如我们模上这里的k+1，然后取模的范围就是0—k+1

leetcode——设计循环队列,leetcode,算法,职场和发展
所以我们上面就可以写成这个样子，如果满了的话就不能插入，因为这里返回值是个bool值，所以我们的返回值就是true和false

既然插入需要判断，那删除也是需要判断的，所以空了我们就不要进行删除了。

leetcode——设计循环队列,leetcode,算法,职场和发展
这里也是用了这样的方法，其实取模大家可以多带几个数进行感觉，光说的话理解起来是特别的难受的。

leetcode——设计循环队列,leetcode,算法,职场和发展
去对头的话直接返回就行，但是去队尾的话需要进行一些操作，因为我们规定的是tail后面的元素，所以要返回的应该是tail前面的一个元素的值，那因为tail可能是再数组下标为0位置的地方，所以我们这里就应该用取模，其实大家发先我们就是加上（k+1）的这个值然后整体取%（k+1），（k+1）%（k+1）就是0其实对原来的是不受影响的。。