鏈式棧

鏈式棧是一種數據存儲結構，可以通過單鍊表的方式來實現，使用鏈式棧的優點在於它能夠克服用數組實現的順序棧空間利用率不高的特點，但是需要為每個棧元素分配額外的指針空間用來存放指針域。

基本介紹

• 中文名：鏈式棧
• 外文名：Chain stack
• 類型：計算機科學
• 學科：跨學科
• 性質：棧
• 特點：數據存儲結構

介紹

棧是只能在某一端插入和刪除的特殊線性表。它按照後進先出的原則存儲數據，先進入的數據被壓入棧底（push），最後的數據在棧頂（top），需要讀數據的時候從棧頂開始彈出數據（top）最後一個數據被第一個讀出來。鏈式棧中的元素以Node的形式存儲，節點Node中存有此節點存於棧中的元素以及指向下個節點的指針。鏈式棧的數據成員只用保存指向棧頂節點的指針 *top_node。

順序棧的實現在於使用了數組這個基本數據結構，數組中的元素在記憶體中的存儲位置是連續的，且編譯器要求我們在編譯期就要確定數組的大小，這樣對記憶體的使用效率並不高，一來無法避免因數組空間用光而引起的溢出問題，二在系統將記憶體分配給數組後，則這些記憶體對於其他任務就不可用；而對於鏈棧而言，使用了鍊表來實現棧，鍊表中的元素存儲在不連續的地址，由於是動態申請記憶體，所以我們可以以非常小的記憶體空間開始，另外當某個項不使用時也可將記憶體返還給系統。

代碼

1、鏈式棧的類型定義

typedef struct node{       datatype data;         /*數據域*/      struct node * next;     /*指針域*/}LinkStack;                 

2、判斷空棧

int StackEmpty(LinkStack *top){       return (top?0:1);}//返回0，則不為空。

3、取棧頂元素

datatype GetTop(LinkStack *top){              if(!top)              {                printf("/n鍊表是空的!");                return 0;                    }              return top->data;}

4、入棧

//入棧LinkStack *Push(LinkStack *top,datatype x){       LinkStack *p;       p=(LinkStack *)malloc(sizeof(LinkStack));//分配空間       p->data=x;         /*設定新結點的值*/       p->next=top;       /*將新元素插入棧中*/       top=p;             /*將新元素設為棧頂*/       return top;}

5、出棧

//出棧LinkStack *Pop(LinkStack *top){       LinkStack *p;       if(!top)       {              printf("/n鏈棧是空的!");              return NULL;       }  //判斷是否為空棧n       p=top;  //指向被刪除的棧頂       top=top->next; //修改棧頂指針       free(p);       return top;}