Chapter 3 Stacks and queues

Chapter3STACKSANDQUEUES3.1TheStackAbstractDataTypeStackAnorderedlistinwhichinsertionsanddeletionsaremadeatoneendcalledthetoponly.Last-In-First-Out(LIFO)StackS=(a0,…,an-1)a0--thebottomelementan-1--thetopelement1234566565StackAbstractDataTypeStructureStackisObject:afiniteorderedlistwithzeroormoreelements.Functions:forallstack∈Stack,item∈element,max_stack_size∈positiveintegerStackCreateS(max_stack_size)::=createanemptystackwhosemaximumsizeismax_stack_sizeBooleanIsFull(stack,max_stack_size)::=if(numberofelementsinstack==max_stack_size)returnTRUEelsereturnFALSEStackPush(stack,item)::=if(IsFull(stack))stackFullelseinsertitemintotopofstackandreturnBooleanIsEmpty(stack)::=if(stack==CreateS(max_stack_size))returnTRUEelsereturnFALSEElementPop(stack)::=if(IsEmpty(stack))returnelseremoveandreturntheitemonthetopofthestackRepresentationandOperationsRepresentationStackCreateS(max_stack_size)::=#defineMAX_STACK_SIZE100/*maximumstacksize*/typedefstruct{intkey;/*otherfields*/}element;elementstack[MAX_STACK_SIZE];inttop=-1;OperationsBooleanIsEmpty(stack)::=top0;BooleanIsFull(stack)::=top=max_stack_size-1;PushtoastackPopfromastack【example】PushtoastackandPopfromastackvoidpush(elementitem){/*addanitemtotheglobalstack*/if(top=MAX_STACK_SIZE-1){stackFull();return;}stack[++top]=item;}elementpop(){/*returnthetopelementfromthestack*/if(top==-1)returnstackEmpty();returnstack[top--];}栈应用1—数制转换问题问题:对于输入的任意十字制表示的整数，将其转换成d进制表示(d=2,8,…)。算法基于原理：N=(Ndivd)*d+Nmodd例如：(1348)10=(2504)8其运算过程如下：NNdiv8Nmod8134816841682102125202voidconversion(){scanf(“%d”,&n);while(n){push(n%8);n=n/8;}while(!isEmpty(s)){e=pop();printf(“%d”,e);}}//conversion栈应用2--3.4EvaluationOfExpression〖Example〗Aninfixexpression:abcdeAprefixexpression:abcdeApostfixexpression:abcdeoperandoperatoroperatorwiththehighestprecedenceReversePolishnotationinfixPostfix2+3*4234*+a*b+5ab*5+(1+2)*712+7*a*b/cab*c/((a/(b-c+d))*(e-a)*cabc-d+/ea-*c*a/b-c+d*e-a*cab/c-de*+ac*-〖Example〗62342=?topGettoken:6(operand)top6Gettoken:2(operand)top2Gettoken:(operator)26=3toptop3topGettoken:3(operand)3topGettoken:(operator)3toptop3=00topGettoken:4(operand)top4Gettoken:2(operand)top2Gettoken:(operator)top2top4=88topGettoken:(operator)top8top0=88topPop:8top8EvaluatingPostfixExpressionProgramDefinition#defineMAX_STACK_SIZE100/*maximumstacksize*/#defineMAX_EXPR_SIZE100/*maxsizeofexpression*/typedefenum{lparen,rparen,plus,minus,times,divide,mod,eos,operand}precedence;intstack[MAX_STACK_SIZE];/*globalstack*/charexpr[MAX_EXPR_SIZE];/*inputstring*/Functiontoevaluateapostfixexpression#defineMAX_STACK_SIZE100/*maximumstacksize*/#defineMAX_EXPR_SIZE100/*maxsizeofexpression*/typedefenum{lparen,rparen,plus,minus,times,divide,mod,eos,operand}precedence;intstack[MAX_STACK_SIZE];/*globalstack*/charexpr[MAX_EXPR_SIZE];/*inputstring*/inteval(void){/*evaluateapostfixexpression*/precedencetoken;charsymbol;/*originalcharacteroftoken*/intop1,op2;/*operands*/intn=0;/*counterfortheexpressionstring*/inttop=1;token=getToken(&symbol,&n);/*getonesymbolandtokentypefromexpr[n]*/Functiontoevaluateapostfixexpressionwhile(token!=eos){/*whileit’snottheendofexpr*/if(token==operand)push(symbol’0’);/*pushthenumberintostack*/else{op2=Pop();/*poptwooperands*/op1=Pop();switch(token){/*performoperationandpushresult*/caseplus:push(op1+op2);break;caseminus:push(op1op2);break;casetimes:push(op1op2);break;casedivide:push(op1/op2);break;casemod:push(op1%op2);}/*endswitch*/}/*endelse*/token=getToken(&symbol,&n);/*getthenexttoken*/}/*endwhile-loop*/returnpop();/*returnresult*/}FunctiontogetatokenfromtheinputstringprecedencegetToken(char*symbol,int*n){/*getthenexttoken,symbolisthecharacterrepresentation,whichisreturned,thetokenisrepresentedbyitsenumeratedvalue,whichisreturnedinthefunctionname*/*symbol=expr[(*n)++];switch(*symbol){case'(':returnlparen;case')':returnrparen;case'+':returnplus;case'-':returnminus;case'/':returndivide;case'*':returntimes;case'%':returnmod;case‘':returneos;default:returnoperand;/*noerrorchecking,defaultisoperand*/}}栈应用3-InfixtoPostfixConversion〖Example〗abcd=?abcdNote:Theorderofoperandsisthesameininfixandpostfix.Operatorswithhigherprecedenceappearbeforethosewithlowerprecedence.Output:topGettoken:a(operand)aGettoken:(plus)topGettoken:b(operand)bGettoken:(times)?topGettoken:c(operand)cGettoken:(minus)?top?toptopGettoken:d(operand)dtopIsn’tthatsimple?Waittillyouseethenextexample...(?〖Example〗a(bc)d=?abcdtopOutput:Gettoken:a(operand)aGettoken:(times)topGettoken:((lparen)(?top(Gettoken:b(operand)bGettoken:(plus)NO?!top+Gettoken:c(operand)cGettoken:)(rparen)toptopGettoken:(divide)?toptopGettoken:d(operand)dtopT(N)=O(N)Solutions:Neverpopa(fromthestackexceptwhenprocessinga).Observethatwhen(isnotinthestack,itsprecedenceisthehighest;butwhenitisinthestack,itsprecedenceisthelowest.Definein-stackprecedenceandincomingprecedenceforsymbols,andeachtimeusethecorrespondingprecedenceforcomparison.Note:a–b–cwillbeconvertedtoab–c–.However,2^2^3()mustbeconvertedt