堆栈堆栈的应用队列队列的应

《堆栈堆栈的应用队列队列的应》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、堆栈堆栈的应用队列队列的应用第三章堆栈和队列7/2/202113.1栈(Stack)只允许在一端插入和删除的顺序表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)退栈进栈7/2/20212进栈示例7/2/20213退栈示例7/2/20214栈的基本操作1、初始化2、进栈3、退栈4、取栈顶元素5、判栈是否非空6、置栈空7/2/20215栈的顺序存储结构顺序栈的定义typedefintdatatype;#definemaxsize64typedefstruct{datatypedata[maxsize];inttop;}seqstack;7/2

2、/20216栈的基本运算置空栈SETNULL(seqstack*s){s->top＝-1;}判栈空intEMPTY(seqstack*s){if(s->top>=0)returnFALSE;elsereturnTRUE;}7/2/20217进栈seqstack*PUSH(seqstack*s,datatypex){if(s->top==maxsize-1){printf(“overflow”);returnNULL;}else{s->top++;s->data[s->top]＝x;}returns;}7/2/20218退栈datatypePOP(seqstack*s){if(EMP

3、TY(s)){printf(“underflow”);returnNULL;}else{s->top--;return(s->data[s->top+1]);}}7/2/20219取栈顶datatypeTOP(seqstack*s){if(EMPTY(s)){printf(“underflow”);returnNULL;}elsereturn(s->data[s->top]);}7/2/202110两个堆栈共享空间0maxsize-1lefttoprighttop7/2/202111栈的链接表示—链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于

4、多栈操作7/2/202112栈的链接存储结构链栈的结点定义typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linkstack;7/2/202113链栈的进栈算法linkstack*PUSHLSTACK(linkstack*top,datatypex){linkstack*p;p＝malloc(sizeof(linkstack));p->data＝x;p->next＝top;returnp;}7/2/202114链栈的出栈算法linkstack*POPLSTACK(linkstack*top,datat

5、ype*datap){linkstack*p;if(top==NULL){printf(“underflow”);returnNULL;}else{*datap＝top->data;p＝top;top＝top->next;free(p);returntop;}}7/2/202115例：对于一个栈，给出输入项A、B、C，如果输入项序列由ABC组成，试给出所有可能的输出序列。A进A出B进B出C进C出ABCA进A出B进C进C出B出ACBA进B进B出A出C进C出BACA进B进B出C进C出A出BCAA进B进C进C出B出A出CBA不可能产生输出序列CAB7/2/202116栈的应用举例－－文字

6、编辑器seqstacks;EDIT(){charc;SETNULL(&s);c＝getchar();while(c!=‘*’){if(c==‘#’)POP(&s);elseif(c==‘@’)SETNULL(&s);elsePUSH(&s,c);c＝getchar();}}7/2/202117栈的应用－－递归函数intFACT(intn){if(n==1)return(1);elsereturn(n*FACT(n-1));}7/2/202118栈的应用－－表达式计算中缀表达式：A+(B–C/D)×E后缀表达式：ABCD/－E×+（逆波兰表达式）后缀表达式特点1、与相应的中缀表达式中的操

7、作数次序相同2、没有括号7/2/202119后缀表达式的处理过程操作顺序后缀表达式ABCD/－E×+T1←C/DABT1－E×+T2←B–T1AT2E×+T3←T2×EAT3+T4←A+T3T47/2/202120ABCDE＋×－／ABCT1＋×－ABT2＋×AT3＋7/2/202121中缀表达式转换为后缀表达式＋－×／()#＋>><<<>>－>><<<>>×>>>><>>／>>>><>>(<<<<<=)>>>>>>#<<<<<=当前运算符栈顶