.NET源码Stack的实现

发表于 |

Stack（栈）是一种后进先出的数据结构，其中最核心的两个方法分别为Push（入栈）和Pop（出栈）两个操作，那么.NET类库是如何实现这种数据结构呢？为了降低学习成本，这里将根据.NET源码的实现，结合其中的核心设计思想，得出一个简化版本的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
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];
            }
        }
    }
}

必须明确的一点是Stack的底层是靠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数据结构，数组扩容应该是影响性能最大的一个因素。默认情况下，假如要往栈中插入100个对象，意味着数组就要经过4->8->16->32->64->128总共5次的数组扩容，那么有没有什么办法可以改善性能呢？答案是有的，.NET源码Stack对象除了提供默认的无参构造函数外，还提供了一个Stack(int capacity)的构造函数，capacity参数其实就是用表示来初始化数组的个数，假如我们能预料到这次插入栈的对象个数的最大值的话（以100为例），就直接这样调用new Stack(100)，这样就能减少不必要的数组扩容，从而提高了Stack的使用性能。