棧（C實現(xiàn)）“>數(shù)據(jù)結(jié)構(gòu)->棧（C實現(xiàn)）

　　舉一個簡單的例子：在往箱子里面放衣物的時候，放在最上面的衣物總是我們最后放上去的；而當(dāng)我們從箱子里取出衣物的時候，總是最先拿出上面的。這就是現(xiàn)實生活中的棧。
　　準(zhǔn)確的講，棧就是一種可以實現(xiàn)“先進(jìn)后出(或者叫后進(jìn)先出)”的存儲結(jié)構(gòu)。
　　學(xué)過數(shù)據(jù)結(jié)構(gòu)的人都知道：棧可以用兩種方式來實現(xiàn)，一種方法是用數(shù)組實現(xiàn)棧，這種棧成為靜態(tài)棧；另外一種方法是用鏈表實現(xiàn)棧，這種棧叫做動態(tài)棧。
　　棧中通常存放著程序的局部變量等。棧通常有出棧和入棧操作。
　　棧的結(jié)構(gòu)
　　空棧的結(jié)構(gòu)：【其實就是棧頂和棧頂都指向一個無用的頭結(jié)點(diǎn)】
　　存有結(jié)點(diǎn)的棧結(jié)構(gòu)：【棧頂指針指向棧頂結(jié)點(diǎn)，棧底指針指向頭結(jié)點(diǎn)】
　　棧的實現(xiàn)
　　下面是用C實現(xiàn)的一個鏈棧結(jié)構(gòu)的源碼及詳細(xì)注釋：
　　#include
　　#include
　　#include
　　//定義結(jié)點(diǎn)結(jié)構(gòu)體
　　typedef struct Node
　　{
　　intdata; //內(nèi)容
　　struct Node * pNext; //指向下一結(jié)點(diǎn)的指針
　　} NODE, * PNODE; //NODE等價于struct Node, PNODE等價于struct Node *
　　//定義棧的結(jié)構(gòu)體
　　typedef struct Stack
　　{
　　PNODE pTop; //棧頂結(jié)點(diǎn)
　　PNODE pBottom; //棧底結(jié)點(diǎn)
　　} STACK, * PSTACK; //STACK等價于struct Stack, PSTACK等價于struct Stack *
　　//函數(shù)聲明
　　void initStack(PSTACK pStack); //對棧進(jìn)行初始化的函數(shù)
　　void pushStack(PSTACK pStack, int val); //入棧的函數(shù)
　　bool popStack(PSTACK pStack, int * pVal);//出棧的函數(shù)，*pVal用來保存出棧的元素內(nèi)容
　　void traverseStack(PSTACK pStack); //遍歷棧的函數(shù)
　　bool isEmpty(PSTACK pStack); //判斷棧是否為空的函數(shù)
　　void clearStack(PSTACK pStack); //清空棧的函數(shù)

//棧調(diào)用示例
　　int main(void)
　　{
　　STACK stack; //定義一個棧變量,STACK等價于struct Stack
　　int val; //用來保存出棧的內(nèi)容
　　initStack(&stack); //調(diào)用棧的初始化函數(shù)
　　pushStack(&stack, 10); //調(diào)用入棧的函數(shù)
　　pushStack(&stack, 20);
　　pushStack(&stack, 30);
　　pushStack(&stack, 50);
　　traverseStack(&stack); //調(diào)用遍歷棧的函數(shù)
　　//調(diào)用出棧的函數(shù)
　　if(popStack(&stack, &val))
　　printf("出棧成功，出棧的元素值為：%d", val);
　　else
　　printf(" 出棧失敗!");
　　//調(diào)用清空棧的函數(shù)
　　clearStack(&stack);
　　traverseStack(&stack); //調(diào)用遍歷棧的函數(shù)
　　system("pause");
　　return 0;
　　}

//操作函數(shù)的實現(xiàn)
　　void initStack(PSTACK pStack)
　　{
　　//創(chuàng)建一個空結(jié)點(diǎn)，讓pTop指向它
　　pStack->pTop = (PN ODE)malloc(sizeof(NODE));
　　if(NULL != pStack->pTop)
　　{
　　//將pBottom也指向空節(jié)點(diǎn)
　　pStack->pBottom = pStack->pTop;
　　//清空空結(jié)點(diǎn)的指針域
　　pStack->pTop->pNext = NULL;
　　}
　　else //如果內(nèi)存分配失敗
　　{
　　printf("內(nèi)存分配失敗!程序退出!");
　　exit(-1);
　　}
　　return;
　　}
　　void pushStack(PSTACK pStack, int val)
　　{
　　//動態(tài)創(chuàng)建一個新結(jié)點(diǎn)
　　PNODE pNew = (PNODE)malloc(sizeof(NODE));
　　//設(shè)置新結(jié)點(diǎn)的數(shù)據(jù)域的值
　　pNew->data= val;
　　//將新結(jié)點(diǎn)的指針域指向之前建的空節(jié)點(diǎn)
　　pNew->pNext = pStack->pTop; //pStack->pTop不能換成pStack->pBottom
　　//pTop指向新的結(jié)點(diǎn)
　　pStack->pTop = pNew;
　　return;
　　}
　　bool popStack(PSTACK pStack, int * pVal)
　　{
　　if(isEmpty(pStack))
　　{
　　return false;
　　}
　　else
　　{
　　//先保存棧頂元素的地址，然后將pTop指向下一元素,最后釋放之前棧頂元素的內(nèi)存
　　PNODE rNode = pStack->pTop;
　　*pVal = rNode->data;
　　pStack->pTop = rNode->pNext;
　　free(rNode);
　　rNode = NULL;
　　return true;
　　}
　　}
　　void traverseStack(PSTACK pStack)
　　{
　　//將棧頂賦給一個臨時結(jié)點(diǎn),因為在遍歷棧的時候不能銷毀棧
　　PNODE pNode = pStack->pTop;
　　//循環(huán)遍歷棧,直到棧底
　　while(pStack->pBottom != pNode )
　　{
　　printf("%d ", pNode->data);
　　pNode = pNode->pNext;
　　}
　　printf("");
　　return;
　　}
　　bool isEmpty(PSTACK pStack)
　　{
　　if(pStack->pTop == pStack->pBottom)
　　return true;
　　else
　　return false;
　　}
　　void clearStack(PSTACK pStack)
　　{ //棧為空，則退出該函數(shù)
　　if(isEmpty(pStack))
　　{
　　return;
　　}
　　else
　　{
　　//兩個結(jié)點(diǎn)指針變量用來釋放棧中元素的內(nèi)存
　　PNODE p = pStack->pTop;
　　PNODE q = NULL;
　　//循環(huán)釋放內(nèi)存
　　while(p != pStack->pBottom)
　　{
　　q = p->pNext;
　　free(p);
　　p = q;
　　}
　　//將棧頂和棧底指向同一個指針域為空的結(jié)點(diǎn)
　　pStack->pTop = pStack->pBottom;
　　return;
　　}
　　}
　　棧的典型應(yīng)用
　　生產(chǎn)消費(fèi)模型常用棧來實現(xiàn)。生產(chǎn)者生產(chǎn)的東西都放入棧中，然后消費(fèi)者從棧中依次取出東西，當(dāng)棧頂和棧底指向都指向首結(jié)點(diǎn)時，生產(chǎn)的東西就被消耗光了。