.NET源码Stack<T>和Queue<T>的实现

using System;

namespace OriginalCode
{
    /// <summary>
    /// 基于.NET源码的简化版实现
    /// </summary>
    public class Stack<T>
    {
        private const int _defaultCapacity = 4;
        private T[] _array;
        private int _size;

        public Stack()
        {
            //默认初始化数组的数量为空
            _array = new T[0];
            //初始化数组的数量为0
            _size = 0;
        }

        /// <summary>
        /// 入栈
        /// </summary>
        /// <param name="item">入栈的元素</param>
        public void Push(T item)
        {
            if (_size == _array.Length)
            {
                //数组存储已经满了，需重新分配数组大小
                //分配的数组大小为原来的两倍
                T[] array = new T[_array.Length == 0 ? _defaultCapacity : 2 * _array.Length];

                //将原来的数组Copy到新数组中
                Copy(_array, array);

                //_array指向新数组
                _array = array;
            }
            _array[_size] = item;
            _size += 1;
        }

        /// <summary>
        /// 出栈
        /// </summary>
        /// <returns>出栈的元素</returns>
        public T Pop()
        {
            if (_size == 0)
            {
                throw new Exception("栈为空，当前不能执行出栈操作");
            }
            _size -= 1;
            T result = _array[_size];
            _array[_size] = default(T);
            return result;
        }

        /// <summary>
        /// 将旧数组赋值到新数组(这个方法是一个模拟实现，实际情况.NET源码底层用C++实现了更高效的复制)
        /// </summary>
        /// <param name="oldArray">旧数组</param>
        /// <param name="newArray">新数组</param>
        private void Copy(T[] oldArray, T[] newArray)
        {
            for (int i = 0; i < oldArray.Length; i++)
            {
                newArray[i] = oldArray[i];
            }
        }
    }
}

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 newArrayBeginIndex, int oldArrayBeginIndex, int copyCount)
        {
            for (int i = oldArrayBeginIndex, j = newArrayBeginIndex; i < oldArrayBeginIndex + copyCount; i++,j++)
            {
                newArray[j] = oldArray[i];
            }
        }
    }
}