鏈式堆疊

鏈式堆疊是一種數據存儲結構，可以通過單鍊表的方式來實現，使用鏈式棧的優點在於它能夠克服用數組實現的順序棧空間利用率不高的特點，但是需要為每個棧元素分配額外的指針空間用來存放指針域。鏈式棧有擁有一個指向棧頂結點的頭指針，但是鏈式棧中沒有哨位結點，而且基本操作也比鏈式棧要簡單。

基本介紹

• 中文名：鏈式堆疊
• 外文名：Link_Stack

鏈式棧的類定義如下

template <class T>

class LStack{private:SLNode<T>* top;//棧頂指針，指向棧頂結點public:LStack(){top==NULL;}//構造函式~LStack{clear();}//析構函式

void clear();//清空棧

bool Push(const&Titem);//向棧頂壓入一個元素

bool Pop(Titem);//從棧頂彈出一個元素

bool Peek(Titem)const;//讀取棧頂元素

int IsEmpty(void)const{return top==NULL;}//檢測棧是否為空

};

鏈式棧的時間複雜度和空間複雜度分析

鏈式棧所需要的空間是在需要的時候隨時創建的，因此，在時間複雜性上，對於針對棧頂的基本操作（壓入，彈出和棧頂元素存取），它的時間複雜度為O（1）。需要說明的是，在堆疊的實際套用中，有時還能對非棧頂指針進行存取，對於這類的操作，鏈式棧需要從頭開始遍歷。在最好情況下，需要存取的是次棧頂元素，時間複雜度為O(1),在最壞情況下，需要存取的是棧底元素，時間複雜度是O（n）,因此，在平均情況下，鏈式棧的時間複雜度是O(n)。