鏈棧-----棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)

   棧通過(guò)數(shù)組來(lái)實(shí)現(xiàn)的方式其實(shí)就是采用的是線性表的順序存儲(chǔ)結(jié)構(gòu)，而通過(guò)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧操作，簡(jiǎn)稱為”鏈?！?。既然是通過(guò)鏈?zhǔn)酱鎯?chǔ)，那么肯定是像單鏈表那樣，是通過(guò)一個(gè)個(gè)結(jié)點(diǎn)來(lái)構(gòu)成的。既然是結(jié)點(diǎn)，必不可少的，需要一個(gè)存放數(shù)據(jù)的變量，一個(gè)存放后繼指針的變量。這是對(duì)結(jié)點(diǎn)的定義，還有就是棧本身的定義，由于棧是在頂部進(jìn)行元素的插入或刪除操作，所以，需要一個(gè)棧頂指針，因?yàn)槭擎湕＃€需要一個(gè)計(jì)數(shù)變量，用來(lái)存放元素個(gè)數(shù)的。那么，鏈棧的結(jié)構(gòu)定義如下：

typedef struct StackNode{

    ElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack{

    LinkStackPtr top;
    int count;
}LinkStack;

   接下來(lái)就是元素的插入操作。鏈棧元素的插入跟單鏈表元素的插入非常類似。既然是鏈?zhǔn)酱鎯?chǔ)，那么很明顯的就是需要?jiǎng)討B(tài)的分配存儲(chǔ)空間。由于只能在棧頂進(jìn)行元素的插入操作，所以，在data中存放數(shù)據(jù)后，后繼指針next中存放的就是top指針中的值，因?yàn)閠op指向的是棧頂。然后，再將棧頂指針指向新的存儲(chǔ)空間。具體實(shí)現(xiàn)代碼如下：

Status Push ( LinkStack *S, SElemType e )
{
    LinkStackPtr s = ( LinkStackPtr ) malloc ( sizeof ( StackNode ) );
    s->data = e;
    s->next = S->top;
    S->top = s;
    S->count++;
    
    return OK;

}

   元素的刪除操作與插入操作非常類似。刪除一個(gè)元素只要將棧頂指針指向它的之前一個(gè)元素就行了，然后釋放刪除元素的空間。代碼如下：

Status Pop ( LinkStack *S, SElemType *e )
{
    LinkStackPtr p;
    if ( StackEmpty ( *s ) )
        return ERROR;
        
    p = S->top;
    *e = S->data;
    S->top = S->top->next;
    free ( p );
    S->count--;
    
    return OK;

}

最后一段總結(jié)，摘自書(shū)本：

如果棧的使用過(guò)程中元素變化不可預(yù)料，有時(shí)很小，有時(shí)非常大。那么最好是用鏈棧，反之，如果它的變化是在可控范圍內(nèi)，建議使用順序棧會(huì)更好些。