资源描述：
《《栈和队列》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章 栈和队列两种特殊的线性表10/6/20211栈和队列3.1栈3.2栈的应用举例3.3栈与递归3.4队列10/6/202123.1栈栈是仅限定在表的一端操作的线性表。它的插入和删除都只能在表的一端进行。定义10/6/20213ADTStack{数据对象：D＝{ai
2、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
3、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStack3.1.1栈的类型定义10/6/20214InitStack(&S)//构造一个空栈S基
4、本操作：DestroyStack(&S)//销毁栈SGetTop(S,&e)//弹出S栈顶元素。Push(&S,e)//向栈内推入元素e10/6/20215栈的表示和实现顺序存储链表存储栈的存储方式栈的性质后进先出10/6/20216栈的顺序存储typedefstruct{charST[101]inttop;}stack;stackS;d4c3b2a1栈顶Top栈底stop10/6/20217栈的顺序存储#defineMaxsize100+1typedefstruct{elemtypeST[Maxsize]inttop;}stack;stackS
5、;d4c3b2a1栈顶top栈底tops10/6/20218栈的顺序存储1.栈空的条件：S.top==04321栈顶Top10/6/202192.栈的压入操作Push(&S,e)//栈S已存在，压入元素e{if(s.top==Maxsize-1)printf("栈满溢出");else{S.top++;S.ST[top]=e;}returnOK;}4321Top10/6/2021102.栈的压入操作Push(&S,e)//栈S已存在，压入元素e{if(s.top==Maxsize-1)printf("栈满溢出");else{S.top++;S.ST
6、[s.top]=e;}returnOK;}4321Top2350Top10/6/2021113.栈的弹出操作pop(&S,e)//栈S已存在，压入元素e{if(s.top==0)printf("栈空下溢");else{e=S.ST[s.top];S.top--;}returnOK;}43212350TopTopTop10/6/202112例题一个栈的入栈序列是12345，则栈的不可能的出栈序列是什么？判断一个顺序栈st(最多元素为maxsize)为栈空he栈满的条件分别是——和——A)st->top!=0B)st->top==0C)st->top
7、!=maxsize-1D)st->top==maxsize-1BD10/6/202113栈的链式存储head211830754256∧进栈出栈读栈顶元素10/6/2021143.2栈的应用举例ClearStack(S)重置S为空栈empty(s)判断栈空push(s，ch)将一个元素e推入栈spop(s)将栈顶元素弹出，且返回其元素gettop(s,e)取栈顶元素10/6/202115例1行编辑程序问题假设“#”为退格符，表示前一个字符无效；“@”为退行符，表示当前行无效；设立一个栈（输入缓冲区），用以接受用户输入的一行字符，然后逐行存入用户数据
8、区。10/6/202116假设从终端接受了这样两行字符：whli##ilr#e（s#*s)outcha@putchar(*s=#++);则实际有效的是下列两行：while(*s)putchar(*s++);10/6/202117假设从终端接受了这样两行字符：whli##ilr#eilhw当'#':Pop(S,e)//弹出当'@':ClearStack(S)//清栈否则入栈10/6/202118假设从终端接受了这样两行字符：whli##ilr#eilhw当'#':Pop(S,e)//弹出当'@':ClearStack(S)//清栈否则入栈10/6/
9、202119假设从终端接受了这样两行字符：whli##ilr#eilhw当'#':Pop(S,e)//弹出当'@':ClearStack(S)//清栈否则入栈10/6/202120while(ch!=EOF&&ch!=''){switch(ch){case'#':Pop(S,e);break;case'@':ClearStack(S);break;//重置S为空栈default:Push(S,ch);break;}ch=getchar();//从终端接收下一个字符}ClearStack(S);//重置S为空栈if(ch!=EOF)ch=get
10、char();while(ch!=EOF){//EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；ilhw10/6/2021
