pascal-第10讲-栈及应用

趣味栈及其应用山东省潍坊第一中学高常华2009-8-51952年10月，在抗美援朝上甘岭战役中，战士们正在向弹夹压子弹杂技演员表演叠罗汉的时候，最后上去的人总是第一个下来

洗碗是我们常做的一件家务活，我们在洗碗的时候，一般情况下，最先洗干净的碗总是放在下面，而后洗干净的碗放在上面；取碗吃饭时，却是从最顶上开始拿取。也就是说，后洗的碗先用。洗碗竖直摆放的图书货栈装水的杯子我们喝水的时候，最先喝到的总是最上层的水，而它们是最后被倒进去的。栈在计算机中的应用栈在计算机中的应用修改字体插入图片输入文本1插入1删除2删除1计算机操作命令撤消命令Fac(3)----→fac(2)--→fac(1)--→fac(0)=1↑3*fac(2)←2*fac(1)←1*fac(0)求函数值Fac(n)=n!=n*(n-1)!=n*fac(n-1)(n>0)其中fac(0)=1;例如Fac(3)=3*fac(2)Fac(2)=2*fac(1)Fac(1)=1*fac(0)Fac(0)=1Fac(0)Fac(1)Fac(2)Fac(3)“后进先出”(LASTINFIRSTOUT，简称LIFO)是它的特点，其实这是计算机程序设计中一个常见的数据结构——栈（STACK），它是一种存储数据的容器，就像装水的杯子一样。水杯里的水按照“后进先出”的顺序被倒进倒出，存储在栈中数据也是是按照“后进先出”的方式被插入和删除的。首先我们要搞清楚它本身的属性和能够实现的基本操作。

栈的属性？像装水的杯子一样的栈？首先应该要有一个容量属性吧，比如杯子的容量有200ML或500ML等栈有三个基本属性：最大容量（最大高度），实际存储量（实际高度），栈空指示标志。存储数据的容器，像装水的杯子一样。。。。。嗯！那它应该可以插入和删除数据。对了，栈用什么来装这些数据啊

杯子满了就不能再加了。对了，我们还要做一个判断栈满的操作

往里加水的时候要判断栈满，那往外倒水的时候就应该判断栈空了——我们还要做一个判断栈空的操作我们并不是一拿到杯子就要喝水，有些时候我们只是想看看杯子里面的水干不干净，并不一定要往外倒水。这也可以看成是一个基本操作：获取栈顶元素的值

栈的特点：后进先出栈这种数据结构就是有三个基本属性和五个基本操作

三个基本属性：最大容量（最大高度），实际存储量（实际高度），栈空指示标志五个基本操作:压入、弹出、判断栈满、判断栈空、获取栈顶元素的值对于一个栈，给定一个输入项目a,b,c。如果输入的顺序规定为abc，试写出全部可能的输出序列

就是a先入栈，b再入栈，c最后入栈Abc的全排列应当有6个，其中cab不合要求CbaBcaBacAcbAbc对于一个栈，给定一个输入项目a,b,c。如果输入的顺序规定为abc，试写出全部可能的输出序列

就是a先入栈，b再入栈，c最后入栈按照a先入栈，b再入栈，c最后入栈的规定：CBA弹出-------输出1--CBABAAa先入栈B再入栈c最后入栈A对于一个栈，给定一个输入项目a,b,c。如果输入的顺序规定为abc，试写出全部可能的输出序列

就是a先入栈，b再入栈，c最后入栈按照a先入栈，b再入栈，c最后入栈的规定：CA弹出-------输出2--bcABAAa入栈B入栈c入栈B出栈AC出栈A对于一个栈，给定一个输入项目a,b,c。如果输入的顺序规定为abc，试写出全部可能的输出序列

就是a先入栈，b再入栈，c最后入栈按照a先入栈，b再入栈，c最后入栈的规定：C弹出-------输出3--bacBAAa入栈B入栈c入栈B出栈

C出栈

A出栈B对于一个栈，给定一个输入项目a,b,c。如果输入的顺序规定为abc，试写出全部可能的输出序列

就是a先入栈，b再入栈，c最后入栈按照a先入栈，b再入栈，c最后入栈的规定：弹出-------输出4--AcbBAa入栈B入栈C出栈AA出栈CBC入栈

B出栈B对于一个栈，给定一个输入项目a,b,c。如果输入的顺序规定为abc，试写出全部可能的输出序列

就是a先入栈，b再入栈，c最后入栈按照a先入栈，b再入栈，c最后入栈的规定：

弹出-------输出5--Abc

Aa入栈A出栈B出栈B入栈CC入栈

C出栈CBA

弹出-------不能输出6--cabBAAa入栈B入栈出栈C入栈

出栈

出栈不能实现的情况题目：输入一个正整数n，试分离并输出其各位数字。例如，输入n=1234，则输出1，2，3，4。（保证n不超出integer的范围）分离并输出其各位数字{代码1：}{输入一个正整数n，试分离并输出其各位数字}PROGRAMSeparate(INPUT,OUTPUT);VARv,n:integer;BEGIN{MAIN}writeln('Inputn:');readln(n);whilen<>0dobeginv:=nmod10;{分离出n的个位数字}write(v:2);n:=ndiv10;{去除n的个位数字}end;{while}END.输出顺序颠倒!!!{代码2：}{先判断出n是个几位数，再从高位开始分离数字并输出}PROGRAMSeparate(INPUT,OUTPUT);VARv,n,h:integer;FUNCTIONHighest(n:integer):integer;{判断n是个几位数，最大为32767}beginend;{Highest见下一片}BEGIN{MAIN}writeln('Inputn:');readln(n);h:=Highest(n);{判断n是个几位数}whileh<>0do{分离数字并将其入栈}beginv:=ndivh;{分离出n的最高位数字}write(v:2);n:=nmodh;{去除n的最高位数字}h:=hdiv10;{n位数降1}end;{while}END.1836Div1000=11836mod1000=8361000div10=100FUNCTIONHighest(n:integer):integer;{判断n是个几位数，最大为32767}Beginifn>10000thenHighest:=10000elseifn>1000thenHighest:=1000elseifn>100thenHighest:=100elseifn>10thenHighest:=10elseHighest:=1;end;{Highest}{递归方法}{输入一个正整数n，试分离并输出其各位数字}Procedurefen(n:integer);VARv:integer;BEGINv:=nmod10;{分离出n的个位数字}n:=ndiv10;{去除n的个位数字}ifn<>0thenfen(n);write(v:1);END;PROGRAMSeparate(INPUT,OUTPUT);VARn:integer;BEGIN{MAIN}readln(n);fen(n);writeln;End.{代码3：}{利用栈解决分离数字问题：输入一个正整数n，试分离并输出其各位数字}PROGRAMSeparate(INPUT,OUTPUT);CONSTMAXCAPACITY=100;{栈的最大容量}BOTTOM=0;{栈底标志}TYPEElemType=integer;{栈内元素数据类型}Stack=array[1..MAXCAPACITY]ofElemType;{用数组表示的栈}VARs:Stack;{定义s为栈}top:integer;{栈顶标志}v,n:integer;{代码3：}FUNCTIONStackEmpty(s:Stack;top:integer):boolean;{判断是否栈空}begin

StackEmpty:=(top=BOTTOM);end;{StackEmpty}

FUNCTIONStackFull(s:Stack;top:integer):boolean;{判断是否栈满}begin

StackFull:=(top=MAXCAPACITY);end;{StackFull}{代码3：}FUNCTIONGetTop(s:Stack;top:integer)

:ElemType;{获取栈顶元素的值}begin

ifStackEmpty(s,top)then

writeln('underflow')

else

GetTop:=s[top];end;{GetTop}{代码3：}PROCEDUREPush(vars:Stack;vartop:integer;data:ElemType);{入栈}begin

ifStackFull(s,top)then

writeln('overflow')

else

begin

inc(top);

s[top]:=data;

end;{if}end;{Push}{代码3：}PROCEDUREPop(vars:Stack;vartop:integer);{出栈}begin

ifStackEmpty(s,top)then

writeln('underflow')

else

dec(top);end;{Pop}BEGIN{MAIN}top:=0;{栈顶初始化}readln(n);whilen<>0do{分离数字并将其入栈}beginv:=nmod10;{分离出n的个位数字}Push(s,top,v);{个位数字入栈}n:=ndiv10;{去除n的个位数字}end;{while}whilenotStackEmpty(s,top)do{输出数字并出栈}beginwrite(GetTop(s,top):2);Pop(s,top);end;{while}END.{判断字符串中的括号是否匹配}（（（{[]}）））（（[（]）））{判断字符串中的括号是否匹配}PROGRAMTheBracketMatch(INPUT,OUTPUT);CONSTMAXCAPACITY=255;{栈的最大容量}BOTTOM=0;{栈底标志}TYPEElemType=char;{栈内元素数据类型}Stack=array[1..MAXCAPACITY]ofElemType;{用数组表示的栈}VARcode:string;s:Stack;{定义s为栈}top:integer;{栈顶标志}。。。。。。{此处为栈的基本操作函数，不再重复列出}FUNCTIONBracketMatch(code:string):BOOLEAN;var

i,len:integer;

flag

:boolean;begin

len:=length(code);{code代码长度}

fori:=1tolendo

begin………见后面幻灯片……………end;{for}

BracketMatch:=true;end;{BracketMatch}{判断字符串中的括号是否匹配}fori:=1tolendobeginflag:=false;{左右括号匹配}casecode[i]of'(','[','{','<':Push(s,top,code[i]);{左括号入栈}')':ifGetTop(s,top)='('then{右括号出栈或报错}Pop(s,top)elseflag:=true;{左右括号不匹配}']':ifGetTop(s,top)='['thenPop(s,top)elseflag:=true;

'}':ifGetTop(s,top)='{'thenPop(s,top)elseflag:=true;'>':ifGetTop(s,top)='<'thenPop(s,top)elseflag:=true;end;{case}

ifflagthen{左右括号不匹配}beginBracketMatch:=false;exit;end;{if}end;{for}注：此处调用有关栈的基本操作调用了代码3中的子函数，不再重复列出，主函数如下：BEGIN{MAIN}

top:=0;{栈顶初始化}

writeln('Inputcode:');

readln(code);

ifBracketMatch(code)then

writeln('match!')

else

writeln('mismatch!');END.1、若已知一个栈的入栈顺序是1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn，若P1是n，则Pi是(C)。

A)iB)n-1C)n-i+1D)不确定练习题654321数据序号i入栈如图所示出栈顺序是：N=6I=4P1=6Pi=p4=3=6-4+1=n-I+1p1=6I→1234562、以下哪一个不是栈的基本运算(B)。

A)删除栈顶元素B)删除栈底的元素

C)判断栈是否为空D)将栈置为空栈3、设栈S的初始状态为空,现有5个元素组成的序列{1,2,3,4,5},对该序列在S栈上依次进行如下操作(从序列中的1开始,出栈后不再进栈):进栈,进栈,进栈,出栈,进栈,出栈,进栈,问出栈的元素序列是:_________,栈顶指针的值为______，栈顶元素为:______。

进栈进栈进栈出栈进栈出栈进栈12132121输出（出栈序列）34栈顶指针值为3栈顶元素为5。42121521数制转换十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：

N=(Ndivd)×d+Nmodd(其中：div为整除运算，mod为求余运算)例如：(1348)10=(2504)8，其运算过程如动画演示所示：

假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。算法数据N=1348余数R=nmod8计算n=ndiv8判断n=0?否，返回计算余数是，倒序输出余数r数制转换方法1：Varn,k:integer;Beginn:=1384;k:=nmod8;write(k:1);n:=ndiv8;untiln=0;Writeln;End顺序反了数制转换方法2：递归Proceduretran(n:integer);Vark:integer;Begink:=nmod8;n:=ndiv8;ifn<>0thentran(n);write(k:1);End;Varm:integer;Beginreadln(m);tran(m);End.算法3Programp1(input,output);typestack=recorddata：array[1..100]ofinteger;top：0..100;end;varn:integer;e:integer;s:stack;

{对于输入的任意一个非负十进制整数打印输出与其等值的八进制数}beginS.top:=0;{构造空栈}Readln(n);{输入一个十进制数}while(n>0)beginPush(s,nmod8);{"余数"入栈}n:=ndiv8;{非零"商"继续运算}end;while(s.top<>0)){和"求余"所得相逆的顺序输出八进制的各位数}beginPop(S,e);write(e);end;end.后缀表达式求值

后缀式的运算规则为：运算符出现的顺序即为表达式的运算顺序；每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式；如：3.5.2.-*7.+@’@’为表达式的结束符号。‘.’为操作数的结束符号。运算符号：+、-、*、/【输入：】后缀表达式（长度不超过100）。【输出：】表达式的值。【样例输入：】3.5.2.-*7.+@【样例输出：】16如何按后缀式进行运算？

可以用两句话来归纳它的求值规则："先找运算符，后找操作数。"算法分析： 栈S用来存放原始数据、中间结果和最终结果。将后缀表达式以@结束存入字符数组，且每个数据后面加一个空格。扫描中，数据入栈，遇到运算符，就依次弹出两个操作数进行运算，运算结果入栈。遇到字符@结束，栈顶的值就是算式的结果。我们来看个例子！（每个数据都是个位数）programp1(input,output);typestack=recorddata:array[1..100]ofreal;{存放实型数}top:0..100;end;vars:stack;ch:char;i:integer;x:real;a:array[1..30]ofchar;functionpop(vars:stack):real;{出栈}beginpop:=s.data[s.top];s.top:=s.top-1;end;procedurepush(vars:stack;x:real);{入栈}begins.top:=s.top+1;s.data[s.top]:=x;end;begin{主程序}i:=0;repeati:=i+1;read(a[i]);{将表达式存入数组a}untila[i]='@';s.top:=0;{清空栈}i:=1;{i为a数组的下标}ch:=a[i];whilech<>'@'dobegincasechof'0'..'9':begin{产生完整的数}x:=0;whilech<>‘.'dobeginx:=x*10+ord(ch)-ord('0');i:=i+1;ch:=a[i];end;end;'+':x:=pop(s)+pop(s);'-':beginx:=pop(s);x:=pop(s)-x;end;'*':x:=pop(s)*pop(s);'/':beginx:=pop(s);x:=pop(s)/x;end;end;push(s,x);{结果入栈}i:=i+1;ch:=a[i];{继续扫描}end;writeln(pop(s));end.八皇后问题解题方法研究1ProcedureTry(I:integer)；{搜索第I行皇后的位置}Varj:integer;beginifI=n+1then输出方案；forj:=1tondoif皇后能放在第I行第J列的位置thenbegin放置第I个皇后；对放置皇后的位置进行标记；Try（I+1）对放置皇后的位置释放标记；end;end;递归programbahuanghou;vara:array[1..8]ofinteger;b,c,d:array[-7..16]ofinteger;t,i,j,k:integer;beginfork:=-7to16dobeginb[k]:=0;c[k]:=0;d[k]:=0;end;try(1);end.八皇后问题解题方法研究2递归procedureprint;begint:=t+1;write(t,'');fork:=1to8dowrite(a[k]);writeln;end;proceduretry(i:integer);varj:integer;beginfo