1 棧的鏈式表示
棧的鏈式存儲結構稱為鏈棧，是運算受限的單鏈表。其插入和刪除操作只能在表頭位置上進行。因此，鏈棧沒有必要像單鏈表那樣附加頭結點，棧頂指針top就是鏈表的頭指針。圖3-4是棧的鏈式存儲表示形式。
鏈棧的結點類型說明如下：
typedef struct Snode
{ ElemType data ;
struct Snode *next ;
} SNode, *Link_Stack ;
2 鏈棧基本操作的實現
(1) 棧的初始化
SNode *Init_Link_Stack(void)
{ SNode *top ;
top=(SNode *)malloc(sizeof(SNode)) ;
if(top==NULL)
return ERROR;
else
{ top->next=NULL ;
return(top) ;}
}
(2) 壓棧(元素進棧)
Status push(SNode *top , ElemType e)
{ SNode *p ;
p=(SNode *)malloc(sizeof(SNode)) ;
if (!p) return ERROR;
/* 申請新結點失敗，返回錯誤標志 */
p->data=e ;
p->next=top->next ;
top->next=p ; /* 鉤鏈 */
return OK;
} 注意：1、與頭插入法建立鏈表類似
2、此處top結點的數據域不放數據，也可設置成存放數據，程序如何改？
(3) 彈棧(元素出棧)
ElemType pop(SNode *top )
/* 將棧頂元素出棧 */
{ SNode *p ;
ElemType e ;
if (top->next==NULL )
return ERROR ; /* 棧空，返回錯誤標志 */
p=top->next ; e=p->data ; /* 取棧頂元素 */
top->next=p->next ; /* 修改棧頂指針 */
free(p) ;
return OK ;
}
void print(SqStack *S)
{
int c;
cout<<"輸出棧中元素"<<endl;
for( c=S.top--;c>=0;c--)
{
cout<<S.bottom[c]<<endl;
}
}
棧的另一個重要應用是在程序設計語言中實現遞歸調用。 遞歸調用：一個函數(或過程)直接或間接地調用自己本身，簡稱遞歸(Recursive)。 遞歸是程序設計中的一個強有力的工具。因為遞歸函數結構清晰，程序易讀，正確性很容易得到證明。 為了使遞歸調用不至於無終止地進行下去，實際上有效的遞歸調用函數(或過程)應包括兩部分：遞推規則(方法)，終止條件。
系統實現遞歸需要一個系統棧 (遞歸工作棧) ，用於在程序運行時處理函數調用。
系統棧是一塊特殊的存儲區。當一個函數被調用時，系統創建一個工作記錄，稱為棧桢(stack frame)，並將其置於棧頂。
初始時只包括返回地址和指向上一棧的指針。
當該函數調用另一個函數時，該函數的局部變量、參數將加到它的棧桢中。
一個函數運行結束，將從棧中刪除它的棧桢，程序控制返回原調用函數繼續執行下去。
從被調函數返回調用函數的一般步驟
若棧為空，則執行正常返回。
否則，從棧頂彈出一個工作記錄，將“工作記錄”中的參數值、局部變量值賦給相應的變量；。
讀取返回地址，將函數值賦給相應的變量。
轉移到返回地址。
優點
程序非常簡潔而清晰，並且易於分析，可讀性較強。
缺點
費空間：系統實現遞歸需要一個系統棧，用於在程序運行時間處理函數調用。
費時：局部變量、形式參數和返回地址的進棧、出棧以及參數的傳遞需要費時，而且遞歸中的重復計算也很浪費時間。
