栈及栈的应用.docx
- 文档编号:15513635
- 上传时间:2023-07-05
- 格式:DOCX
- 页数:25
- 大小:54.02KB
栈及栈的应用.docx
《栈及栈的应用.docx》由会员分享,可在线阅读,更多相关《栈及栈的应用.docx(25页珍藏版)》请在冰点文库上搜索。
栈及栈的应用
栈
[内容提要]
1、栈的概念和特性;
2、栈的存储结构;
3、栈的几种运算(操作)实现;
4、栈的应用举例;
[重点难点]
1、栈的概念和特性;
2、栈的应用场合;
3、栈的操作实现;
[内容讲授]
1.栈的概念和特性
栈(stack)是一种特殊的线性表。
作为一个简单的例子,可以把食堂里冼净的一摞碗看作一个栈。
在通常情况下,最先冼净的碗总是放在最底下,后冼净的碗总是摞在最顶上。
而在使用时,却是从顶上拿取,也就是说,后冼的先取用,后摞上的先取用。
好果我们把冼净的碗“摞上”称为进栈(压栈),把“取用碗”称为出栈(弹出),那么,上例的特点是:
后进栈的先出栈。
然而,摞起来的碗实际上是一个表,只不过“进栈”和“出栈”都在最顶上进行,或者说,元素的插入和删除是在表的一端进行而已。
一般而言,栈是一个线性表,其所有的插入和删除均是限定在表的一端进行,允许插入和删除的一端称栈顶(Top),不允许插入和删除的一端称栈底(Bottom)。
若给定一个栈S=(a1,a2,a3,…,an),则称a1为栈底元素,an为栈顶元素,元素ai位于元素ai-1之上。
栈中元素按a1,a2,a3,…,an的次序进栈,如果从这个栈中取出所有的元素,则出栈次序为an,an-1,…,a1。
也就是说,栈中元素的进出是按后进先出的原则进行,这是栈结构的重要特征。
因此栈又称为后进先出(LIFO—LastInFirstOut)表。
我们常用一个图来形象地表示栈,其形式如下图:
通常,对栈进行的运算主要有以下几种:
⑴在使用栈之前,首先需要建立一个空栈,称建栈;
⑵往栈顶加入一个新元素,称进栈(压栈);
⑶删除栈顶元素,称出栈(退栈、弹出);
⑷查看当前的栈顶元素,称读栈;{注意与⑶的区别}
⑸在使用栈的过程中,还要不断测试栈是否为空或已满,称为测试栈。
2.栈的存储结构
栈是一种线性表,在计算机中用向量作为栈的存储结构最为简单。
因此,当用编程语言写程序时,用一维数组来建栈十分方便。
例如,设一维数组STACK[1..n]表示一个栈,其中n为栈的容量,即可存放元素的最大个数。
栈的第一个元素,或称栈底元素,是存放在STACK[1]处,第二个元素存放在STACK[2]处,第i个元素存放在STACK[i]处。
另外,由于栈顶元素经常变动,需要设置一个指针变量top,用来指示栈顶当前位置,栈中没有元素即栈空时,令top=0,当top=n时,表示栈满。
如果一个栈已经为空,但用户还继续做出栈(读栈)操作,则会出现栈的“下溢”;如果一个栈已经满了,用户还继续做进栈操作,则会出现栈的“上溢”。
两种情况统称为栈的溢出。
3.对栈的几种运算的实现方法:
(1)建栈
这比较简单,只要建立一个一维数组,再把栈顶指针置为零。
栈的容量根据具体的应用要求而定。
比如:
typearraytype=array[1..n]ofinteger;
varstack:
arraytype;
top:
integer;
再在程序开始时,置top:
=0;
(2)测试栈
测试栈顶指针的值,若top=0,则栈空;若top=n,则栈满。
(3)读栈
若top=0,则栈空,无栈顶元素可读,出错;若top<>0,则回送栈顶元素的值STACK[top]。
(4)进栈(push)
将栈顶指针加1后,再把新元素送到栈顶。
假设新元素x为整型,栈的最大深度为n,x和n设置为值型参。
而栈和栈顶指针要设置成变量型参。
procedurepush(varstack:
arraytype;vartop:
integer;n:
integer;x:
integer);
begin
iftop=n
thenbeginwriteln(‘Stackfull!
’);haltend
elsebegintop:
=top+1;stack[top]:
=xend
end;
(5)退栈(pop)
取得栈顶元素的值后,再把栈顶指针top减1。
注意都用变量型参。
procedurepop(varstack:
arraytype;vartop:
integer;varx:
integer);
begin
iftop=0
thenbeginwriteln(‘Stackempty!
’);haltend
elsebeginx:
=stack[top];top:
=top-1end
end;
注意:
由于栈本身和栈顶指针是密不可分的,所以有时我们把他们定义成一个记录来处理。
如:
typestack=record
vec:
array[1..n]ofinteger;{n为栈可达到的最大深度}
top:
integer;
end;
则以上几种运算的实现只要稍做修改即可。
procedurepush(vars:
stack;x:
integer);
begin
ifs.top=n
thenbeginwriteln(‘Stackfull!
’);haltend
elsebegins.top:
=s.top+1;s.vec[s.top]:
=xend
end;
procedurepop(vars:
stack;varx:
integer);
begin
ifs.top=0
thenbeginwriteln(‘Stackempty!
’);haltend
elsebeginx:
=s.vec[s.top];s.top:
=s.top-1end
end;
出栈有时也可用函数实现,如:
functionpop(vars:
stack):
integer;
begin
ifs.top=0
thenbeginwriteln(‘Stackempty!
’);haltend
elsebeginpop:
=s.vec[s.top];s.top:
=s.top-1end
end;
[栈的应用举例]
1、若已知一个栈的入栈顺序是1,2,3,…,n,其输出序列为P1,P2,P3,…,Pn,若P1是n,则Pi是(C)。
A)i B)n-1 C)n-i+1 D)不确定
2、以下哪一个不是栈的基本运算(B)。
A)删除栈顶元素 B)删除栈底的元素 C)判断栈是否为空D)将栈置为空栈
3、设栈S和队列Q初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若出队的顺序为e2,e4,e3,e6,e5,e1,则栈S的容量至少应该为(B)。
A)2B)3C)4D)5
4、设栈S的初始状态为空,现有5个元素组成的序列{1,2,3,4,5},对该序列在S栈上依次进行如下操作(从序列中的1开始,出栈后不在进栈):
进栈,进栈,进栈,出栈,进栈,出栈,进栈,问出栈的元素序列是:
_________,栈顶指针的值为______,栈顶元素为:
___________________。
解答:
出栈序列为{3,4},栈顶指针值为3,栈顶元素为5。
5、设栈S和队列Q初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若出队顺序为e2,e4,e3,e6,e5,e1,则栈S的容量至少应该为______________。
解答:
为3。
6、如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。
其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。
现已知第一个到达出口的是3号车厢,请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。
出口←
←
12345
S↓
解答:
9
栈的应用举例(栈与表达式)
[引言]
处理表达式是高级语言的编绎中的一个基本问题。
它的实现是栈的一个重要应用,通过对处理表达式的讨论,可以帮助我们进一步了解栈的性能。
[内容讲授]
栈在计算机科学领域有着广泛的应用。
比如在编译和运行计算机程序的过程中,就需要用栈进行语法检查(如检查begin和end、“(”和“)”等是否匹配)、计算表达式的值、实现过程和函数的递归调用等。
下面举例说明栈在这些方面的应用。
例1、假设一个表达式有英文字母(小写)、运算符(+,—,*,/)和左右小(圆)括号构成,以“@”作为表达式的结束符。
请编写一个程序检查表达式中的左右圆括号是否匹配,若匹配,则返回“YES”;否则返回“NO”。
表达式长度小于255,左圆括号少于20个。
分析:
假设输入的字符串存储在c中(varc:
string[255])。
我们可以定义一个栈:
vars:
array[1..maxn]ofchar;top:
integer;
用它来存放表达式中从左往右的左圆括号。
算法的思路为:
顺序(从左往右)扫描表达式的每个字符c[i],若是“(”,则让它进栈;若遇到的是“)”,则让栈顶元素出栈;当栈发生下溢或当表达式处理完毕而栈非空时,表示不匹配,返回“YES”,否则表示匹配返回“NO”。
程序代码如下:
varc:
string;
functiondoit(c:
string):
boolean;
vars:
array[1..20]ofchar;
top,i:
integer;
ch:
char;
begin
top:
=0;
i:
=1;ch:
=c[i];
whilech<>'@'do
begin
if(ch='(')or(ch=')')then
casechof
'(':
begintop:
=top+1;s[top]:
='('end;
')':
iftop>0thentop:
=top-1
elsebegindoit:
=false;exitend;
end;
i:
=i+1;ch:
=c[i];
end;
iftop=0thendoit:
=true
elsedoit:
=false;
end;
begin
assign(input,'in.txt');
reset(input);
readln(c);
writeln(doit(c));
close(input);
end.
[补充]关于表达式的三种表示法。
1、中缀表达式:
a+b
2、后缀表达式:
ab+
3、前缀表达式:
+ab
4、中缀转后缀的方法及举例转换:
一般方法:
把每个运算符移到它的两个运算数后面,每个运算数后多加上一个空格(为了分隔各个运算数),然后去掉所有括号即可。
如:
3/5+6——————————3□5□/□6□+{□表示空格,下同}
16-9*(4+3)——————19□9□4□3□+*-
2*(x+y)/(1-x)———————2□x□y□+*1□x□-/
(25+x)*(a*(a+b)+b)————25□x□+a□a□b□+*b□+*
另外一种手工方法:
可以用后面讲到的二叉表达式树结合先序、中序和后序遍历。
5、中缀表达式的运算规则比较多,包括优先级、左右次序和括号;尤其是括号可以改变优先顺序,这就只能在计算的每一步,用肉眼去扫描、观察和比较整个表达式中谁的优先级高,就先计算那部分。
但用计算机去做就很麻烦,而且效率不高。
所以,计算机科学中是把中缀表达式先转换成后缀表达式,在利用计算机来计算后缀表达式的值。
后缀表达式又称“逆波兰式”,在后缀表达式中,不存在括号,也不存在优先级的差别,计算过程完全按照运算符出现的先后顺序进行,整个计算过程仅需一遍扫描即可完成。
6、两个任务:
(1)把中缀表达式转换成后缀表达式;
(2)求后缀表达式的值;
例2、输入一个中缀表达式,编程输出其后缀表达式,要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序相一致。
为简单起见,假设输入的中缀表达式由+(加)、-(减)、×(乘)、/(除)四个运算符号以及左右圆括号和大写英文字母组成,其中算术运算符遵守先乘除后加减的运算规则。
假设输入的中缀表达式长度不超过80个字符,且都是正确的,即没有语法错误,并且凡出现括号其内部一定有表达式,即内部至少有一个运算符号。
以下是一个运行实例。
输入:
X+A*(Y-B)-Z/F
输出:
XAYB-*+ZF/-
[算法设计]
设置两个栈:
操作数栈(ovs)和运算符栈(ops),用来分别存放表达式中的操作数和运算符。
开始时操作数栈为空,运算符栈中放入一个特殊的标志运算符号#号,并在表达式的末尾加上一个#号,并规定#号的优先级最低,然后从左向右扫描表达式,凡遇操作数便一律进栈;若遇运算符,则判断其优先级是否大于运算符栈栈顶元素的优先级。
若小,则栈顶运算符退栈,并从操作数栈中弹出两个操作数(操作数为后缀表达式)进行后缀变换处理,处理结果进操作数栈,重复刚才的比较,直到栈顶运算符的优先级大于等于当前运算符的优先级,此时,若当前运算符的优先级大于栈顶运算符的优先级,则当前运算符进栈,继续扫描;若当前运算符的优先级等于栈顶运算符的优先级,则弹出栈顶运算符,继续扫描。
扫描完该表达式后运算符栈为空,操作数栈中只有一个元素,该元素就是所要求的后缀表达式。
以下程序中的数组f用来存放运算符之间的优先级关系,1(>)表示前面的运算符优先于后面的运算符,-1(<)表示后面的运算符优先于前面的运算符,0(=)表示前面的运算符的优先级与后面的运算符相同,2(ERROR)表示这两个运算符如果在扫描中相遇的话,意味着该表达式是错误的。
需要补充的是:
左括号的优先级是最高的,而里层的左括号比外层的左括号更优先,右括号的优先级是除#号以外最低的,但左括号和右括号的优先级则是相等的,这样定义的目的是为了消去括号。
以上规律列表如下:
+
-
*
/
(
)
#
+
>
>
<
<
<
>
>
-
>
>
<
<
<
>
>
*
>
>
>
>
<
>
>
/
>
>
>
>
<
>
>
(
<
<
<
<
<
=
ERROR
)
>
>
>
>
ERROR
>
>
#
<
<
<
<
<
ERROR
=
上述算法还可用于求一个表达式的值和判断一个表达式是否有错等等。
右上图是对范例表达式的扫描示意图:
[程序清单]
programex2(input,output);
constmax=100;
op_set:
setofchar=['+','-','*','/'];
letter:
setofchar=['A'..'Z'];
varexpression,result:
string;
procedurescan(expression:
string);
vari,top1,top2:
integer;
ovs:
array[1..max]ofstring[max];
ops:
array[1..max]ofchar;
f:
array['#'..'/','#'..'/']ofshortint;
begin
f['+','+']:
=1;f['+','-']:
=1;f['+','*']:
=-1;f['+','/']:
=-1;f['+','(']:
=-1;f['+',')']:
=1;f['+','#']:
=1;
f['-','+']:
=1;f['-','-']:
=1;f['-','*']:
=-1;f['-','/']:
=-1;f['-','(']:
=-1;f['-',')']:
=1;f['-','#']:
=1;
f['*','+']:
=1;f['*','-']:
=1;f['*','*']:
=1;f['*','/']:
=1;f['*','(']:
=-1;f['*',')']:
=1;f['*','#']:
=1;
f['/','+']:
=1;f['/','-']:
=1;f['/','*']:
=1;f['/','/']:
=1;f['/','(']:
=-1;f['/',')']:
=1;f['/','#']:
=1;
f['(','+']:
=-1;f['(','-']:
=-1;f['(','*']:
=-1;f['(','/']:
=-1;f['(','(']:
=-1;f['(',')']:
=0;f['(','#']:
=2;
f[')','+']:
=2;f[')','-']:
=2;f[')','*']:
=2;f[')','/']:
=2;f[')','(']:
=2;f[']',')'):
=2;f[']','#'):
=2;
f['#','+']:
=-1;f['#','-']:
=-1;f['#','*']:
=-1;f['#','/']:
=-1;f['#','('):
=-1;f['#',']']:
=2;f['#','#']:
=0;
expression:
=expression+'#';
ops[1]:
='#';
top1:
=0;
top2:
=1;
fori:
=1tolength(expression)do
begin
ifexpression[i]inletter
thenbegintop1:
=top1+1;
ovs[top1]:
=expression[i]
end
elsebegin
whilef[ops[top2],expression[i]]=1do
begin
ovs[top1-1]:
=ovs[top1-1]+ovs[top1]+ops[top2];
top1:
=top1-1;
top2:
=top2-1
end;
iff[ops[top2],expression[i]]=0
thentop2:
=top2-1
elsebegintop2:
=top2+1;
ops[top2]:
=expression[i]
end;
end
end;
result:
=ovs[1]
end;
begin{main}
write('Inputaexpression:
');
readln(expression);
scan(expression);
writeln('Theresultis:
',result)
end.
测试输入:
A*(X+Y)/(B-Z)
输出:
AXY+*BZ-/
例3、编程求一个后缀表达式的值。
从键盘读入一个后缀表达式(字符串),只含有0-9组成的运算数及加(+)、减(—)、乘(*)、除(/)四种运算符。
每个运算数之间用一个空格隔开,不需要判断给你的表达式是否合法。
分析:
先读入后缀表达式(字符串)。
后缀表达式的处理过程如下:
扫描后缀表达式,凡遇操作数则将之压进堆栈,遇运算符则从堆栈中弹出两个操作数进行该运算,将运算结果压栈,然后继续扫描,直到后缀表达式被扫描完毕为止,此时栈底元素即为该后缀表达式的值。
程序:
constmaxn=20;
varstack:
array[1..maxn]ofinteger;
s:
string;
functioncomp(s:
string):
integer;
varch:
char;
i,top,x,y,z:
integer;
begin
top:
=0;
i:
=1;
ch:
=s[i];
whilei<=length(s)dobegin
casechof
'0'..'9':
beginx:
=0;
whilech<>''dobegin
x:
=x*10+ord(ch)-ord('0');
i:
=i+1;
ch:
=s[i];
end;
top:
=top+1;
stack[top]:
=x;
end;
'+':
beginx:
=stack[top];top:
=top-1;y:
=stack[top];z:
=y+x;stack[top]:
=zend;
'-':
beginx:
=stack[top];top:
=top-1;y:
=stack[top];z:
=y-x;stack[top]:
=zend;
'*':
beginx:
=stack[top];top:
=top-1;y:
=stack[top];z:
=y*x;stack[top]:
=zend;
'/':
beginx:
=stack[top];top:
=top-1;y:
=stack[top];z:
=ydivx;stack[top]:
=zend;
end;
i:
=i+1;
ch:
=s[i];
end;{while}
comp:
=stack[top];
end;
begin{main}
writeln('inputastring(@_over):
');
readln(s);
writeln('result=',comp(s));
readln;
end.
[作业与思考]
请把本节的内容组合在一起,编一个程序,输入一个中缀表达式(由0-9组成的运算数、加+减—乘*除/四种运算符、左右小括号组成。
注意“—”也可作为负数的标志,表达式以“@”作为结束符),判断表达式是否合法,如果不合法,请输出“NO”;否则请把表达式转换成后缀形式,再求出后缀表达式的值并输出。
注意:
必须用栈操作,不能直接输出表达式的值。
如果再考虑是实数运算呢?
栈与递归
[递归算法及在计算机中的实现]
1、递归算法
例1、用递归算法把任一给定的十进制正整数(<=32000)转换成八进制数输出,程序如下:
varm:
integer;
proceduretran(n:
integer);{递归过程}
vark:
integer;
begin
k:
=nmod8;
n:
=ndiv8;
ifn<>0thentran(n);
write(k:
1)
end;
begin{主程序}
write('inputm:
');
readln(m);
write(m,'=(');
tran(m);
writeln(')8');
readln;
end.
输入:
m=765{下划线表示输入}
输出:
765=(1375)8
例2、用递归算法求N阶乘(N!
=1*2*3*……*N,N<20);
varn:
integer;
functionf(n:
integer):
longint;{递归函数,N=20时,超过maxlongint}
begin
ifn=0thenf:
=1
elsef:
=n*f(n-1)
end;
begin{主程序}
write('inputn:
');
readln(n);
write(n,'!
=',f(n));
end.
2、递归在计算机中的实现
计算机执行递归算法时,是通过栈来实现的。
具体说来,就是在(递归过程或递归函数)开始运行时,系统首先为递归建立一个栈,该栈的元素类型(数据域)包括值参、局部变量和返回地址;在每次执行递归调用语句时之前,自动把本算法中所使用的值参和局部变量的当
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 应用
![提示](https://static.bingdoc.com/images/bang_tan.gif)