数据结构中的栈是什么
举一个简单的例子：在往箱子里面放衣物的时候，放在最上面的衣物总是我们最后放上去的；而当我们从箱子里取出衣物的时候，总是最先拿出上面的。这就是现实生活中的栈。
准确的讲，栈就是一种可以实现“先进后出(或者叫后进先出)”的存储结构。
学过数据结构的人都知道：栈可以用两种方式来实现，一种方法是用数组实现栈，这种栈成为静态栈；另外一种方法是用链表实现栈，这种栈叫做动态栈。
栈中通常存放着程序的局部变量等。栈通常有出栈和入栈操作。
栈的结构
空栈的结构：
存有结点的栈结构：
栈的实现
下面是用C实现的一个栈结构的源码及详细注释：
#includestdio.h#includestdlib.h#includemalloc.h//定义结点结构体typedefstructNode{intdata;//内容structNode*pNext;//指向下一结点的指针}NODE,*PNODE;//NODE等价于structNode,PNODE等价于structNode*//定义栈的结构体typedefstructStack{PNODEpTop;//栈顶结点PNODEpBottom;//栈底结点}STACK,*PSTACK;//STACK等价于structStack,PSTACK等价于structStack*//函数声明voidinitStack(PSTACKpStack);//对栈进行初始化的函数voidpushStack(PSTACKpStack,intval);//入栈的函数boolpopStack(PSTACKpStack,int*pVal);//出栈的函数，*pVal用来保存出栈的元素内容voidtraverseStack(PSTACKpStack);//遍历栈的函数boolisEmpty(PSTACKpStack);//判断栈是否为空的函数voidclearStack(PSTACKpStack);//清空栈的函数intmain(void){STACKstack;//定义一个栈变量,STACK等价于structStackintval;//用来保存出栈的内容initStack(stack);//调用栈的初始化函数pushStack(stack,10);//调用入栈的函数pushStack(stack,20);pushStack(stack,30);pushStack(stack,50);traverseStack(stack);//调用遍历栈的函数//调用出栈的函数if(popStack(stack,val))printf(出栈成功，出栈的元素值为：%d\n,val);elseprintf(出栈失败!);//调用清空栈的函数clearStack(stack);traverseStack(stack);//调用遍历栈的函数system(pause);return0;}voidinitStack(PSTACKpStack){//创建一个空结点，让pTop指向它pStack-pTop=(PNODE)malloc(sizeof(NODE));if(NULL!=pStack-pTop){//将pBottom也指向空节点pStack-pBottom=pStack-pTop;//清空空结点的指针域pStack-pTop-pNext=NULL;
}else//如果内存分配失败{printf(内存分配失败!程序退出!\n);exit(-1);}return;}voidpushStack(PSTACKpStack,intval){//动态创建一个新结点PNODEpNew=(PNODE)malloc(sizeof(NODE));//设置新结点的数据域的值pNew-data=val;//将新结点的指针域指向之前建的空节点pNew-pNext=pStack-pTop;//pStack-pTop不能换成pStack-pBottom//pTop指向新的结点pStack-pTop=pNew;return;}boolpopStack(PSTACKpStack,int*pVal){if(isEmpty(pStack)){returnfalse;}else{//先保存栈顶元素的地址，然后将pTop指向下一元素,最后释放之前栈顶元素的内存PNODErNode=pStack-pTop;*pVal=rNode-data;pStack-pTop=rNode-pNext;free(rNode);rNode=NULL;returntrue;}
}voidtraverseStack(PSTACKpStack){//将栈顶赋给一个临时结点,因为在遍历栈的时候不能销毁栈PNODEpNode=pStack-pTop;//循环遍历栈,直到栈底while(pStack-pBottom!=pNode){printf(%d,pNode-data);pNode=pNode-pNext;}printf(\n);return;}boolisEmpty(PSTACKpStack){if(pStack-pTop==pStack-pBottom)returntrue;elsereturnfalse;}voidclearStack(PSTACKpStack){//栈为空，则退出该函数if(isEmpty(pStack)){return;}else{//两个结点指针变量用来释放栈中元素的内存PNODEp=pStack-pTop;PNODEq=NULL;//循环释放内存while(p!=pStack-pBottom){q=p-pNext;free(p);p=q;}//将栈顶和栈底指向同一个指针域为空的结点pStack-pTop=pStack-pBottom;return;}}
栈的典型应用
生产消费模型常用栈来实现。生产者生产的东西都放入栈中，然后消费者从栈中依次取出东西，当栈顶和栈底指向都指向首结点时，生产的东西就被消耗光了。
北京白癜风医院北京白癜风医院