数据结构栈及其应用学习教案.pptx

会计学对于(duìyú)程序设计来说：
编程语言是工具；
数据结构是基础；
算法设计是方法。数据结构(shùjùjiéɡòu)数据结构相关(xiāngguān)概念逻辑(luójí)结构物理(wùlǐ)结构线性表线性表的两种存储(cúnchǔ)方式数组的插入(chārù)与删除链表的插入(chārù)与删除线性表的具体(jùtǐ)实现顺序存储与链式存储操作(cāozuò)的对比限定(xiàndìng)仅在表尾进行插入和删除操作的线性表,又称为后进先出(lastinfirstout)线性表(LIFO结构)

栈顶——表尾
栈底——表头栈的实现(shíxiàn)（一）栈的实现(shíxiàn)（二）栈的基本操作1）过程(guòchéng)init(s,t)—初始化
procedureinit;
begin
t:=0;
end;
2)、过程(guòchéng)push(x)—往栈s中压入一个值为x的数据：
procedurepush(vars：stack；x：stype；vart：integer)；
begin
ift=mthenwriteln(‘overflow’){上溢}
elsebegint←t+1；s[t]←x；end；{else}{x入栈}
end；{Push}3）函数pop(s，t)—从栈中弹出一个表目
functionpop(vars：stack；vart：integer)：stype；
begin
ift=0thenwriteln(‘underflow’){下溢}
elsebeginpop←s[t]；t←t-1；end；{else}{栈顶元素(yuánsù)出栈}
end；{pop}
4）函数top(s，t)—读栈顶元素(yuánsù)
functiontop(s：stack；t：integer)：stype；
begin
ift=0thenwriteln(‘stackempty’)
elsetop←s[t]；{返回栈顶元素(yuánsù)}
end；{top}栈的应用(yìngyòng)【样例3输入(shūrù)：】
{[}]
【样例3输出：】
no
【样例4输入(shūrù)：】
<>>>
【样例4输出：】
noi:=1;t:=0;tt:+0;
whilei<=ndo
begin
cases[i]of
'(','[','{','<':push(s[i]);
')':ifpop<>'('thenbegintt:=1;break;end;
'}':ifpop<>'{'thentt:=1;break;end;']':ifpop<>'['thentt:=1;break;end;'>':ifpop<>'<'thentt:=1;break;end;end;
inc(i);
end;
if(t<>0)or(tt<>0)thenwriteln('No')
elsewriteln('Yes');
end.var
f:array[char]ofchar;
a:array[0..200]ofchar;
s:string;ch:char;
p,i,n:longint;
functionpop:char;
beginpop:=a[p];dec(p);end;
procedurepush(x:char);
begininc(p);a[p]:=x;end;
procedureprint(k:integer);
beginwriteln(k);halt;end;
begin
f['[']:=']';
f['(']:=')';
f['{']:='}';
f['<']:='>';readln(s);
p:=0;i:=1;n:=length(s);
whilei<=ndo
begin
iford(f[s[i]])<>0thenpush(s[i])//左括号进栈
else//右括号判断
begin
ifp=0thenprint(0);//有多余的右括号
iff[pop]<>s[i]thenprint(0);//和前面(qiánmian)的不匹配
end;
inc(i);
end;
ifp=0thenprint(1)elseprint(0);
end.栈的应用(yìngyòng)3——表达式求值中缀表达式和后缀(hòuzhuì)表达式的特征中缀表达式的运算规则比较多，包括优先级、左右次序和括号；尤其是括号可以改变优先顺序，这就只能在计算的每一步，用肉眼去扫描、观察和比较整个(zhěnggè)表达式中谁的优先级高，就先计算那部分。但用计算机去做就很麻烦，而且效率不高。
所以，计算机科学中是把中缀表达式先转换成后缀表达式，在利用计算机来计算后缀表达式的值。后缀表达式又称“逆波兰式”，在后缀表达式中，不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现