栈（Stack ）表达式求值队列 （ Queue ）递归的概念递归与.ppt

《栈（Stack ）表达式求值队列 （ Queue ）递归的概念递归与.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、栈(Stack)表达式求值队列(Queue)递归的概念递归与递归工作栈递归与回溯第三章栈和队列只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)栈(Stack)退栈进栈a0an-1an-2topbottomADTStack{//对象:由数据类型为StElemType的元素构成voidPush(stackS,SElemTypex);//进栈intPop(stackS,SElemType&x);//出栈intGetTop(stackS,SElemType&x);//取栈顶voidInitStack(stack&S);

2、//置空栈intStackEmpty(stackS);//判栈空否intStackFull(stackS);//判栈满否}栈的主要操作#defineInitSize100#dafineStackIncreament10typedefcharSElemType;typedefstruct{//顺序栈定义SElemType*base;//栈数组inttop,StackSize;//栈顶指针及栈大小}SeqStack;栈的数组表示—顺序栈123456789StackSizetop(栈空)basevoidInitStack(SeqStack*S){//置空栈S->base=newSElemTyp

3、e[InitSize];if(S->base==NULL)exit(1);S->top=S->base;S->StackSize=InitSize;}intStackEmpty(SeqStack*S){//判断栈是否空？空则返回1，否则返回0returnS->top==S->base;}intStackFull(SeqStack*S){//判断栈是否满？满则返回1，否则返回0returnS->top-S->base==S->StackSize;}voidPush(SeqStack*S,SElemTypex){//若栈满返回0,否则新元素x进栈并返回1if(StackFull(S))Ove

4、rFlow(S);//栈满溢出处理*S->top++=x;//加入新元素}voidOverFlow(SeqStack*S){//栈满处理intnewSize=S->StackSize+StackIncrement;SElemType*temp=newSElemType[newSize];if(temp==NULL)exit(1);//数组分配失败SElemType*src=S->base,obj=temp;for(inti=1;i<=S->StackSize;i++)*obj++=*src++;//向新数组传送数据delete[]S->base;//释放老数组S->base=temp;S

5、->top=obj;S->StackSize=newSize;//新数组大小}top空栈toptoptoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈ctopc退栈b退栈abaa退栈空栈topabdd退栈ctopabctoptopintpop(SeqStack*S,SElemType&x){//若栈空返回0,否则栈顶元素退出到x并返回1if(StackEmpty(S))return0;x=*--S->top;return1;}intGettop(SeqStackS,SElemType&x){//若栈空返回0,否则栈顶元素读到x并返回1if(StackE

6、mpty(S))return0;x=*(S->top-1);return1;}b[0]t[0]t[1]b[1]1maxSizedata双栈共享一个栈空间两个栈共享一个数组空间V[maxSize]设立栈顶指针数组t[2]和栈底指针数组b[2]t[i]和b[i]分别指示第i个栈的栈顶与栈底初始t[0]=b[0]=0,t[1]=b[1]=maxSize+1栈满条件：t[0]+1==t[1]//栈顶指针相遇栈空条件：t[0]=b[0]或t[1]=b[1]//栈顶指针退到栈底intpush(DualStack&DS,SElemTypex,inti){if(DS.t[0]+1==DS.t[1])re

7、turn0;if(i==0)DS.t[0]++;elseDS.t[1]--;DS.base[DS.t[i]]=x;return1;}intPop(DualStack&DS,SElemType&x,inti){if(DS.t[i]==DS.b[i])return0;x=DS.base[DS.t[i]];if(i==0)DS.t[0]--;elseDS.t[1]++;return1;}栈的链接表示—链式栈链式栈无栈满问题，空间可扩充插入