文档介绍：第三章栈与队列数据结构电子教案郇矢宇1栈队列栈的应用:表达式求值栈的应用:递归队列的应用第三章栈与队列2只允许在一端插入和删除的线性表允许插入和删除 的一端称为栈顶 (top),另一端称 为栈底(bottom)特点 后进先出(LIFO)栈(Stack)退栈进栈a0an-1an-2topbottom3栈的数组存储表示—顺序栈0123456789maxSize-1top(栈空)elements4top空栈toptoptoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈c5topc退栈b退栈abaa退栈空栈topabdd退栈ctopabctoptop6建立一个容量为m的空栈:#include“”Voidinit-stack(s,m,top)ET*s;intm,*top;{s=malloc(m*sizeof(ET));*top=0;return;}7PROCEDUREPUSH(S,m,top,x)//若栈不满,则将元素x插入该栈栈顶,否则溢出处理 if(top=m)then{Stackoverflow;RUTURN} //栈满 top=top+1; //栈顶指针先加1,再进栈S(top)=x;RETURNPROCEDUREPOP(S,m,top,y)//退出栈顶元素并返回栈顶元素的值 if(top=0)then{Stackunderflow;RETURN} y=S(top); top=top-1;//栈顶指针退1returntrue; //退栈成功};8PROCEDURETOP(S,m,top,y)//若栈不空则返回该栈栈顶元素的地址 if(top=0)then{“Stackempty”;RETURN} y=S(top);return;9栈的链接存储表示—链式栈链式栈无栈满问题,空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作top10