.NET源码Queue的实现

Queue（队列）是一种先进先出的数据结构，其中最核心的两个方法是Enqueue（入队）和Dequeue（出队）两个操作。Queue的实现与Stack也有相似的地方，例如底层的数据结构同样是靠T[] _array数组对象维系着，也是使用了2倍数组扩容的方式。不过，由于队列具有先进先出的特性，它决定了不能像Stack那样只用一个_size来维系栈尾的下标，队列必须有一个队头_head下标和一个队尾_tail下标来保证先进先出的特性。考虑到队列的存储效率，还必须涉及到循环队列的问题，所以Queue的实现会比Stack更为复杂一些，同样来看一个简化版本的实现：

using System;

namespace OriginalCode
{
    /// <summary>
    /// 基于.NET源码的简化版实现
    /// </summary>
    public class Queue<T>
    {
        private static T[] EMPTY_ARRAY = new T[0];
        private const int _defaultCapacity = 4;
        private T[] _array;
        private int _head; //头位置
        private int _tail; //尾位置
        private int _size; //队列元素个数

        public Queue()
        {
            _array = EMPTY_ARRAY;
            _head = 0;
            _tail = 0;
            _size = 0;
        }

        public Queue(int capacity)
        {
            _array = new T[capacity];
            _head = 0;
            _tail = 0;
            _size = 0;
        }

        /// <summary>
        /// 入队操作
        /// </summary>
        /// <param name="item">待入队元素</param>
        public void Enqueue(T item)
        {
            if (_size == _array.Length)
            {
                //确定扩充的容量大小
                int capacity = _array.Length * 2;
                if (capacity < _array.Length + _defaultCapacity)
                {
                    //.NET源码这样实现的一些基本猜想
                    //由于可以通过调用Queue(int capacity)实例化队列 capacity可以=1 | 2 | 3
                    //这里做与+4做判断 应该是为了提高基本性能 比如当capacity = 1的时候 *2 = 2 这样2很快容易有下一次扩充
                    //不过其实感觉效果并不大 有点设计过度的嫌疑
                    capacity = _array.Length + _defaultCapacity;
                }

                //实例化一个容量更大的数组
                T[] array = new T[capacity];
                if (_size > 0)
                {
                    //当需要重新分配数组内存的时候 根据循环队列的特性 这时的_head一定等于_tail
                    //从旧数组_array[_head]到_array[_size-1] 复制到 新数组array[0]...[_size - _head - 1]  
                    ArrayCopy(_array, array, 0, _head, _size - _head);
                    //从旧数组_array[0]到_array[_head-1] 复制到 新数组array[_size - _head]...[_size - 1]
                    ArrayCopy(_array, array, _size - _head, 0, _head);
                }

                _array = array; //将旧数组指向新数组
                _head = 0; //重新将头位置定格为0
                _tail = _size; //重新将尾位置定格为_size
            }
            _array[_tail] = item;
            _tail = (_tail + 1) % _array.Length;
            _size += 1;
        }

        /// <summary>
        /// 出队操作
        /// </summary>
        /// <returns>出队元素</returns>
        public T Dequeue()
        {
            if (_size == 0)
            {
                throw new Exception("当前队列为空 不能执行出队操作");
            }
            T result = _array[_head];
            _array[_head] = default(T);
            _head = (_head + 1) % _array.Length;
            _size -= 1;
            return result;
        }

        /// <summary>
        /// 将旧数组的项复制到新数组(这个方法是一个模拟实现，实际情况.NET源码底层用C++实现了更高效的复制)
        /// </summary>
        /// <param name="oldArray">旧数组</param>
        /// <param name="newArray">新数组</param>
        /// <param name="newArrayBeginIndex">新数组开始项下标</param>
        /// <param name="oldArrayBeginIndex">旧数组开始项下标</param>
        /// <param name="copyCount">复制个数</param>
        private void ArrayCopy(T[] oldArray, T[] newArray, int newArrBeginIndex, int oldArrBeginIndex, int copyCount)
        {
            for (int i = oldArrBeginIndex, j = newArrBeginIndex; i < oldArrBeginIndex + copyCount; i++,j++)
            {
                newArray[j] = oldArray[i];
            }
        }
    }
}

首先通过下面的图来看一下数组容量足够的时候，循环队列的执行过程：

基于上面这张图的执行过程，来看一下Dequeue函数的实现。第一步判断的是_size是否为0，是的话就抛出异常。如果当前入队个数大于0，则获取_array[_head]元素作为出队元素，之后就调用default(T)填充_array[_head]的位置。由于是一个循环队列的设计，所以不能简单地将_head+=1，而必须这样_head=(_head+1)%_array.Length，如上图所示，_head有可能指向下标为3的位置，假如这时直接_head += 1变为4的话，就跳出了数组的小标范围，而_head=(_head+1)%_array.Length变为0，则指向了数组最前的位置，实现了循环队列的功能，更好地利用了内存。

接下来看一下Enqueue(T item)函数的实现。承接上图的Queue的状态，假如现在要执行q.Enqueue(“f”)的入队操作，但是很明显数组_array已经满了，那么要怎么办呢？其实原理和Stack的实现类似，也是要通过数组扩容的方式，不过比Stack的数组复制要复杂一些。来继续看图：

与Stack一样，影响Queue性能最大因素是数组扩容以及相应的数组复制操作，同样Queue也提供了一个带初始化容量的构造函数Queue(int capacity)，如果我们能估算到队列可能同时存在元素的最大值，就尽量调用这个带capacity的构造函数。