栈（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;
　　}
　　}
　　栈的典型应用
　　生产消费模型常用栈来实现。生产者生产的东西都放入栈中，然后消费者从栈中依次取出东西，当栈顶和栈底指向都指向首结点时，生产的东西就被消耗光了。