#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//定義結(jié)點(diǎn)結(jié)構(gòu)體
typedef struct Node
{
 int data;  //內(nèi)容
 struct Node * pNext; //指向下一結(jié)點(diǎn)的指針
} NODE, * PNODE;  //NODE等價(jià)于struct Node, PNODE等價(jià)于struct Node *
//定義棧的結(jié)構(gòu)體
typedef struct Stack
{
 PNODE pTop;  //棧頂結(jié)點(diǎn)
 PNODE pBottom;  //棧底結(jié)點(diǎn)
} STACK, * PSTACK;  //STACK等價(jià)于struct Stack, PSTACK等價(jià)于struct Stack *
//函數(shù)聲明
void initStack(PSTACK pStack);  //對(duì)棧進(jìn)行初始化的函數(shù)
void pushStack(PSTACK pStack, int val); //入棧的函數(shù)
bool popStack(PSTACK pStack, int * pVal);//出棧的函數(shù)，*pVal用來(lái)保存出棧的元素內(nèi)容
void traverseStack(PSTACK pStack);  //遍歷棧的函數(shù)
bool isEmpty(PSTACK pStack);  //判斷棧是否為空的函數(shù)
void clearStack(PSTACK pStack);  //清空棧的函數(shù)
int main(void)
{
 STACK stack;  //定義一個(gè)棧變量,STACK等價(jià)于struct Stack
 int val;  //用來(lái)保存出棧的內(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\n", val);
 else
 printf(" 出棧失敗!");
 //調(diào)用清空棧的函數(shù)
 clearStack(&stack);
 traverseStack(&stack); //調(diào)用遍歷棧的函數(shù)
 system("pause");
 return 0;
}

void initStack(PSTACK pStack)
{
 //創(chuàng)建一個(gè)空結(jié)點(diǎn)，讓pTop指向它
 pStack->pTop = (PNODE)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)存分配失敗!程序退出!\n");
 exit(-1);
 }
 return;
}

void pushStack(PSTACK pStack, int val)
{
 //動(dòng)態(tài)創(chuàng)建一個(gè)新結(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)
{
 //將棧頂賦給一個(gè)臨時(shí)結(jié)點(diǎn),因?yàn)樵诒闅v棧的時(shí)候不能銷毀棧
 PNODE pNode = pStack->pTop;
 //循環(huán)遍歷棧,直到棧底
 while(pStack->pBottom != pNode )
 {
 printf("%d ", pNode->data);
 pNode = pNode->pNext;
 }
 printf("\n");
 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
 { 
 //兩個(gè)結(jié)點(diǎn)指針變量用來(lái)釋放棧中元素的內(nèi)存
 PNODE p = pStack->pTop;
 PNODE q = NULL;
 //循環(huán)釋放內(nèi)存
 while(p != pStack->pBottom)
 {
  q = p->pNext;
  free(p);
  p = q;
 }
 //將棧頂和棧底指向同一個(gè)指針域?yàn)榭盏慕Y(jié)點(diǎn)
 pStack->pTop = pStack->pBottom;
 return;
 }
}