必须明确的一点是Stack<T>的底层是靠T[] _array数组对象维系着。首先来看构造函数Stack()，这里做的事情无非是一些基本的初始化工作，当调用这个无参构造函数的时候，会将_array数组实例化为T[0]，同时将一个_size初始化为0。这个_size主要是用来表示当前栈中存在的元素个数，同时也承担起类似数组下标的作用，标识下一个元素入栈的数组位置。
　　接下来来看一下Push(T item)函数的实现。这里的第一步操作其实是执行一次判断，判断当前_array数组的元素个数是否已经满了，假如满了的话，要对数组进行扩充。.NET源码对于数组扩充的设计还是比较巧妙的，当_array为空的时候，默认开始分配的数组个数为4，既new T[4]，假如要插入的是第5个元素的时候，这时数组的个数不足，声明一个新的T[] array，并将个数扩充为_array个数的2倍，之后再将_array元素一个个复制到新的array中，后将_array字段指向array，完成了数组扩充的工作。这一步在前面的代码中的实现应该是很清晰的，不过需要注意的一点是这里的Copy(_array，array)函数是我自己的一个简单的实现，跟.NET源码中的实现是很不一样的，.NET源码是调用一个Array.Copy(this._array， 0， array， 0， this._size)的函数，它的底层应该是用C++实现了数组复制的更好的优化。通过一张图来看一下数组扩容的过程：

　　后来看一下Pop()函数的实现。首先先判断当前数组的个数是否大于0，小于等于0的话会抛出异常。之后将_size-=1，得到要Pop的对象在数组的位置。取出_array[_size]后，调用default(T)填充_array[_size]的位置，这样做的一个好处是取消对原来的对象的引用，是其能够成为垃圾回收的对象，更好地减少内存的占用。总体而言Pop()实现还是比较简单的。
　　从前面我们知道，使用Stack<T>数据结构，数组扩容应该是影响性能大的一个因素。默认情况下，假如要往栈中插入100个对象，意味着数组要经过4->8->16->32->64->128总共5次的数组扩容，那么有没有什么办法可以改善性能呢？答案是有的，.NET源码Stack<T>对象除了提供默认的无参构造函数外，还提供了一个Stack(int capacity)的构造函数，capacity参数其实是用表示来初始化数组的个数，假如我们能预料到这次插入栈的对象个数的大值的话（以100为例），直接这样调用new Stack<T>(100)，这样能减少不必要的数组扩容，从而提高了Stack的使用性能。
　　Queue<T>的实现
　　Queue（队列）是一种先进先出的数据结构，其中核心的两个方法是Enqueue（入队）和Dequeue（出队）两个操作。通过前面的热身，我们已经对Stack<T>的实现比较理解了，其实Queue<T>的实现也有相似的地方，例如底层的数据结构同样是靠T[] _array数组对象维系着，也是使用了2倍数组扩容的方式。不过，由于队列具有先进先出的特性，它决定了不能像Stack<T>那样只用一个_size来维系栈尾的下标，队列必须有一个队头_head下标和一个队尾_tail下标来保证先进先出的特性。考虑到队列的存储效率，还必须涉及到循环队列的问题，所以Queue<T>的实现会比Stack<T>更为复杂一些，同样来看一个简化版本的实现：
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];
}
}
}
}