环形队列实现原理

使用数组实现队列，用顺序存储时涉及到了“假溢出”的现象。所谓“假溢出”就是随着对队列的不断删除和插入，队尾指针rear就指到了队列所在空间的最顶端，也就是说此时队列不能再插入了，好像满了，可是队列的另一头front指针还有很多空间（即删除数据节点后释放的空间）没有利用的现象。

为了解决这一问题，通常采用队尾和队头相连接的方法来提高空间的利用率，即环形队列。环形队列并不是物理上循环，只是逻辑上实现循环而已。

假设队列为Q，最大空间为8，用MaxSize来代替这个长度8，空间从0到7来标识。若增加队头或队尾指针，可以利用取模运算（一个整数数值整除以另一个整数数值的余数）实现。当到了假溢出时，即队尾指针到了第7个空间时，它的下一个位置就是第0个空间，就像日常生活中的时钟，12点之后就是1点，这样的话就要对MaxnSize进行取余。

当做删除时要：rear=（rear+1）% MaxSize；

当做插入时要：front=（front+1）% MaxSize。

在对队列进行删除时要判断队列是否为空，进行插入时要判断队列是否为满，这时就产生了一个矛盾，此时队列满和队列空的条件就变成了一样的。

即：Q.rear == Q.front

这样就给程序带来了不便，不能区分队列满和队列空了。

为了区分队列满和队列空，通常有两个办法来解决。

（1）设计一个计数器，例如num，插入一个数据元素时，计数器加1，删除一个数据元素时，计数器减1。这样非常明确，计数器为0，则判断队列为空；计数器为空间最大值时，则判断队列为满。

（2）在循环队列中少用一个数据元素的空间，并约定对头指针在队尾指针的下一个位置上作为满的标志。

所以，

队列空的条件是：Q.front == Q.rear

队列满的条件是：(Q.rear+1) % MaxSize == Q.front

以上队列满和空成立的条件有一个重要的前提，那就是初始化一个队列时的条件一定是：Q.front = Q.rear = 0，否则就不一定合适了。