队列的定义：
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
队列的顺序存储
假设我们一个队列有n个元素，则顺序存储结构的队列需要建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端是队头。入队操作就是在队尾追加一个元素，不需要移动任何元素，时间复杂度为O(1)。出列是在队头，即下标为0的位置，所有元素都得向前移动，以保证队列头部位空，时间复杂度O(n)。
如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加，即队头不需要一定在下标为0的位置。
为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾的下一个位置，这样当front等于rear时，队列为空队列。
初始状态，front和rear指针均指向下标为0的位置。
入队操作时，front指针不动，rear指针后移。
出队操作时，front指针后移，rear指针不动。
当front大于0时，rear指针大于了数组界限，此时称为“假溢出”。
循环队列定义
解决假溢出的办法就是后面满了，就再从头开始，就是头尾相接的循环。
我们把队列的这种头尾相接的顺序存储结构称为循环队列。
继续，
当数组后面元素满了，rear指针就指向下标0位置。若此时，一直入队操作，rear指针就会与front指针重合！
问题来了
刚说了，空队列时，front等于rear，现在当队列满时，也是front等于rear。此时如何判断？
①设置一个标志变量flag，当front==rear，且flag=0时为队列空；当front==rear，且flag=1时为队列满。
②空队列就是front==rear；满队列时，我们修改其条件，保留一个元素空间。也就是说，数组中还有一个空闲单元，我们就认为队列已经满了。（不会让rear指针追上front指针）
我们实现第二种。
由于rear可能比front大，也可能比front小。假设 队列的最大尺寸为QueueSize，那么队列满的条件是：
(rear + 1) % QueueSize == front 。
另外，当rear>front，此时队列的长度为rear-front；
当rear<front，队列长度为两段，一段是QueueSize-front,另一段是0+rear，此时队列的长度为rear-front+QueueSize；
通用的计算队列的长度的公式为：
（rear-front+QueueSize）% QueueSize。
public class Queue<T>
{
private readonly int MaxSize = 10;
private T[] _array;
private int front;
private int rear;
public Queue()
{
front = 0;
rear = 0;
_array = new T[MaxSize];
}
public int QueueLength()
{
return (rear - front + MaxSize) % MaxSize;
}
public bool IsFull()
{
return (rear + 1) % MaxSize == front;
}
public bool IsEmpty()
{
return front == rear;
}
public void EnQueue(T item)
{
if (IsFull())
{
Console.WriteLine("IsFull");
return;
}
_array[rear] = item;
rear = (rear + 1) % MaxSize;
}
public T DeQueue()
{
if (IsEmpty())
{
return default(T);
}
T item = _array[front];
front = (front + 1) % MaxSize;
return item;
}
public void Display()
{
if (IsEmpty())
{
return;
}
int _front = front;
while (_front % MaxSize != rear)
{
Console.WriteLine("data--" + _array[_front].ToString() + "index--" + _front.ToString());
_front = (_front + 1) % MaxSize;
}
}
}队列的链式存储结构及实现
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。
public class Node<T>
{
public T data;
public Node<T> next;
public Node()
{
data = default(T);
}
public Node(T item)
{
data = item;
}
}
public class LinkQueue<T>
{
private Node<T> front;
private Node<T> rear;
private int count;
public LinkQueue()
{
front = null;
rear = null;
count = 0;
}
public LinkQueue(T item)
{
Node<T> temp = new Node<T>(item);
front = temp;
rear = temp;
count = 1;
}
public int LinkQueueLength()
{
return count;
}
public bool IsEmpty()
{
return count == 0;
}
public void EnQueue(T item)
{
Node<T> temp = new Node<T>(item);
if (IsEmpty())
{
front = temp;
rear = temp;
count++;
return;
}
rear.next = temp;
rear = temp;
count++;
}
public T DeQueue()
{
if (IsEmpty())
{
return default(T);
}
Node<T> temp = front;
front = front.next;
count--;
return temp.data;
}
public void Display()
{
if (IsEmpty())
{
return;
}
Node<T> temp = front;
while (temp != null)
{
Console.WriteLine("--" + temp.data.ToString());
temp = temp.next;
}
}
}在空间上链队列更灵活。
在可以确定队列最大值的情况下，建议使用循环队列，如果无法预估队列的长度，则使用链队列。