栈和队列§3.1 栈栈（stack ）是一种仅限于在称为栈顶（top ）的一端进行插入和删除操作的线性表,另一端则被为栈底（bottom ）.不含元素的空表称为空栈.栈的特点：后进先出（Last In First Out ）,简称：LIFO.栈的表示和实现 和线性表类似,栈也有两种存储结构. （1）．顺序栈顺序栈即采用的顺序存储结构来表示栈,通常采用数组来实现.采用顺序栈受数组空间的约束,有“溢出”的可能,编程前应作空间估算,若有溢出可能,应作溢出判断及相应的处理.在一个程序中,常常会出现同时使用多个栈的情形.为了不因栈上溢而产生错误中断,必须给每个栈预分一个较大的空间,但这并不容易做到,因为栈实际所用的最大空间很难估计；而且各个栈的实际使用量在使用期间是变化的,往往会有这样的情况,即其中一个栈发生上溢,而另一个栈还是空的.设想,若令多个栈共享空间,则将提高空间的使用效率,并减少发生栈上溢的可能.所以,可以采用两个栈共享空间的方法：假设在程序中需设两个栈,并共享一维数组空间.则利用“栈底位置不变”的特性,可将两个栈的栈底分别设在数组空间的两端,然后各自向中间伸展（如图）,仅当两个栈的栈顶相遇时才可能发生上溢.（2）．链栈采用链式存储结构的栈简称链栈.对于链栈,不含产生单个栈溢出的情况,但要记得回收结点空间（dispose （p ））,否则会出现整个空间被占满,new （p ）过程无法实现（即无法申请新的结点空间）的情况.【练习】 回文串识别输入一字符串,判断它是否为一回文串.所谓回文串是指去掉其中的空格与标点符号等非字母符号后,从前后两个方向读到的串相同,例如：ten animals I slam in a net. （我将十只动物装在网里） 输入：一字符串 输出：Yes 或No§3.2 队列队列（queue ）是所有的插入都在一端进行,而所有的删除都在另一端进行的线性表.允许插入的一端称为队尾（rear ）,允许删除的一端称为队头（front ）. 队列的特点：先进先出（|First In First Out ）,简称：FIFO.队列的表示和实现和栈一样,队列也有顺序存储和链式存储两种表示和实现方法.在顺序存储结构中,同样有溢出可能,即元素因队满而无法入队.对于队列来说,可以采用循环队列的技巧,仅当队头与队尾相遇时为队满.【例3.2.1】逐行打印二项展开式 (a + b )i 的系数： 杨辉三角形 (Pascal’s triangle)要求：采用队列实现！输入： n ——层数（n<50）25 输出：如上图的数字阵列 【算法思路】分析第 i 行元素与第 i +1行元素的关系目的是从前一行的数据可以计算下一行的数据 从第 i 行数据计算并存放第 i+1 行数据a 1 a 2 a 3 …… a n 出队列 出队列队头 队尾 队头 队尾 1 1 i = 11 2 1 21 5 5 1 3 1 4 6 4 1 4 1 5 10 10 5 1 5 1 6 15 20 15 6 1 6从数据结构上,可设计一个足够长的一维数组,以实现上述算法.【练习】根据上述思路分析,用队列的方法完成例3.2.1.【练习】再用二维数组,用其它方法完成例3.2.1.【练习】侦察兵队列有一个侦察班,由11人组成,其中6名是老侦察员,5名是新侦察员.一次执勤要穿越敌人的一道封锁线.根据当时的情况,队伍只能单线纵向排列,且前面第一、二人越过后,第三个人要返回报告情况,该侦察员随后编到队伍的末尾.接着第四、五人越过,第六人报告并排到末尾.依此类推.最后三人一齐顺次过去.越过封锁线后,队伍便形成老、新交替的队形.请问,穿越前队伍该怎样排？要求：采用队列实现！输出：O表示老队员,Y表示新队员【练习】倒水问题[问题描述]有三个分别装有a升水、b升水和c升水的量筒（c>b>a>0,且b与a互质）, 如果c筒装满水,a与b均为空筒,三个筒相互倒水且不准把水倒往三个筒之外,一个往另一个筒倒水记为一次倒水.问是否能量出d升水(c>d>0),若能,请求出最少的倒水次数使它能倒出容量为d的水的方案.[输入格式]数据存放在当前目录下的文本文件“water.in”中.文件中以一行的形式存放四个正整数,分别a、b、c、d的值.[输出格式]答案输出到当前目录下的文本文件“water.out”中.第一次行是最少的倒水次数Q,第二起的Q行是每次例水时量简的水量,依次为a、b、c （输入与输出数据中同一行相邻两个数之间用空格区分.）[输入输出举例]water.in3 7 10 5water.out10 90 0 10 0 0 103 0 7 0 7 30 3 7 3 4 33 34 0 4 60 6 4 3 1 63 6 1 0 1 92 7 1 1 0 92 0 8 1 7 20 2 8 3 5 23 2 5（仅有第二组才是最优的一个解.）§3.3 栈的应用实例§3.3.1 中缀表达式和后缀表达式对于高级语言程序中的表达式,在编译时求解用栈来实现.任何一个表达式是由操作数（常量、常量名、变量名）、运算符（算术、关系和逻辑三种运算符）和界限符（左、右圆括号,结束符）所组成.运算符在两个操作数之间的表达式,如a+b、e*f-d等,称为中缀表达式.求值时,一般会有运算符号的优先权和结合权问题.例如：a+b*c-d,我们知道b*c要先求,但编译器只能从左到有逐一检查,检查到加号时尚无法知道是否可执行,待检查到乘号时,因乘号运算优先级比加号高,所有a+b不可以被执行,待继续基础到减号时,方可执行b*c.而后缀表达式是运算符在两个操作数之后,如ab*,也称为“逆波兰式”.后缀表达式可以顺序计算求值,所以编译程序常把中缀表达式变换成后缀表达式,然后再求值.(一)、将中缀表达式转换成后缀表达式在转换过程中为了确定计算次序,要按运算符的优先级进行,各运算符优先级如下表,优先【例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所示.【参考程序段】const m=100;var E , A , S : array [1..m] of char; { E 中为中缀式,A 中为后缀式,S 为栈} i , j , t : integer; procedure postexp; begini:=1; j:=1; t:=0;while E[ i ]<>’#’ do begin case E[ i ] of‘a ’.. ‘z ’, ‘A ’.. ‘Z ’ : beginA[ j ]:=E[ i ]; j:=j+1; end;‘(’ : begin扫描E 栈S 转换至AB * B* * ( B( * ( BD * ( - BD - * ( - BD C * BDC ) + BDC - + + BDC -* A BDC -*A # BDC -*A+ 图3_1t:=t+1; S[ t ]:= ‘(’;end;‘)’ : beginwhile s[ t ]< > ‘(’ do beginA[ j ]:=s[ t ]; j:=j+1; t:=t-1;end;t:=t-1;end;‘+’, ‘-’ : beginwhile (t< >0) and (s[t]< > ‘(’) do beginA[ j ]:=S[ t ]; j:=j+1; t:=t-1;end;t:=t+1; s[ t ]:=E[ i ];end;‘*’, ‘/’ : beginwhile (t< >0) and (S[ t ]= ‘*’ or S[ t ]= ‘/’) do beginA[ j ]:=S[ t ]; j:=j+1; t:=t-1;end; {while}t:=t+1; S[ t ]:=E[ i ];end;end; {case}i:=i+1;end; {while}while t< >0 do beginA[ 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^C A 4 B 10 C 3 D 8B DC - * A C ^ + 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.【参考程序段】const n=7; {地图中区域数}type adjar=array[1..n,1..n] of 0..1; ads=array[1..n] of 1..4;procedure mapcolor (var r:adjr; var s:ads); begins[ 1]:=1; {01区染1色}图 3_3 j1 0 1 1 1 1 1 02 1 0 0 0 0 1 03 1 0 0 1 1 0 04 1 0 1 0 1 1 05 1 0 1 1 0 1 06 1 1 0 1 1 0 07 0 0 0 0 0 0 0R i 图3_4i:=2; j:=1; { i 为区域号,j 为染色号} while i<n do beginwhile ( j< =4 ) and ( i<n ) do begin k:=1; { k 指示已染色区域号}while ( k<i ) and ( s[ k ]*R[ i , k ]<>j ) do begin k:=k+1; { 判断相邻区是否已染色}if k<i then j:=j+1 { 用j+1色继续试探} else begins[ i ]:= j; i:=i+1; j:=1;end; { 与相邻区不重色,染色结果进栈,继续对下一区从1色进行试探} end;if j.> 4 then begini:= i-1; j:=s[ i ]+1;end; { 变更栈顶区域的染色色数} end; end; end;按图3_37→6 → 5 → → 4 → 3 → 2 1从关系矩阵R 可以看出,当i = 6时,无论色数j ＝1 , 2 , 3 , 4都产生与相邻区重色问题 （因与i = 6相邻的区是1,2,4,5区,从栈S 可见这四个区色数分别1,2,3,4,四种色全部用完.6区再用四种色数之一,必然重色）.因此必须变更栈顶色数,而5区当前色数为“4”,也不存在除4以外的可染色色数,则需继续退栈,变更S[ 4 ]:=4,由此S[ 5 ]:=3,然而此时仍然6区与相邻区重色,再次退栈,将S[ 3 ]改为S[ 3 ]:=3时才求得所有地区的染色解.§3.4 栈与递归§3.4.1 递归形式一般有两种——直接递归和间接递归,而栈是实现递归的重要手段. (一)、直接递归——子程序自己调用自己 【例2】 fac (n) = n! = 按上述递归定义形式写出fac(n) 函数如下： function fac(n:integer):integer;1 n=0 n ×fac (n -1) n>1 S 图3_5beginif n=0 then fac:=1 else fac:=n*fac(n-1); end;它的执行流程如下：一般来说,递归子程序在调用本身前应有条件语句控制何时进行递归,何时递归结束.这个条件语句就是递归边界.例如,fac 函数体中的“ if n=0 then fac:=1 ”.(二)、间接递归——子程序A 调用子程序B,子程序B 又调用子程序A 子程序A 和B 组合起来有两种结构形式： 1．B 是A 的局部对象 例： procedure A; procedure B; begin… A; {在B 中调用A}… end begin… B; {在A 中调用B} … end;2．A 和B 是两个地位相同的子程序例： procedure B (形式参数表): forward; {B 的完整说明在后} procedurde A; begin…B (实参表); {在A 中调用B} end;procedure B; {B 的首部缩写,形式参数表不再列出} begin …A; {在B 中调用A}3×fac (2) 2×fac (1) 1×fac (0) fac (0) = 16 A 的子过程B 的过程说明…end;【例题3】求出一个在8×8的棋盘上,放置8个不能互相捕捉的“皇后”的所有布局.显然,一个使“皇后”间不能互相捕捉的合理布局应该是——每列、每行确定有一个“皇后”,且在每条对角线上最多只有一个“皇后”.【数据结构设计】从8×8的棋盘,我们很容易想到用二维数组来存储布局.但是,进一步分析,每行有且仅有一个“皇后”,我们可以仅用一维数组来存储布局.SS[ i ] 表示第i行“皇后”所处的列.这一数据结构的改进,将大大简化编程.【算法思路】从空配置开始,在第1行至第top行为合理配置的基础上,递归调用自己而完成top+1行上的配置,直至第8行配置也是合理时,就找到一个解.因此,top=9是递归边界.在任一行上可能的配置有8种.开始时配置在第1列,以后改变时,顺次选择第2列,第3列,……,直至第8列,当8列配置全不合理或者选中某一列配置时,则退出递归过程,通过恢复步数的形式回溯,直到所有布局为止.要在 ( i , top) 配置“皇后”（S[ top ]:= i）的条件有两个：①第1至top-1行的第i 列不能有“皇后”,即S[j]≠i,1≤j≤top-1；②经 ( i , top) 的两条对角线上不能有“皇后”,即： | S[ j ]-i | ≠ | j -top |,1≤j≤top-1；【参考程序】program queen;vartotal : integer; {布局数}s : array[1..8] of 1..8; {布局}procedure search(top:integer);vari,j : integer;p : boolean; {p=true表示找到某列的配置}beginif top>8then begin {配置成功,打印布局}total:=total+1;writeln(total,' step: ');for i:=1 to 8 do write(s[i],' ');writeln;endelse beginfor i:=1 to 8 do begin {由第1行开始,顺序选择} p:=true;if top>1 then beginj:=1; {确定可否在(i,top)位置配置皇后} while (j<top) and p do beginif (s[j]=i) or (abs(s[j]-i)=abs(j-top))then p:=false;j:=j+1;end;end;if p then begin {top列配置成功}s[top]:=i;search(top+1); {递归执行top+1列上的配置} end;end;end;end;Begintotal:=0; {布局数计数器清0}search(1);End.§3.4.2 递归算法适用的场合1、数据的定义形式按递归定义如斐波那契数列的定义： f n = f n-1 + f n-2； f0 = 1 ； f1 = 2 ；【练习3】对应的递归程序为：function fib ( n : integer ) : integer;beginif n=0 then {递归边界}else {递归}end; {fib}★这类问题可转化为递推算法,递归边界作为递推的边界条件,如上例： f [0]:= 1; f [1]:= 2; {递推边界}for i:=2 to n do f [ i ]:= f [ i-1 ]+ f [ i-2 ];fib:= f [ n ];2、数据之间的关系（即数据结构）按递归定义,如树的遍历、图的搜索等；3、问题解法按递归算法实现,如回溯法、分治法等；递归算法效率较低,费时费空间,但递归算法可以使一个蕴含递归关系的程序简洁精炼.P. （相关知识见《数学基础补充§1》）【练习4】输出N元集的R排列,及其排列种数rn（输入： N R）C.【练习5】输出N元集的R组合,及其排列种数rn（输入： N R）练习3答案：① fib:=2 ② fib:=fib(n-2)+fib(n-1);。
