親自教你實(shí)現(xiàn)棧及C#中Stack源碼分析

第親自教你實(shí)現(xiàn)棧及C#中Stack源碼分析棧又名堆棧，是一種操作受限的線性表，僅能在表尾進(jìn)行插入和刪除操作。

它的特點(diǎn)是先進(jìn)后出，就好比我們往桶里面放盤子，放的時候都是從下往上一個一個放（入棧），取的時候只能從上往下一個一個取（出棧），這個比喻并非十分恰當(dāng)，比如拿盤子的時候只是習(xí)慣從上面開始拿，也可以從中間拿，而棧的話是只能操作最上面的元素，這樣比喻只是為了便于了解。

剛開始接觸?？赡軙行┮蓡?，我們已經(jīng)有數(shù)組和鏈表了，為什么還要棧這個操作受限制的數(shù)據(jù)結(jié)構(gòu)呢？數(shù)組和鏈表雖然靈活，但是操作起來也更容易出錯，而棧因?yàn)椴僮魇芟?，在特定場景中使用還是有優(yōu)勢的。

當(dāng)某個數(shù)據(jù)集合只涉及在一端插入和刪除數(shù)據(jù)，并且滿足先進(jìn)后出的特性時，我們就應(yīng)該首選“?！边@種數(shù)據(jù)結(jié)構(gòu)。

棧的實(shí)現(xiàn)方式有兩種，一種是基于數(shù)組實(shí)現(xiàn)的順序棧，另一種是基于鏈表實(shí)現(xiàn)的鏈?zhǔn)綏?。它的主要操作也就兩個，即入棧和出棧，難度并不大。

先了解一下入棧（Push）和出棧（Pop），如下圖

基于數(shù)組實(shí)現(xiàn)，就面臨著數(shù)組大小固定、擴(kuò)容成本大的問題，下面是使用C#實(shí)現(xiàn)出棧和入棧簡單功能代碼。

//基于數(shù)組實(shí)現(xiàn)的順序棧

publicclassArrayStack

privatestring[]items;//數(shù)組

privateintcount;//棧中元素個數(shù)

privateintn;//棧的大小

//初始化數(shù)組，申請一個大小為n的數(shù)組空間

publicArrayStack(intn)

this.items=newstring[n];

this.n=n;

this.count=0;

//入棧操作

publicboolPush(stringitem)

//數(shù)組空間不夠了，直接返回false，入棧失敗。

if(count==n)returnfalse;

//將item放到下標(biāo)為count的位置，并且count加一

items[count]=item;

++count;

returntrue;

//出棧操作

publicstringPop()

//棧為空，則直接返回null

if(count==0)returnnull;

//返回下標(biāo)為count-1的數(shù)組元素，并且棧中元素個數(shù)count減一

stringtmp=items[count-1];

--count;

returntmp;

}

上面代碼有一些很明顯的缺點(diǎn)，比如存儲的數(shù)據(jù)類型固定為string(C#中使用泛型可以很好的解決)，大小固定...這只是簡單的功能演示，后面分析C#中Stack源碼時這些問題都會被化解。

出棧和入棧的時間復(fù)雜度是多少呢？這個很好計算，因?yàn)槌鰲：腿霔６贾簧婕皸ｍ數(shù)脑?，所以是O(1)。

空間復(fù)雜度呢？還是O(1),因?yàn)檫@里只額外使用了count和n兩個臨時變量。

♂空間復(fù)雜度是指除了原本的數(shù)據(jù)存儲空間外，算法運(yùn)行還需要額外的存儲空間。例子中大小為n的數(shù)組是無法省略的，也就是說這n個空間是必須的，對復(fù)雜度不了解的可以點(diǎn)擊查看一文搞定算法復(fù)雜度分析。

話不多說，上代碼

//鏈表實(shí)現(xiàn)棧

publicclassLinkStackT

//棧頂指示器

publicNodeTTop{get;set;}

//棧中結(jié)點(diǎn)的個數(shù)

publicintNCount{get;set;}

//初始化

publicLinkStack()

Top=null;

NCount=0;

//獲取棧的長度

publicintGetLength()

returnNCount;

//判斷棧是否為空

publicboolIsEmpty()

if((Top==null)(0==NCount))

returntrue;

returnfalse;

//入棧

publicvoidPush(Titem)

NodeTp=newNodeT(item);

if(Top==null)

Top=p;

else

p.Next=Top;

Top=p;

NCount++;

//出棧

publicTPop()

if(IsEmpty())

returndefault(T);

NodeTp=Top;

Top=Top.Next;

--NCount;

returnp.Data;

//結(jié)點(diǎn)定義

publicclassNodeT

publicTData;

publicNodeTNext;

publicNode(Titem)

Data=item;

}

時間復(fù)雜度和空間復(fù)雜度均為O(1).

C#中Stack源碼分析

前面我們已經(jīng)知道了順序棧和鏈?zhǔn)綏５膬?yōu)缺點(diǎn)，那么C#語言中自帶的Stack是基于什么實(shí)現(xiàn)的呢？

答案是順序棧。Stack是一個泛型類，里面定義了一個泛型數(shù)組用以存儲數(shù)據(jù)

privateT[]_array;

既然是一個順序棧，為什么在使用的過程中什么不需要初始化數(shù)組大小，也不用擔(dān)心擴(kuò)容問題呢？

當(dāng)我們實(shí)例化Stack的時候，會調(diào)用它的構(gòu)造函數(shù)，初始化數(shù)組大小為0.

publicStack()

_array=_emptyArray;

_size=0;

_version=0;

}

向數(shù)組中添加元素時，會檢測數(shù)組是否還有空閑容量，如果超出數(shù)組大小，將進(jìn)行擴(kuò)容

publicvoidPush(Titem)

if(_size==_array.Length)

T[]array=newT[(_array.Length==0)4:(2*_array.Length)];

Array.Copy(_array,0,array,0,_size);

_array=array;

_array[_size++]=item;

_version++;

}