循环队列及假溢出的现象图文详解

1. 顺序队列的假溢出&循环队列的概念

我们已经明白了队列这种基本数据结构，对于顺序队列而言，其存在已经足够解决大多时候的设计问题了，但是其依旧存在一些缺陷和不足，因为我们的入队和出队操作均是直接在其后面进行结点的链接和删除，这就造成其使用空间不断向出队的那一边偏移，产生假溢出。

什么是假溢出？打一个比方：

（示例顺序队列）

回顾一下队列的性质，首先我们有一个顺序队列，这个队列的大小为5，其已经包含了四个元素data1,data2,data3,data4,接着，我们对这个队列进行出队操作，出队2个元素，队列就变成了这个样子：

目前看起来没有问题，那么我们接着再进行入队操作，我们入队2个元素，分别是data5和data6，此时我们已经发现问题了，尾指针移动到我们可以进行队列操作的范围之外去了，我们称呼作为队列用的存储区还没有满,但队列却发生了溢出,我们把这种现象称为"假溢出"。

（出队产生假溢出）

可能这个时候会产生一个疑问，我们学习的队列不是使用链表实现的动态队列么？没有空间的时候会开辟空间，这难道还会产生假溢出么？

是的的确，当进行动态创建队列的时候，也只不过是向后继续不断的申请内存空间，即时前面出队操作释放掉了前面的空间，但是指针依旧会向后进行移动，直到达到系统预留给程序的内存上界被强行终止，这对于极为频繁的队列操作和程序而言是致命的，这时候，就需要对我们的队列进行优化，使用更为优秀的结构——循环队列。

循环队列的思维非常简单，就是给定我们队列的大小范围，在原有队列的基础上，只要队列的后方满了，就从这个队列的前面开始进行插入，以达到重复利用空间的效果，由于循环队列的设计思维更像一个环，因此常使用一个环图来表示，但注意其不是一个真正的环，循环队列依旧是单线性的。

2. 循环队列的结构设计

由于循环对列给定了数据范围的大小，则不需要使用链式的动态创建方法了（如果依旧使用链式存储，会无法确定何时再回到队头进行插入操作），因此我们采用模拟的方法，如图所示：

其中，data表示一个数据域，int为类型，其可以修改为任意自定义的类型，比如说简单的char,float类型等等，也可以是复杂的结构体类型，我们使用maxsize表示循环队列的最大容纳量，其表示队列的全部可操作空间。

rear代表尾指针，入队时移动。

front代表头指针，出队时移动。

其代码可以表示为

#define maxsize 10      //表示循环队列的最大容量
 
//循环队列的结构设计
typedef struct cir_queue{
    int data[maxsize];
    int rear;
    int front;
}cir_queue;