为什么要设计循环队列

前面数组实现队列的课程里，我们知道，线性队列存在空间浪费的问题。为了解决这个空间浪费，我们提了两个解决方案：一是每次出队的时候，将所有的元素前移一位，保证队头始终在数组的索引0处。二是等rear=size-1的时候，统一再向前移动。由于在数组中删除元素和移动元素非常不方便，尤其是当数据量大的时候，会导致程序运行的耗时增加，系统性能下降。
为了解决上面的问题，我们提出了循环队列，在不移动数组元素的情况下，实现环形队列。我们可以把数组的第一个元素和最后一个元素想象成首位相连的，就会出现以下的队列。

在上面的示例图中，我们将front始终指向头节点的前一个节点，之所以这么做是因为队空和队满的时候，front和rear都指向同一个位置，这个时候，我们就不知道队列到底是空的还是满的。不过这么做的话，数组中永远有一个元素是空的，我们的队列最多只能放下n-1个元素。下面的伪代码中我们用n表示队列的容量，也就是数组的长度。
1、队列空：front==rear;
2、队列满：(rear+1)%n==front；
3、出队：front=(front+1)%n;
4、入队：rear=(rear+1)%n；

队列的定义

我们在程序中声明CircleQueue类代表循环队列，类中声明的queue表示存放队列元素的容器，size表示容器的容量，也就是queue的长度。front和rear分别表示队头和队尾。

internal class CircleQueue
{
    int[] queue;//存放队列元素的容器
    int size;//队列容量
    int front;//队头
    int rear;//队尾
}

算法1：入队

由于rear始终指向队列尾部，所以需要将rear向后移动一个位置，然后再给这个位置赋值即可。

public void EnQueue(int data)
{
    if (IsFull())
    {
        throw new Exception("队列满了！");
    }
    rear = (rear + 1) % size;
    queue[rear] = data;
}

算法2：出队

由于front始终指向队列的前一个位置，所以需要先将front向后移动一个位置，然后再返回这个位置的值。

public int Dequeue()
{
    if (IsEmpty())
    {
        throw new Exception("队列为空！");
    }
    front = (front + 1) % size;
    return queue[front];
}

算法3：队列是否为空

public bool IsEmpty()
{
    return front == rear;
}

算法4：队列是否满了

public bool IsFull()
{
    return ((rear + 1) % size) == front;
}

示例代码地址

https://gitee.com/jiamingyuanjin_admin/data_struct/blob/master/DataStruct/09CircleQueue.cs

关于队空和队满条件判断。

上面的代码中，我们初始化空队列的时候，默认front=rear=-1；同时front始终指向队头位置的前一个位置，这样的话就牺牲了数组中的一个位置，导致数组最多可以存放n-1个元素，其实这一个元素对程序的影响也不大。
现在我们介绍队空和队满的另一种方案，count计数方案。在CircleQueue类中声明一个变量count表示队列中元素的数量，当count==0的时候，队空。当count==size的时候，队列满。这种方案有一个好处就是非常容易理解。入队的时候count++，出队的时候count--，front指向队头的前一个位置，rear指向队尾。第二种方案在文章里面，我就不给大家贴代码了，有兴趣的可以查看https://gitee.com/jiamingyuanjin_admin/data_struct/blob/master/DataStruct/10CircleQueue2.cs这里的实现。

循环队列