背景
如果基于数组实现队列，常见的选择是采用 RingBuffer，否则就需要移动数组元素。
RingBuffer
很容易看出 RingBuffer 的思想，这里就不赘述了。
您可以思考一个问题：图中表示的场景是一个空队列？还是一个满队列？答案是：单单维护 _header 和 _tail 还不足以判断，必须维护一个 _count 计数。
ArrayQueue
代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks; namespace DataStuctureStudy.Queues
{
public class ArrayQueue<T>
{
private readonly int _maxSize;
private readonly T[] _items;
private int _count = ;
private int _header = ;
private int _tail; public ArrayQueue(int size)
{
_maxSize = size;
_items = new T[size];
_tail = _maxSize - ;
} public void EnQueue(T item)
{
if (this.IsFull())
{
throw new InvalidOperationException("队列已满");
} if (_tail == _maxSize - )
{
_tail = -;
} _items[++_tail] = item; _count++;
} public T DeQueue()
{
if (this.IsEmpty())
{
throw new InvalidOperationException("队列已空");
} T item = _items[_header++]; if (_header == _maxSize)
{
_header = ;
} _count--; return item;
} public T Peek()
{
if (this.IsEmpty())
{
throw new InvalidOperationException("队列已空");
} return _items[_header];
} public bool IsFull()
{
return _count == _maxSize;
} public bool IsEmpty()
{
return _count == ;
}
}
}
测试
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks; namespace DataStuctureStudy
{
class Program
{
static void Main(string[] args)
{
var queue = new Queues.ArrayQueue<int>(); queue.EnQueue();
queue.EnQueue();
queue.EnQueue();
queue.EnQueue();
queue.EnQueue();
while (!queue.IsEmpty())
{
Console.WriteLine(queue.DeQueue());
} queue.EnQueue();
queue.EnQueue();
queue.EnQueue();
queue.EnQueue();
queue.EnQueue();
while (!queue.IsEmpty())
{
Console.WriteLine(queue.DeQueue());
}
}
}
}
备注
真正的基于数组的队列还需要考虑扩容，一般的策略是：成本的扩容。