1.队列是插入操作限定在表的尾部而其他操作限定在表的头部进行的线性表。首先我们把队列的一些基本操作抽象为接口，如下：
public interface ICaryQueue<T>
{
int GetLength();
bool IsEmpty();
void Clear();
void In(T item);
T Out();
T GetFront();
}
2.下面就是具体的实现了，使用连续的存储空间来存储队列中的数据元素为顺序队列。我们用一维数组来存储，对头front设在数组下标为0的端队尾rear设在另一端。当队列为空时front=rear=-1.当有数据入队时，队尾rear加1。当有元素出队时，对头front加1.当front=rear的时候，队列为空。当队尾rear达到数组的上限而front为-1的时候队列为满。
但是，有下图的情况：
在上图右边的情况如果再有一个元素入队就会导致溢出，但实际上数组却还有空间，我们称这种情况为假溢出。解决这种假溢出的方式就是将首尾连接起来，也就有循环顺序队列。如下图：
3.当队尾rear到达数组上限时，如果还有数据入队并且数组第0个空间空闲时，队尾就指向了数组的第一个元素0，所以在循环队列中队尾rear的操作应该修改为：
Rear=(rear+1)%maxsize
队头也是同理为
Front=(front+1)%maxsize
这样就解决了假溢出的问题，但是在循环顺序队列中队满和队空都有rear=front，他们的判断条件是相同的，解决这个问题我们一般是少用数组的一个空间，这个时候
队空的条件为：Rear==front
队满的条件为：（rear+1）%maxsize==front
数据元素个数：（rear-front+maxsize）%maxsize
4.下面就具体实现上面描述的循环顺序队列，如下：
public class CarySeqQueue<T>:ICaryQueue<T>
{
public int Maxsize{get;set;}
public int Front { get; set; }
public int Rear { get; set; }
private T[] data;
public T this[int index]
{
get { return data[index]; }
set { data[index] = value; }
}
public CarySeqQueue(int size)
{
data = new T[size];
Maxsize = size;
Front = Rear = -1;
}
public int GetLength()
{
return (Rear - Front + Maxsize) % Maxsize;
}
public void Clear()
{
Front = Rear = -1;
}
public bool IsEmpty()
{
if (Front == Rear)
return true;
else
return false;
}
public bool IsFull()
{
if ((Rear + 1) % Maxsize == Front)
return true;
else
return false;
}
public void In(T item)
{
if (IsFull())
{
Console.WriteLine("Queue is full");
return;
}
data[++Rear] = item;
}
public T Out()
{
T tmp = default(T);
if (IsEmpty())
{
Console.WriteLine("Queue is empty");
return tmp;
}
tmp = data[++Front];
return tmp;
}
public T GetFront()
{
if (IsEmpty())
{
Console.WriteLine("Queue is empty");
return default(T);
}
return data[Front + 1];
}
}
5.队列还可以使用链式存储，它的操作也单链表的简化。在此就不给出实现了。
6.下面主要来看下.NET Framework中的相关实现。我们只看泛型的版本。在2.0以后提供了Queue<T>类，该类继承自IEnumerable<T>,ICollection和IEnumerable接口。该类的内部实现就是我们上面的顺序循环队列方式。不同的是在.NET Framework中当空间不够时，会根据扩张因子决定新缓冲区的大小。我们主要就分析下这个地方：
下面是入队的方法，在这个方法会根据扩展因子来决定是否增加空间，下面的200是在源代码中定义好的扩张因子
private const int _GrowFactor = 200;
4为最小的增长值：private const int _MinimumGrow = 4;
public void Enqueue(T item)
{
if (this._size == this._array.Length)
{
int capacity = (int) ((this._array.Length * 200) / ((long) 100));
if (capacity < (this._array.Length + 4))
{
capacity = this._array.Length + 4;
}
this.SetCapacity(capacity);
}
this._array[this._tail] = item;
this._tail = (this._tail + 1) % this._array.Length;
this._size++;
this._version++;
}
下面是具体扩容的方法：
private void SetCapacity(int capacity)
{
T[] destinationArray = new T[capacity];
if (this._size > 0)
{
if (this._head < this._tail)
{
Array.Copy(this._array, this._head, destinationArray, 0, this._size);
}
else
{
Array.Copy(this._array, this._head, destinationArray, 0, this._array.Length - this._head);
Array.Copy(this._array, 0, destinationArray, this._array.Length - this._head, this._tail);
}
}
this._array = destinationArray;
this._head = 0;
this._tail = (this._size == capacity) ? 0 : this._size;
this._version++;
}
这个函数中我们主要说下if (this._head < this._tail)这个判断，这个判断的目的就为了确定循环队列中数据元素存储的位置。当tail大于head的时候，数据元素存储在head到tail的位置。当tail小于head的时候存储的数据原色应该是0到tail和head到maxsize的位置。这个只要画个图表示下就很明白了。
本文转自生鱼片博客园博客，原文链接：http://www.cnblogs.com/carysun/archive/2009/10/21/Queue.html，如需转载请自行联系原作者
