本文介绍循环队列及其C语言的实现

假溢出

回想我们之前队列的数组实现，其中：

1. 我们判断队列为满的条件为rear==数组的大小-1（数组的坐标是从0开始的）
2. 我们判断队列为空的条件为front==rear

考虑这样一种情形：

1. 队列中rear=数组的大小-1，我们可以认为队列已满，因此数据再也不能入栈
2. front=rear-1队列不为空

假如我们为队列申请申请的数组大小为1000，经过一番操作，队列变成了如下图所示的情况，若：rear=999，front=998，根据我们设定的条件，队列已满（不能再进行入栈操作）

然而，图中我们可以看到，队列中其实只有数组的1个被用到了，因此，我们队列的空间利用率为1/1000，居然有99.9%的空间被浪费掉了！而且，这只是数组比较小的情况。

以上现象称为“假溢出”：

• 系统作为队列用的存储区还没有满，但是队列再也不能进行入队操作

为充分利用空间，克服“假溢出”现象，循环队列被提了出来。

循环队列

循环队列中，第一个索引紧跟在最后一个索引之后，如下图所示（我们用Q表示队列，用N表示队列的大小）：

因此：

• 当front = -1和rear = N-1时，循环队列将满

循环队列的操作

入队

• 若(rear+1) mod N等于front，则队列已满
• 若real != N-1，则队列未满，则rear = (rear+1) mod N，直接添加到队尾
• 若front != 0且rear等于N-1，意味着循环队列中删除过元素（front > 0），因此循环队列未满，我们可以令rear = 0，并在该位置插入新元素

出队

• 若front = -1，队列为空
• 如果front == rear，队列中只有一个元素，因此可将-1赋给front和rear，以删掉最后一个元素，让列表为空
• 若front == N-1，将front置为0完成删除
• 一般情况，front直接加1完成删除

遍历

输出front到rear之间的元素

• 如果front小于rear，正常遍历输出
• 如果front大于rear，输出front到N-1和0到rear之间的值

查找

遍历的过程中与给定数据进行比对以查找

循环队列的C语言实现

以上提到的所有操作都使用C语言进行了实现，具体代码见Github

代码运行效果如下：

才疏学浅，难免有错误和不当之处，欢迎交流批评指正!
同时有问题的话欢迎留言或邮箱联系（[email protected]）。