棧（C實現）“>數據結構->棧（C實現）

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

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

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