第三章栈和队列

1第三章栈和队列从数据结构的角度看:它们和线性表相同，从数据类型的角度看:它们和线性表不同栈按“后进先出”，队列按“先进先出”§3.1栈的类型定义一、栈的定义及基本运算1．定义：ADTStack{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。2．基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。2操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。}ADTStack二栈的存储表示和基本操作的实现1．顺序栈//顺序栈#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#includecommon.htypedefintSElemType;//accrodingproblemSelemTypetypedefstruct{3SElemType*base;SElemType*top;intstacksize;}SqStack;（1）栈的初始化StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}（2）判空intStackEmpty(SqStackS){if(S.top==S.base)returnTRUE;elsereturnFALSE;}（3）入栈StatusPush(SqStack&S,SElemTypee)4{if(S.top-S.base=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}//Push_SqStack(4)出栈StatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*(--S.top);returnOK;}//Pop_SqStack（5）得到栈顶元素StatusGetTop(SqStackS,SElemType&e){5if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}(6)求元素个数intStackLength(SqStackS){intlen=0;SElemTypee;while(!StackEmpty(S)){Pop_SqStack(S,e);len++;}returnlen;}2．链栈//链栈#includecommon.htypedefintSElemType;typedefstructNode{SElemTypedata;6structNode*next;}StackNode,*LinkStack;(1)初始化LinkStackInitStack(){returnNULL;}//Init_LinkStack（2）判空intStackEmpty(LinkStacktop){if(top==NULL)returnTRUE;elsereturnFALSE;}（3）入栈StatusPush(LinkStack&top,SElemTypee){StackNode*s;s=(StackNode*)malloc(sizeof(StackNode));s-data=e;s-next=top;top=s;returnOK;}7（4）出栈StatusPop(LinkStack&top,SElemType&x){StackNode*p;if(top==NULL)returnERROR;x=top-data;p=top;top=top-next;free(p);returnOK;}（5）得到栈顶元素StatusGetTop(LinkStacks,Selemtype&e){if(s==NULL)returnERROR;e=s-data;returnOK;}§3.2栈的应用举例例1,ABC顺序入栈，出栈的方式有：ABCACBBACBCACBACBA8n个字符顺序入栈，出栈的方式有：nnCn211例2数制转换十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N=(Ndivd)×d+Nmodd(其中：div为整除运算，mod为求余运算）例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。voidconversion(){//对于输入的任意一个非负十进制整数，打印输出9//与其等值的八进制数InitStack(S);//构造空栈scanf(%d,N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf(%d,e);}}//conversion这是利用栈的后进先出特性的最简单的例子。在这个例子中，栈操作的序列是直线式的，即先一味地入栈，然后一味地出栈。也许，有的读者会提出疑问：用数组直接实现不也很简单吗？仔细分析上述算法不难看出，栈的引入简化了程序设计的问题，划分了不同的关注层次，使思考范围缩小了。而用数组不仅掩盖了问题的本质，还要分散精力去考虑数组下标增减等细节问题。例2、括号匹配的检验假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（［］（））或［（［］［］）］等为正确的10格式，［（］）或（［（））或(()])均为不正确的格式。检验括号是否匹配的方法可用期待的急迫程度这个概念来描述。例如考虑下列括号序列：[([][])]12345678intAllBrackets_Test(char*str){SqStacks;char*p,c;InitStack(s);for(p=str;p;p++){if(*p=='('||*p=='['||*p=='{')Push(s,*p);elseif(*p==')'||*p==']'||*p=='}'){if(StackEmpty(s))returnFALSE;Pop(s,c);if(*p==')'&&c!='(')returnFALSE;if(*p==']'&&c!='[')returnFALSE;if(*p=='}'&&c!='{')returnFALSE;}11}if(!StackEmpty(s))returnFALSE;returnTRUE;}例3字符串（回文数）对称问题①intsymmetry(char*str){SqStacks;char*c=str,t;inti=0,j;while(*c++!='\0')i++;j=0;c=str;InitStack(s);while(ji/2){Push(s,*c);c++;j++;}if(i%2!=0)c++;while(*c!='\0'){Pop(s,t);12if(t==*c)c++;elsereturnFALSE;}returnTRUE;}②intPalindrome(char*str){//huiwenzifuchara,*c;LinkStackS;S=InitStack();c=str;while(*c!='\0'){Push(S,*c);c++;}c=str;while(!StackEmpty(S)){Pop(S,a);if(a!=*c)returnFALSE;c++;}13returnTRUE;}//PaLindrome例4、表达式求值限于二元运算符的表达式定义:表达式::=(操作数)+(运算符)+(操作数)操作数::=简单变量|表达式简单变量::=标识符|无符号整数在计算机中，表达式可以有三种不同的标识方法(以运算符所在不同位置命名)设Exp=S1+OP+S2则称OP+S1+S2为表达式的前缀表示法称S1+OP+S2为表达式的中缀表示法称S1+S2+OP为表达式的后缀表示法结论:操作数之间的相对次序不变;运算符的相对次序不同;中缀式丢失了括弧信息，致使运算的次序不确定;前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式;如何从后缀式求值？先找运算符，后找操作数，如何从原表达式求得后缀式？分析“原表达式”和“后缀式”中14的运算符:每个运算符的运算次序要由它之后的一个运算符来定，若当前运算符的优先数小，则暂不进行;否则立即进行。从原表达式求得后缀式的规律为：设立操作数栈;设表达式的结束符为“#”,予设运算符栈的栈底为“#”，若当前字符是操作数，则直接发送给后缀式;若当前运算符的优先数高于栈顶运算符，则进栈;否则，退出栈顶运算符发送给后缀式;“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。算法描述如下：voidtransform(charsuffix[],charexp[]){//从合法的表达式字符串exp求得其相应的后缀式InitStack(S);Push(S,‘#’);p=exp;ch=*p;while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);//直接发送给后缀式else{switch(ch){case‘(‘:Push(S,ch);break;case‘)’:{Pop(S,c);while(c!=‘(‘)15{Pass(Suffix,c);Pop(S,c)}break;}defult:{while(Gettop(S,c)&&(precede(c,ch))){Pass(Suffix,c);Pop(S,c);}if(ch!=‘#’)Push(S,ch);break;}//defult}//switch}//elseif(ch!=‘#’){p++;ch=*p;}}//while}//CrtExptree表达式求值的规则:设立运算符栈和操作数栈;设表达式的结束符为“#”,予设运算符栈的栈底为“#”，若当前字符是操作数，则进操作数栈;若当前运算符的优先数高于栈顶运算符，则进栈;否则，退出栈顶运算符作相应运算;“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。算法描述如下:OperandTypeEvaluateExpression(){//算术表达式求值