搜索
§3栈和队列§3.1栈栈（stack）是一种仅限于在称为栈顶（top）的一端进行插入和删除操作的线性表，另一端则被为栈底（bottom）。不含元素的空表称为空栈。栈的特点：后进先出（LastInFirstOut），简称：LIFO。栈的表示和实现和线性表类似，栈也有两种存储结构。（1）．顺序栈顺序栈即采用的顺序存储结构来表示栈，通常采用数组来实现。采用顺序栈受数组空间的约束，有“溢出”的可能，编程前应作空间估算，若有溢出可能，应作溢出判断及相应的处理。在一个程序中，常常会出现同时使用多个栈的情形。为了不因栈上溢而产生错误中断，必须给每个栈预分一个较大的空间，但这并不容易做到，因为栈实际所用的最大空间很难估计；而且各个栈的实际使用量在使用期间是变化的，往往会有这样的情况，即其中一个栈发生上溢，而另一个栈还是空的。设想，若令多个栈共享空间，则将提高空间的使用效率，并减少发生栈上溢的可能。所以，可以采用两个栈共享空间的方法：假设在程序中需设两个栈，并共享一维数组空间。则利用“栈底位置不变”的特性，可将两个栈的栈底分别设在数组空间的两端，然后各自向中间伸展（如图），仅当两个栈的栈顶相遇时才可能发生上溢。（2）．链栈采用链式存储结构的栈简称链栈。对于链栈，不含产生单个栈溢出的情况，但要记得回收结点空间（dispose（p）），否则会出现整个空间被占满，new（p）过程无法实现（即无法申请新的结点空间）的情况。【练习】回文串识别出栈入栈栈顶栈底ana1a2……栈1栈2栈1底栈1顶栈2顶栈2底输入一字符串，判断它是否为一回文串。所谓回文串是指去掉其中的空格与标点符号等非字母符号后，从前后两个方向读到的串相同，例如：tenanimalsIslaminanet.（我将十只动物装在网里）输入：一字符串输出：Yes或No§3.2队列队列（queue）是所有的插入都在一端进行，而所有的删除都在另一端进行的线性表。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。队列的特点：先进先出（|FirstInFirstOut），简称：FIFO。队列的表示和实现和栈一样，队列也有顺序存储和链式存储两种表示和实现方法。在顺序存储结构中，同样有溢出可能，即元素因队满而无法入队。对于队列来说，可以采用循环队列的技巧，仅当队头与队尾相遇时为队满。【例3.2.1】逐行打印二项展开式(a+b)i的系数：杨辉三角形(Pascal’striangle)要求：采用队列实现！输入：n——层数（n50）25输出：如上图的数字阵列【算法思路】分析第i行元素与第i+1行元素的关系a1a2a3……an出队列出队列队头队尾队头队尾11i=112121551314641415101051516152015616目的是从前一行的数据可以计算下一行的数据从第i行数据计算并存放第i+1行数据从数据结构上，可设计一个足够长的一维数组，以实现上述算法。【练习】根据上述思路分析，用队列的方法完成例3.2.1。【练习】再用二维数组，用其它方法完成例3.2.1。【练习】侦察兵队列有一个侦察班，由11人组成，其中6名是老侦察员，5名是新侦察员。一次执勤要穿越敌人的一道封锁线。根据当时的情况，队伍只能单线纵向排列，且前面第一、二人越过后，第三个人要返回报告情况，该侦察员随后编到队伍的末尾。接着第四、五人越过，第六人报告并排到末尾。依此类推。最后三人一齐顺次过去。越过封锁线后，队伍便形成老、新交替的队形。请问，穿越前队伍该怎样排？要求：采用队列实现！输出：O表示老队员，Y表示新队员【练习】倒水问题[问题描述]有三个分别装有a升水、b升水和c升水的量筒（cba0，且b与a互质）,如果c筒装满水，a与b均为空筒，三个筒相互倒水且不准把水倒往三个筒之外，一个往另一个筒倒水记为一次倒水。问是否能量出d升水(cd0)，若能，请求出最少的倒水次数使它能倒出容量为d的水的方案。[输入格式]数据存放在当前目录下的文本文件“water.in”中。文件中以一行的形式存放四个正整数，分别a、b、c、d的值。[输出格式]答案输出到当前目录下的文本文件“water.out”中。第一次行是最少的倒水次数Q，第二起的Q行是每次例水时量简的水量，依次为a、b、c（输入与输出数据中同一行相邻两个数之间用空格区分。）[输入输出举例]water.in37105water.out10900100010307073037343334046064316361019271109208172028352325（仅有第二组才是最优的一个解。）§3.3栈的应用实例§3.3.1中缀表达式和后缀表达式对于高级语言程序中的表达式，在编译时求解用栈来实现。任何一个表达式是由操作数（常量、常量名、变量名）、运算符（算术、关系和逻辑三种运算符）和界限符（左、右圆括号，结束符）所组成。运算符在两个操作数之间的表达式，如a+b、e*f-d等，称为中缀表达式。求值时，一般会有运算符号的优先权和结合权问题。例如：a+b*c-d，我们知道b*c要先求，但编译器只能从左到有逐一检查，检查到加号时尚无法知道是否可执行，待检查到乘号时，因乘号运算优先级比加号高，所有a+b不可以被执行，待继续基础到减号时，方可执行b*c。而后缀表达式是运算符在两个操作数之后，如ab*，也称为“逆波兰式”。后缀表达式可以顺序计算求值，所以编译程序常把中缀表达式变换成后缀表达式，然后再求值。下表是中缀表达式所对应的后缀表达式：中缀表达式后缀表达式A+B*CB*(D-C)+A40.+(10.-8.)*2.-16./8.ABC*+BDC-*A+40.10.8.-2.*+16.8./-(一)、将中缀表达式转换成后缀表达式在转换过程中为了确定计算次序，要按运算符的优先级进行，各运算符优先级如下表，优先级数大的先执行。运算符^(乘方)*,/+,-优先级321【例3.3.1】将中缀表达式转换成后缀表达式。输入：中缀表达式，如：B*(D-C)+A输出：后缀表达式，如：BDC-*A+【算法思想】设立一个栈来实现中缀表达式变后缀表达式。设中缀表达式在字符数组E中，E的末尾再加‘#’作为结束符，将转成后缀表达式，存于字符串A中。对E中表达式自左向右扫描，遇数直接送到A中，若遇到运算符就考虑进栈，进栈的原则是保持栈顶的运算符优先级最高。即若欲进栈的算符是‘(’或欲进栈的运算符优先级大于栈顶运算符的优先级，则将算符入栈，否则从栈中退出算符送至A中，直至欲进栈的算符优先级大于栈顶算符的优先级，这时才将欲进栈的算符入栈。若遇到‘)’时，将栈中算符退出送入A中，直至退出‘(’为止。若遇表达式结束符‘#’，则依次退出栈中算符送入A中。根据上述算法，将中缀表达式B*(D-C)+A转换成后缀表达式BDC-*A+的过程图3_1所示。【参考程序段】constm=100;varE,A,S:array[1..m]ofchar;{E中为中缀式，A中为后缀式，S为栈}i,j,t:integer;procedurepostexp;begini:=1;j:=1;t:=0;whileE[i]’#’dobegincaseE[i]of‘a’..‘z’,‘A’..‘Z’:beginA[j]:=E[i];j:=j+1;end;‘(’:begint:=t+1;S[t]:=‘(’;end;‘)’:beginwhiles[t]‘(’dobeginA[j]:=s[t];j:=j+1;t:=t-1;end;t:=t-1;end;‘+’,‘-’:beginwhile(t0)and(s[t]‘(’)dobeginA[j]:=S[t];j:=j+1;t:=t-1;end;t:=t+1;s[t]:=E[i];end;‘*’,‘/’:beginwhile(t0)and(S[t]=‘*’orS[t]=‘/’)dobeginA[j]:=S[t];j:=j+1;t:=t-1;end;{while}t:=t+1;S[t]:=E[i];end;扫描E栈S转换至AB*B**(B(*(BD*(-BD-*(-BDC*BDC)+BDC-++BDC-*ABDC-*A#BDC-*A+图3_1end;{case}i:=i+1;end;{while}whilet0dobeginA[j]:=S[t];j:=j+1;t:=t-1;end;A[j]:=‘#’;end;(二)、对后缀表达式求值计算一个后缀表达式的值，在算法上比中缀表达式要简单得多，这是因为后缀表达式有两个优点：表达式无括号，也不需考虑运算符的优先级。【算法思想】对后缀表达式求值要使用一个栈来实现。自左至右扫描后缀表达式，若遇数就入栈，若遇到运算符就从栈中退出两个数进行运算，并把计算结果入栈。如此下去，直至遇到结束符“#”为止。最后栈底元素值为所求得的结果。【练习】将一个中缀表达式转换成后缀表达式，并对后缀表达式求值。输入格式：（输入文件bds.in）第一行：中缀表达式，运算数均为大写字母，运算符含乘方‘^’第二行开始：每行为表达式中字母，及其对应的值，输入顺序按字典排序输出格式：（输入文件bds.out）第一行：该中缀表达式所对应的后缀表达式第二行：该表达式的值输入输出举例：输入：(bds.in)输出：(bds.out)B*(D-C)+A^CA4B10C3D8BDC-*AC^+114§3.3.2地图着色问题对地图着色，可使用“四染色”定理，它是计算机科学中的著名定理之一，可以用不多于四色对地图着色，使相邻的行政区域不重色。应用这个定理的结论，利用回溯算法可对一幅给定的地图染色。作为地图四色的示例如图3_3所示，图中01、02、03、04、05、06、07为行政区编号，1色、2色、3色、4色为各区域的颜色，称为色数。【算法思想】从编号为01的区域开始逐一进行染色，对每个区域用色数1，2，3，4依次进行试探，并尽可能取小色数。若当前所取色数与周围已染色的区域不重色，则把该区的色数入栈，否则依次使用下一色数进行试探。若从1色至4色均与相邻的某区域发生重色，则需退栈回溯，修改栈顶区域的色数。在实现此算法时，可用一个关系矩阵R(1:n,1:n)来描述各区域之间的边界关系。若第i区与第j区相邻（有共同边界），则R[i,j]的值为1，否则为0。图3_3中所示的地图关系矩阵如图3_4所示。为了记下每个区域当前染色结果而设立一个栈S(1:n)，栈的下标值表示区域号，栈中的内容是色数，如S[6]=3表示06区域当前染色的色数是3。【参考程序段】constn=7;{地图中区域数}typeadjar=array[1..n,1..n]of0..1;ads=array[1..n]of1..4;proceduremapcolor(varr:adjr;vars:ads);begins[1]:=1;{01区染1色}i:=2;j:=1;{i为区域号，j为染色号}whileindobeginwhile(j=4)and(in)dobegink:=1;{k指示已染色区域号}while(ki)and(s[k]*R[i,k]j)dobegink:=k+1;{判断相邻区是否已染色}ifkithenj:=j+1{用j+1色继续试探}elsebegin图3_3j123456710111110210000103100110041010110510110106110110070000000Ri图3_4s[i]:=j;i:=i+1;j:=1;end;{与相邻区不重色，染色结果进栈，继续对下一区从1色进行试探}end;ifj.4thenbegini:=i-1;j:=s[i]+1;end;{变更栈顶区域的染色色数}end;end;end;按图3_3所示地图执行上述算法时，栈的变化情况如图3_5所示。7→16→3354→3→444434→2222322→333332222222211111111从关系矩阵R可以看出，当i=6时，无论色数j＝1,2,3,4都产生与相邻区重色问题（因与i=6相邻的区是1，2，4，5区，从栈S可见这四个