第3章-栈和队列

东北大学信息学院计算机应用技术研究所杨雷[e-mail]第三章栈和队列通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型3.1栈的类型定义3.2栈类型的实现3.3栈的应用举例3.4队列的类型定义3.5队列类型的实现3.6队列的应用举例3.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端为栈底。基本操作：}ADTStacktopbottom进栈出栈an....a1InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。a1a2an……ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。a1a2ane……Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1……3.2栈类型的实现顺序栈链栈顺序栈的表示与实现base空栈a进栈b进栈atopbasetopbasetopab约定：top指向栈顶元素的下一个位置basee进栈f进栈溢出e出栈edcbatopbasetopbasetopedcbadcba//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。StatusInitStack(SqStack&S){//构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusPush(SqStack&S,SElemTypee){if(S.top-S.base=S.stacksize){//栈满，追加存储空间S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，//用e返回其值，并返回OK；//否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}链栈•栈的链式存储结构称为链栈。栈顶链栈的特点---（1）插入和删除（进栈/退栈）仅在表头位置上（栈顶）进行。（2）不需附加头结点，栈顶指针就是链表（即链栈）的头指针。datalink栈底栈的链接存储结构链栈的结点定义:typedefcharSElemType;typedefstructLinkNode{SElemTypedata;structLinkNode*next;}LinkNode,*LinkStack;LinkStacktop;链栈的进栈算法:StatusPush(LinkStack&top,SElemTypee){LinkStackp;p=(LinkNode*)malloc(sizeof(LinkNode));if(!p)exit(ERROR);p-data=e;p-next=top;top=p;}链栈的出栈算法:StatusPop(LinkStack&top,SElemType&e){if(top==NULL)returnERROR;else{e=top-data;p=top;top=top-next;free(p);returnOK;}}3.3栈的应用举例例一、数制转换例二、括号匹配的检验例三、行编辑程序问题例四、迷宫求解例五、表达式求值例六、实现递归例一、数制转换算法基于原理：N=(Ndivd)×d+Nmodd例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202计算顺序输出顺序voidconversion(){InitStack(S);scanf(%d,N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf(%d,e);}}//conversion回文游戏•顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文字符串：“madamimadam”假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或（（）］)均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例二、括号匹配的检验分析可能出现的不匹配的情况:•到来的右括弧并非是所“期待”的；例如：考虑下列括号序列：[([][])]12345678•到来的是“不速之客”；•直到结束，也没有到来所“期待”的括弧。算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。Statusmatching(string&exp){intstate=1;while(i=Length(exp)&&state){switchofexp[i]{case左括弧:{Push(S,exp[i]);i++;break;}case”)”:{if(NOTStackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);ii++;}else{state=0;}break;}……}if(StackEmpty(S)&&state)returnOK;…...例三、行编辑程序问题如何实现？“每接受一个字符即存入存储器”?并不恰当！设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。合理的作法是：假设从终端接受了这样两行字符：whli##ilr#e（s#*s)outcha@putchar(*s=#++);则实际有效的是下列两行：while(*s)putchar(*s++);while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(S,c);break;case'@':ClearStack(S);break;//重置S为空栈default:Push(S,ch);break;}ch=getchar();//从终端接收下一个字符}ClearStack(S);//重置S为空栈if(ch!=EOF)ch=getchar();while(ch!=EOF){//EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；例四、迷宫求解通常用的是“穷举求解”的方法############$$$####$$$###$$#####################################求迷宫路径算法的基本思想是：•若当前位置“可通”，则纳入路径，继续前进;•若当前位置“不可通”，则后退，换方向继续探索;•若四周“均无通路”，则将当前位置从路径中删除出去。设定当前位置的初值为入口位置；do｛若当前位置可通，则｛将当前位置插入栈顶；若该位置是出口位置，则算法结束；否则切换当前位置的东邻方块为新的当前位置；｝否则{｝｝while(栈不空）；求迷宫中一条从入口到出口的路径的算法……若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则｛删去栈顶位置；//从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；｝若栈空，则表明迷宫没有通路。(1)(2)(4)(5)(6)(7)(3)地图四染色问题R[7][7]12345671234567100001001111101010110101101011011001001100000000012345671223414334231#紫色2#黄色3#红色4#绿色限于二元运算符的表达式定义:表达式::=(操作数)+(运算符)+(操作数)操作数::=简单变量|表达式简单变量::=标识符|无符号整数例五、表达式求值表达式的三种标识方法：设Exp=S1+OP+S2则称OP+S1+S2为前缀表示法S1+OP+S2为中缀表示法S1+S2+OP为后缀表示法例如:Exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）中缀式丢失了括弧信息，致使运算的次序不确定;4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;5)后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。如何从后缀式求值？先找运算符，再找操作数例如：abcde/f+abd/ec-d/e(c-d/e)f如何从原表达式求得后缀式？每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。分析“原表达式”和“后缀式”中的运算符:原表达式:a+bcd/ef后缀式:abc+de/f从原表达式求得后缀式的规律为1)设立运算符栈；2)设表达式的结束符为“#”，予设运算符栈的栈底为“#”；3)若当前字符是操作数，则直接发送给后缀式。4)若当前运算符的优先数高于栈顶运算符，则进栈；5)否则，退出栈顶运算符发送给后缀式；6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为算符间的优先关系＋－×／()#＋－×／(=)#=说明：•左括号‘(’的优先级最高•当θ1=θ2时，令θ1