鏈棧

鏈棧

　　棧的鏈式存儲結構稱為鏈棧

鏈棧的類型定義
　　鏈棧是沒有附加頭結點的運算受限的單鏈表棧頂指針就是鏈表的頭指針

　　鏈棧的類型說明如下
       typedef struct stacknode{
            DataType data
            struct stacknode *next
       }StackNode;
    
       typedef struct{
             StackNode *top;  //棧頂指針
       }LinkStack;
　注意
　　①LinkStack結構類型的定義是為了方便在函數體中修改top指針本身
　　②若要記錄棧中元素個數可將元素個數屬性放在LinkStack類型中定義

鏈棧的基本運算
（） 置棧空
      Void InitStack(LinkStack *S)
      {
             S>top=NULL;
      }
（） 判棧空
      int StackEmpty(LinkStack *S)
      {
            return S>top==NULL;
      }
（） 進棧
      void Push(LinkStack *SDataType x)
      {//將元素x插入鏈棧頭部
            StackNode *p=(StackNode *)malloc(sizeof(StackNode));
            p>data=x;
            p>next=S>top;//將新結點*p插入鏈棧頭部
            S>top=p;
       }
（） 退棧
      DataType Pop(LinkStack *S)
      {
            DataType x;
            StackNode *p=S>top;//保存棧頂指針
            if(StackEmpty(S))
                  Error(Stack underflow);  //下溢
            x=p>data;  //保存棧頂結點數據
            S>top=p>next;  //將棧頂結點從鏈上摘下
            free(p);
            return x;
       }
（） 取棧頂元素
      DataType StackTop(LinkStack *S)
       {
            if(StackEmpty(S))
                 Error(Stack is empty)
             return S>top>data;
        }
  注意
　    鏈棧中的結點是動態分配的所以可以不考慮上溢無須定義StackFull運算

From:http://tw.wingwit.com/Article/program/sjjg/201311/22753.html