出棧與入棧是棧的最主要操作，當無法預見棧所需大小時，需要采用棧鏈的方式。
一、棧鏈結點
在棧鏈中，不需要像單鏈表一樣需要頭結點。棧鏈的結構如下圖所示
根據該結構，用C語言定義為：
typedef char SElemType
typedef struct StackNode
{
SElemType data;//根據實際需要定義數據類型
struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct LinkStack
{
LinkStackPtr top;//指向棧鏈頂部
int count;//用以判斷是否棧為空，可初始化為0
}LinkStack;
二、進棧操作
能夠進棧的前提是已成功建立棧空間，即成功調用malloc函數。進棧操作的過程如下圖所示。進棧函數所需的參數主要是指向棧頂的指針和入棧內容，因此可定義為：
int Push(LinkStack *pS,SElemType e)
Step1：開辟內存，將需要入棧的元素壓入棧：
LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
s->data = e;
Step2：更改指針
（1）新結點的*next指向原來棧頂：s->next = pS->top;
（2）棧鏈新的top指針指向新建立的結點：pS->top = s;
Step3：更改棧狀態（累計入棧元素個數）
pS->count++;
三、出棧操作
出棧之前需要判斷當前棧的狀態，如果棧元素個數為零，則顯然是空棧，無法進行出棧操作。出棧操作函數同樣需要兩個參數，一是指向棧鏈的指針，二是彈出的棧元素，因此定義為：
int Pop(LinkStackPtr *pS,SElemType *e)//之所以是*e，是為了在函數結束後可以取得該彈出元素
出棧操作過程如下圖所示：
出棧過程：
Step1：獲取彈出元素：*e = pS->top->data;
Step2：top指針指向棧頂：p = pS->top ;pS->top = p->next;//LinkStackPtr p;
Step3：釋放結點：free(p);
Step4：更改棧狀態
pS->count--;
四、測試程序
#include <stdio.h>
#include <stdlib.h>
typedef char SElemType ;
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct LinkStack
{
LinkStackPtr top;
int count;
}LinkStack;
//棧指針初始化
void InitialStack(LinkStack *L)
{
L->top=NULL;
L->count=0;
return;
}
//棧狀態
int StackEmpty(LinkStack *pS)
{
if(!pS->count)//若為空，則返回1
return 1;
else
return 0;//若非空，則返回0；
}
//壓棧操作
int Push(LinkStack *pS,SElemType e)
{
//一般情況下，不存在棧滿情況
LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
s->data = e;
s->next = pS->top;
pS->top=s;
pS->count++;
return 0;
}
//出棧操作
int Pop(LinkStack *pS,SElemType *e)
{
LinkStackPtr p;
if(StackEmpty(pS))
{
printf("棧為空！");
return 0;
}
*e=pS->top->data;
p = pS->top;
pS->top = p->next;
free(p);
pS->count--;
return 0;
}
//打印棧鏈
void PrintStackLink(LinkStack *pS)
{
LinkStackPtr L;
int i;
//i = pS->count;
L = pS->top;
if(pS->count == 0)
{
printf("棧為空！");
return;
}
for(i=0;i<(pS->count);i++)
{
printf("%c\n",L->data);
L = L->next;
}
return ;
}
void main()
{
//測試
char getch;
char outch;
LinkStack myStack;
InitialStack(&myStack);
//壓棧
printf("請輸入壓入棧的數據（char型），輸入#結束");
scanf("%c",&getch);
while(getch!='#')
{
Push(&myStack,getch);
scanf("%c",&getch);
}
printf("棧鏈內容為：\n");
PrintStackLink(&myStack);
//出棧
while(!StackEmpty(&myStack))
{
Pop(&myStack,&outch);
printf("彈出內容為：%c\n",outch);
}
PrintStackLink(&myStack);
while(1);
return ;
}
相關閱讀：
C語言變長數組之剖析 http://www.linuxidc.com/Linux/2013-07/86997.htm
C語言需要注意的問題 http://www.linuxidc.com/Linux/2013-05/84301.htm
C語言位域的使用及其注意點 http://www.linuxidc.com/Linux/2013-07/87027.htm
