循环队列是指队列是前后连成一个圆圈, 它以循环的方式去存储元素, 但还是会按照队列的先进先出的原则去操作. 循环队列是基于数组实现的队列, 但它比普通数据实现的队列带来的好处是显而易见的, 它能更有效率的利用数组空间, 且不需要移动数据.
普通的数组队列在经过了一段时间的入队和出队以后, 尾指针 rear 就指向了数组的最后位置了, 没法再往队列里插入数据了, 但是数组的前面部分 (front 的前面) 由于旧的数据曾经出队了, 所以会空出来一些空间, 这些空间就没法利用起来, 如图:
当然可以在数组尾部已满的这种情况下, 去移动数据, 把数据所有的元素都往前移动以填满前面的空间, 释放出尾部的空间, 以便尾部还可以继续插入新元素. 但是这个移动也是消耗时间复杂度的.
而循环队列就可以天然的解决这个问题, 下面是循环队列的示意图:
循环队列也是一种线性数据结构, 只不过它的最后一个位置并不是结束位. 对于循环队列, 头指针 front 始终指向队列的前面, 尾指针 rear 始终指向队列的末尾. 在最初阶段, 头部和尾部的指针都是指向的相同的位置, 此时队列是空的, 如图:
当有新元素要插入到这个循环队列的时候(入队), 新元素就会被添加到队尾指针 rear 指向的位置(rear 和 tail 这两个英文单词都是表示队尾指针的, 不同人喜欢的叫法不一样), 并且队尾指针就会递增加一, 指向下一个位置, 如图:
当需要做出队操作时, 直接将头部指针 front 指向的元素进行出队(我们常用 front 或 head 英文单词来表示头部指针, 凭个人喜好), 并且头部指针递增加一, 指向下一个位置, 如图:
上图中, D1 元素被出队列了, 头指针 head 也指向了 D2, 不过 D1 元素的实际数据并没有被删除, 但即使没有删除, D1 元素也不属于队列中的一部分了, 队列只承认队头和队尾之间的数据, 其它数据并不属于队列的一部分.
当继续再往队列中插入元素, 当 tail 到达队列的尾部的时候:
tail 的下标就有重新变成了 0, 此时队列已经真的满了.
不过此处有个知识点需要注意, 在上述队列满的情况下, 其实还是有一个空间是没有存储数据的, 这是循环队列的特性, 只要队列不为空, 那么就必须让 head 和 tail 之间至少间隔一个空闲单元, 相当于浪费了一个空间吧.
假如此时我们将队列中的 D2,D3,D4,D5 都出队, 那队列就又有空间了, 我们又可以继续入队, 我们将 D9,D10 入队, 状态如下:
此时, 头指针的下标已经大于尾指针的下标了, 这也是正式循环队列的特性导致的.
所以可以看到, 整个队列的入队和出队的过程, 就是头指针 head 和尾指针 tail 互相追赶的过程, 如果 tail 追赶上了 head 就说明队满了(前提是相隔一个空闲单元), 如果 head 追赶上了 tail 就说明队列空了.
因此循环队列中, 判断队列为空的条件是: head==tail.
判断队列为满的情况就是: tail+1=head(即 tail 的下一个是 head, 因为前面说了不为空的情况下两者之间需相隔一个单元), 不过如果 tail 与 head 正好一个在队头一个在队尾 (即 tail=7,head=0) 的时候, 队列也是满的, 但上述公式就不成立了, 因此正确判断队满的公式应该是:(tail+1)%n=head
来源: https://www.cnblogs.com/jsjwk/p/11510755.html