这阵子在重温数据结构的时候，顺便用ILSpy看了一些.NET类库的实现，发现一些基本的数据结构的实现方法也是挺有意思的，所以这里拿出来跟大家分享一下。这篇文章讨论的是Stack和Queue的泛型实现。
Stack<T>的实现
Stack（栈）是一种后进先出的数据结构，其中最核心的两个方法分别为Push（入栈）和Pop（出栈）两个操作，那么.NET类库是如何实现这种数据结构呢？为了降低学习成本，这里将根据.NET源码的实现，结合其中的核心设计思想，得出一个简化版本的实现：
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]; } } } } |
