本文共 3578 字，大约阅读时间需要 11 分钟。

.NET源码中的栈是基于数组实现的，基本的内部结构定义如下：用一个数组来保存数据。而_emptyArray用于默认构造函数，初始化空栈。

  public class Stack
   
     : IEnumerable
    
     , ICollection, IEnumerable  {    private static T[] _emptyArray = new T[0];    private T[] _array;    private int _size;
    
   

有两种构造方式，指定容量，或从一个集合构造。

指定容量主要是初始化数组的大小。

public Stack(int capacity)    {      if (capacity < 0)        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNumRequired);      this._array = new T[capacity];      this._size = 0;      this._version = 0;    }

从集合构造则是直接用集合的CopyTo()方法直接保存到数组中，注意即使集合为空，也将集合中的空对象push进数组中， 有点不太明白？

public Stack(IEnumerable
   
     collection)    {      if (collection == null)        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);      ICollection
    
      collection1 = collection as ICollection
     
      ;      if (collection1 != null)      {        int count = collection1.Count;        this._array = new T[count];        collection1.CopyTo(this._array, 0);        this._size = count;      }      else      {        this._size = 0;        this._array = new T[4];        foreach (T obj in collection)          this.Push(obj);      }    }
     
    
   

最基本的操作：入栈的实现如下，首先是要将老数组扩容，而扩容的方式是0到4，再依次翻倍，然后将老数据复制进新数组，然后把要插入的数据放进数组的index+1的位置。

注意这里的size和Length，size指的是栈中实际的数据个数，而Length则是数组的长度，所以当数据个数达到长度上限时，需要扩容。

public void Push(T item)    {      if (this._size == this._array.Length)      {        T[] objArray = new T[this._array.Length == 0 ? 4 : 2 * this._array.Length];        Array.Copy((Array) this._array, 0, (Array) objArray, 0, this._size);        this._array = objArray;      }      this._array[this._size++] = item;      ++this._version;    }

出栈的实现如下：得到数组中最外面一个数据，然后将此数据的位置设置置为null或0（default<T>表示引用类型null，值类型为0）

注意并没有减少减少数组容量。

public T Pop()    {      if (this._size == 0)        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack);      ++this._version;      T obj = this._array[--this._size];      this._array[this._size] = default (T);      return obj;    }

而取得栈顶数据并不弹出数据的实现如下：直接返回数组的最外面那个数据。

public T Peek()    {      if (this._size == 0)        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack);      return this._array[this._size - 1];    }

判断某个数据是否在栈中的实现：反向遍历数组。

public bool Contains(T item)    {      int index = this._size;      EqualityComparer
   
     @default = EqualityComparer
    
     .Default;      while (index-- > 0)      {        if ((object) item == null)        {          if ((object) this._array[index] == null)            return true;        }        else if ((object) this._array[index] != null && @default.Equals(this._array[index], item))          return true;      }      return false;    }
    
   

清空栈：清空数组，并将size设置为0

public void Clear()    {      Array.Clear((Array) this._array, 0, this._size);      this._size = 0;      ++this._version;    }

复制到数组的实现：直接Copy即可，因为栈是从外向内存储的，所以还需要逆序。

public void CopyTo(T[] array, int arrayIndex)    {      if (array == null)        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);      if (arrayIndex < 0 || arrayIndex > array.Length)        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);      if (array.Length - arrayIndex < this._size)        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);      Array.Copy((Array) this._array, 0, (Array) array, arrayIndex, this._size);      Array.Reverse((Array) array, arrayIndex, this._size);    }

以上。

转载地址：http://lnlgb.baihongyu.com/