這陣子在重溫數據結構的時候，順便用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];
}
}
}
}
必須明確的一點是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];
}
}
}
}
首先通過下面的圖來看一下數組容量足夠的時候，循環隊列的執行過程：
基于上面這張圖的執行過程，來看一下Dequeue函數的實現。第一步判斷的是_size是否為0，是的話就拋出異常。如果當前入隊個數大于0，則獲取_array[_head]元素作為出隊元素，之后就調用default(T)填充_array[_head]的位置。由于是一個循環隊列的設計，所以不能簡單地將_head+=1，而必須這樣_head=(_head+1)%_array.Length，如上圖所示，_head有可能指向下標為3的位置，假如這時直接_head += 1變為4的話，就跳出了數組的小標范圍，而_head=(_head+1)%_array.Length變為0，則指向了數組最前的位置，實現了循環隊列的功能，更好地利用了內存。
接下來看一下Enqueue(T item)函數的實現。承接上圖的Queue的狀態，假如現在要執行q.Enqueue(“f”)的入隊操作，但是很明顯數組_array已經滿了，那么要怎么辦呢？其實原理和Stack的實現類似，也是要通過數組擴容的方式，不過比Stack的數組復制要復雜一些。來繼續看圖：
與Stack<T>一樣，影響Queue<T>性能最大因素是數組擴容以及相應的數組復制操作，同樣Queue也提供了一個帶初始化容量的構造函數Queue(int capacity)，如果我們能估算到隊列可能同時存在元素的最大值，就盡量調用這個帶capacity的構造函數。
更多信息請查看IT技術專欄
版權所有:易賢網
公眾號
事業單位
當前位置：
公考類
招聘類
各類考試