鏈棧-----棧的鏈式存儲結構及其實現

   棧通過數組來實現的方式其實就是采用的是線性表的順序存儲結構，而通過鏈式存儲結構實現的棧操作，簡稱為”鏈棧“。既然是通過鏈式存儲，那么肯定是像單鏈表那樣，是通過一個個結點來構成的。既然是結點，必不可少的，需要一個存放數據的變量，一個存放后繼指針的變量。這是對結點的定義，還有就是棧本身的定義，由于棧是在頂部進行元素的插入或刪除操作，所以，需要一個棧頂指針，因為是鏈棧，還需要一個計數變量，用來存放元素個數的。那么，鏈棧的結構定義如下：

typedef struct StackNode{

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

typedef struct LinkStack{

    LinkStackPtr top;
    int count;
}LinkStack;

   接下來就是元素的插入操作。鏈棧元素的插入跟單鏈表元素的插入非常類似。既然是鏈式存儲，那么很明顯的就是需要動態的分配存儲空間。由于只能在棧頂進行元素的插入操作，所以，在data中存放數據后，后繼指針next中存放的就是top指針中的值，因為top指向的是棧頂。然后，再將棧頂指針指向新的存儲空間。具體實現代碼如下：

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;

}

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

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;

}

最后一段總結，摘自書本：

如果棧的使用過程中元素變化不可預料，有時很小，有時非常大。那么最好是用鏈棧，反之，如果它的變化是在可控范圍內，建議使用順序棧會更好些。