這陣子在重溫?cái)?shù)據(jù)結(jié)構(gòu)的時(shí)候,順便用ILSpy看了一些.NET類庫(kù)的實(shí)現(xiàn),發(fā)現(xiàn)一些基本的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方法也是挺有意思的,所以這里拿出來跟大家分享一下。這篇文章討論的是Stack和Queue的泛型實(shí)現(xiàn)。
Stack<T>的實(shí)現(xiàn)
Stack(棧)是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu),其中最核心的兩個(gè)方法分別為Push(入棧)和Pop(出棧)兩個(gè)操作,那么.NET類庫(kù)是如何實(shí)現(xiàn)這種數(shù)據(jù)結(jié)構(gòu)呢?為了降低學(xué)習(xí)成本,這里將根據(jù).NET源碼的實(shí)現(xiàn),結(jié)合其中的核心設(shè)計(jì)思想,得出一個(gè)簡(jiǎn)化版本的實(shí)現(xiàn):
using System;
namespace OriginalCode
{
/// <summary>
/// 基于.NET源碼的簡(jiǎn)化版實(shí)現(xiàn)
/// </summary>
public class Stack<T>
{
private const int _defaultCapacity = 4;
private T[] _array;
private int _size;
public Stack()
{
//默認(rèn)初始化數(shù)組的數(shù)量為空
_array = new T[0];
//初始化數(shù)組的數(shù)量為0
_size = 0;
}
/// <summary>
/// 入棧
/// </summary>
/// <param name="item">入棧的元素</param>
public void Push(T item)
{
if (_size == _array.Length)
{
//數(shù)組存儲(chǔ)已經(jīng)滿了,需重新分配數(shù)組大小
//分配的數(shù)組大小為原來的兩倍
T[] array = new T[_array.Length == 0 ? _defaultCapacity : 2 * _array.Length];
//將原來的數(shù)組Copy到新數(shù)組中
Copy(_array, array);
//_array指向新數(shù)組
_array = array;
}
_array[_size] = item;
_size += 1;
}
/// <summary>
/// 出棧
/// </summary>
/// <returns>出棧的元素</returns>
public T Pop()
{
if (_size == 0)
{
throw new Exception("棧為空,當(dāng)前不能執(zhí)行出棧操作");
}
_size -= 1;
T result = _array[_size];
_array[_size] = default(T);
return result;
}
/// <summary>
/// 將舊數(shù)組賦值到新數(shù)組(這個(gè)方法是一個(gè)模擬實(shí)現(xiàn),實(shí)際情況.NET源碼底層用C++實(shí)現(xiàn)了更高效的復(fù)制)
/// </summary>
/// <param name="oldArray">舊數(shù)組</param>
/// <param name="newArray">新數(shù)組</param>
private void Copy(T[] oldArray, T[] newArray)
{
for (int i = 0; i < oldArray.Length; i++)
{
newArray[i] = oldArray[i];
}
}
}
}
必須明確的一點(diǎn)是Stack<T>的底層是靠T[] _array數(shù)組對(duì)象維系著。首先來看構(gòu)造函數(shù)Stack(),這里做的事情無非就是一些基本的初始化工作,當(dāng)調(diào)用這個(gè)無參構(gòu)造函數(shù)的時(shí)候,會(huì)將_array數(shù)組實(shí)例化為T[0],同時(shí)將一個(gè)_size初始化為0。這個(gè)_size主要是用來表示當(dāng)前棧中存在的元素個(gè)數(shù),同時(shí)也承擔(dān)起類似數(shù)組下標(biāo)的作用,標(biāo)識(shí)下一個(gè)元素入棧的數(shù)組位置。
接下來來看一下Push(T item)函數(shù)的實(shí)現(xiàn)。這里的第一步操作其實(shí)就是執(zhí)行一次判斷,判斷當(dāng)前_array數(shù)組的元素個(gè)數(shù)是否已經(jīng)滿了,假如滿了的話,就要對(duì)數(shù)組進(jìn)行擴(kuò)充。.NET源碼對(duì)于數(shù)組擴(kuò)充的設(shè)計(jì)還是比較巧妙的,當(dāng)_array為空的時(shí)候,默認(rèn)開始分配的數(shù)組個(gè)數(shù)為4,既new T[4],假如要插入的是第5個(gè)元素的時(shí)候,這時(shí)數(shù)組的個(gè)數(shù)不足,就聲明一個(gè)新的T[] array,并將個(gè)數(shù)擴(kuò)充為_array個(gè)數(shù)的2倍,之后再將_array元素一個(gè)個(gè)復(fù)制到新的array中,最后將_array字段指向array,就完成了數(shù)組擴(kuò)充的工作。這一步在前面的代碼中的實(shí)現(xiàn)應(yīng)該是很清晰的,不過需要注意的一點(diǎn)是這里的Copy(_array,array)函數(shù)是我自己的一個(gè)簡(jiǎn)單的實(shí)現(xiàn),跟.NET源碼中的實(shí)現(xiàn)是很不一樣的,.NET源碼是調(diào)用一個(gè)Array.Copy(this._array, 0, array, 0, this._size)的函數(shù),它的底層應(yīng)該是用C++實(shí)現(xiàn)了數(shù)組復(fù)制的更好的優(yōu)化。通過一張圖來看一下數(shù)組擴(kuò)容的過程:
最后來看一下Pop()函數(shù)的實(shí)現(xiàn)。首先先判斷當(dāng)前數(shù)組的個(gè)數(shù)是否大于0,小于等于0的話就會(huì)拋出異常。之后就將_size-=1,得到要Pop的對(duì)象在數(shù)組的位置。取出_array[_size]后,就調(diào)用default(T)填充_array[_size]的位置,這樣做的一個(gè)好處是取消對(duì)原來的對(duì)象的引用,是其能夠成為垃圾回收的對(duì)象,更好地減少內(nèi)存的占用??傮w而言Pop()實(shí)現(xiàn)還是比較簡(jiǎn)單的。
從前面我們知道,使用Stack<T>數(shù)據(jù)結(jié)構(gòu),數(shù)組擴(kuò)容應(yīng)該是影響性能最大的一個(gè)因素。默認(rèn)情況下,假如要往棧中插入100個(gè)對(duì)象,意味著數(shù)組就要經(jīng)過4->8->16->32->64->128總共5次的數(shù)組擴(kuò)容,那么有沒有什么辦法可以改善性能呢?答案是有的,.NET源碼Stack<T>對(duì)象除了提供默認(rèn)的無參構(gòu)造函數(shù)外,還提供了一個(gè)Stack(int capacity)的構(gòu)造函數(shù),capacity參數(shù)其實(shí)就是用表示來初始化數(shù)組的個(gè)數(shù),假如我們能預(yù)料到這次插入棧的對(duì)象個(gè)數(shù)的最大值的話(以100為例),就直接這樣調(diào)用new Stack<T>(100),這樣就能減少不必要的數(shù)組擴(kuò)容,從而提高了Stack的使用性能。
Queue<T>的實(shí)現(xiàn)
Queue(隊(duì)列)是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu),其中最核心的兩個(gè)方法是Enqueue(入隊(duì))和Dequeue(出隊(duì))兩個(gè)操作。通過前面的熱身,我們已經(jīng)對(duì)Stack<T>的實(shí)現(xiàn)比較理解了,其實(shí)Queue<T>的實(shí)現(xiàn)也有相似的地方,例如底層的數(shù)據(jù)結(jié)構(gòu)同樣是靠T[] _array數(shù)組對(duì)象維系著,也是使用了2倍數(shù)組擴(kuò)容的方式。不過,由于隊(duì)列具有先進(jìn)先出的特性,它決定了不能像Stack<T>那樣只用一個(gè)_size來維系棧尾的下標(biāo),隊(duì)列必須有一個(gè)隊(duì)頭_head下標(biāo)和一個(gè)隊(duì)尾_tail下標(biāo)來保證先進(jìn)先出的特性??紤]到隊(duì)列的存儲(chǔ)效率,還必須涉及到循環(huán)隊(duì)列的問題,所以Queue<T>的實(shí)現(xiàn)會(huì)比Stack<T>更為復(fù)雜一些,同樣來看一個(gè)簡(jiǎn)化版本的實(shí)現(xiàn):
using System;
namespace OriginalCode
{
/// <summary>
/// 基于.NET源碼的簡(jiǎn)化版實(shí)現(xiàn)
/// </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; //隊(duì)列元素個(gè)數(shù)
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>
/// 入隊(duì)操作
/// </summary>
/// <param name="item">待入隊(duì)元素</param>
public void Enqueue(T item)
{
if (_size == _array.Length)
{
//確定擴(kuò)充的容量大小
int capacity = _array.Length * 2;
if (capacity < _array.Length + _defaultCapacity)
{
//.NET源碼這樣實(shí)現(xiàn)的一些基本猜想
//由于可以通過調(diào)用Queue(int capacity)實(shí)例化隊(duì)列 capacity可以=1 | 2 | 3
//這里做與+4做判斷 應(yīng)該是為了提高基本性能 比如當(dāng)capacity = 1的時(shí)候 *2 = 2 這樣2很快容易有下一次擴(kuò)充
//不過其實(shí)感覺效果并不大 有點(diǎn)設(shè)計(jì)過度的嫌疑
capacity = _array.Length + _defaultCapacity;
}
//實(shí)例化一個(gè)容量更大的數(shù)組
T[] array = new T[capacity];
if (_size > 0)
{
//當(dāng)需要重新分配數(shù)組內(nèi)存的時(shí)候 根據(jù)循環(huán)隊(duì)列的特性 這時(shí)的_head一定等于_tail
//從舊數(shù)組_array[_head]到_array[_size-1] 復(fù)制到 新數(shù)組array[0]...[_size - _head - 1]
ArrayCopy(_array, array, 0, _head, _size - _head);
//從舊數(shù)組_array[0]到_array[_head-1] 復(fù)制到 新數(shù)組array[_size - _head]...[_size - 1]
ArrayCopy(_array, array, _size - _head, 0, _head);
}
_array = array; //將舊數(shù)組指向新數(shù)組
_head = 0; //重新將頭位置定格為0
_tail = _size; //重新將尾位置定格為_size
}
_array[_tail] = item;
_tail = (_tail + 1) % _array.Length;
_size += 1;
}
/// <summary>
/// 出隊(duì)操作
/// </summary>
/// <returns>出隊(duì)元素</returns>
public T Dequeue()
{
if (_size == 0)
{
throw new Exception("當(dāng)前隊(duì)列為空 不能執(zhí)行出隊(duì)操作");
}
T result = _array[_head];
_array[_head] = default(T);
_head = (_head + 1) % _array.Length;
_size -= 1;
return result;
}
/// <summary>
/// 將舊數(shù)組的項(xiàng)復(fù)制到新數(shù)組(這個(gè)方法是一個(gè)模擬實(shí)現(xiàn),實(shí)際情況.NET源碼底層用C++實(shí)現(xiàn)了更高效的復(fù)制)
/// </summary>
/// <param name="oldArray">舊數(shù)組</param>
/// <param name="newArray">新數(shù)組</param>
/// <param name="newArrayBeginIndex">新數(shù)組開始項(xiàng)下標(biāo)</param>
/// <param name="oldArrayBeginIndex">舊數(shù)組開始項(xiàng)下標(biāo)</param>
/// <param name="copyCount">復(fù)制個(gè)數(shù)</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];
}
}
}
}
首先通過下面的圖來看一下數(shù)組容量足夠的時(shí)候,循環(huán)隊(duì)列的執(zhí)行過程:
基于上面這張圖的執(zhí)行過程,來看一下Dequeue函數(shù)的實(shí)現(xiàn)。第一步判斷的是_size是否為0,是的話就拋出異常。如果當(dāng)前入隊(duì)個(gè)數(shù)大于0,則獲取_array[_head]元素作為出隊(duì)元素,之后就調(diào)用default(T)填充_array[_head]的位置。由于是一個(gè)循環(huán)隊(duì)列的設(shè)計(jì),所以不能簡(jiǎn)單地將_head+=1,而必須這樣_head=(_head+1)%_array.Length,如上圖所示,_head有可能指向下標(biāo)為3的位置,假如這時(shí)直接_head += 1變?yōu)?的話,就跳出了數(shù)組的小標(biāo)范圍,而_head=(_head+1)%_array.Length變?yōu)?,則指向了數(shù)組最前的位置,實(shí)現(xiàn)了循環(huán)隊(duì)列的功能,更好地利用了內(nèi)存。
接下來看一下Enqueue(T item)函數(shù)的實(shí)現(xiàn)。承接上圖的Queue的狀態(tài),假如現(xiàn)在要執(zhí)行q.Enqueue(“f”)的入隊(duì)操作,但是很明顯數(shù)組_array已經(jīng)滿了,那么要怎么辦呢?其實(shí)原理和Stack的實(shí)現(xiàn)類似,也是要通過數(shù)組擴(kuò)容的方式,不過比Stack的數(shù)組復(fù)制要復(fù)雜一些。來繼續(xù)看圖:
與Stack<T>一樣,影響Queue<T>性能最大因素是數(shù)組擴(kuò)容以及相應(yīng)的數(shù)組復(fù)制操作,同樣Queue也提供了一個(gè)帶初始化容量的構(gòu)造函數(shù)Queue(int capacity),如果我們能估算到隊(duì)列可能同時(shí)存在元素的最大值,就盡量調(diào)用這個(gè)帶capacity的構(gòu)造函數(shù)。
更多信息請(qǐng)查看IT技術(shù)專欄