队列的结构

队列是一种受限制的线性表数据结构，它允许在表的一端进行插入操作，在表的另一端进行删除操作。我们把允许插入的一端叫做队尾，允许删除的一端叫做队头。
简单点说，队列是一种先进先出的线性表。

队列的顺序存储和链式存储

顺序存储：利用一组连续的存储单元存储从队头到队尾的元素，连续的存储单元通过数组实现，同时通过front表示队头在数组中下标，rear表示队尾在数组中的下标。
链式存储：利用单链表的头节点和为节点分别表示front和rear。只允许在头部删除，尾部插入。所以链式存储实际上就是受限制的单链表。
这一节我们介绍顺序存储的相关算法，链式存储的相关算法在下一章节会有详细的介绍。

队列的定义

我们在程序中声明一个Queue类来表示队列类，其中数组queues用于存放队列中的元素，size表示队列的容量，front表示队头在数组中索引，rear表示队尾在数组中的索引。在初始化的时候front和rear都设置为-1。
队列空的条件：rear==front
队列满的条件：rear=size-1

internal class Queue
{
    int[] queues;
    int size;
    int front;//队头
    int rear;//队尾
}

算法1：入队

入队就是在队尾插入一个元素，同时修改队尾指针rear，具体示例代码如下：

public void EnQueue(int data)
{
    if (rear == (size - 1))//队满 扩容
    {
        int[] newArr = new int[size * 2];
        size = size * 2;
        for (int i = 0; i < rear; i++)
        {
            newArr[i] = queues[i];
        }
        queues = newArr;
    }
    queues[++rear] = data;
}

算法2：出队

出队就是从队头删除一个元素，同时修改队头指针front。

public int Dequeue()
{
    if (front == rear)
    {
        throw new Exception("队列为空！");
    }
    return queues[++front];
}

算法3：队列是否为空

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

算法4：查看队头元素

查看队头元素，不会执行出队操作，只是返回队头那个元素信息。

public int Peek()
{
    if (front == rear)
    {
        throw new Exception("队列为空！");
    }
    return queues[front + 1];
}

示例代码地址

https://gitee.com/jiamingyuanjin_admin/data_struct/blob/master/DataStruct/07Queue.cs

总结

数组作为队列容器的时候，有一个问题就是，当我们执行了一些次数的出队操作之后，数组中0到front位置的空间就会被浪费，有一个办法就是每次出队的时候，把数组中所有数据向前移动一位，队头始终指向数组的第一个位置，不会有空间浪费，但是这样显然太麻烦。还有一种办法就是等队尾指向数组最后一个位置的时候，将数组中的数据统一向前移动。如果不需要向前移动的情况下，就需要扩容。后面我们也会学习一种循环队列，可以帮助我们将数组空间有效利用起来。

数组实现队列