数据结构_栈及其应用.pptVIP

数据结构-栈;对于程序设计来说： 编程语言是工具； 数据结构是基础； 算法设计是方法。 ;数据结构;数据结构相关概念;逻辑结构;物理结构; ;线性表;线性表的两种存储方式;数组的插入与删除;链表的插入与删除;线性表的具体实现;顺序存储与链式存储操作的对比; 限定仅在表尾进行插入和删除操作的线性表,又称为后进先出(last in first out )线性表 (LIFO结构) 栈顶——表尾 栈底——表头;;栈的实现（一）;栈的实现（二）;栈的基本操作;1） 过程init(s,t) —初始化 procedure init; begin t:=0; end; 2)、过程push(x)—往栈s中压入一个值为x的数据： procedure push (var s：stack； x：stype； var t：integer)； begin if t=m then writeln(‘overflow’) {上溢} else begin t←t+1；s[t]←x；end；{else} {x入栈} end；{Push} ;3）函数pop(s，t)—从栈中弹出一个表目 function pop (var s：stack； var t：integer)：stype； begin if t=0 then writeln (‘underflow’) {下溢} else begin pop←s[t]； t←t-1； end；{else} {栈顶元素出栈} end；{pop} 4）函数top(s，t)—读栈顶元素 function top (s：stack； t：integer)：stype； begin if t=0 then writeln (‘stack empty’) else top←s[t]； {返回栈顶元素} end；{top} ;栈的应用;【样例3输入：】 { [ } ] 【样例3输出：】 no 【样例4输入：】 【样例4输出：】 no;i:=1; t:=0;tt:+0; while i=n do begin case s[i] of (,[,{,:push(s[i]); ):if pop( then begin tt:=1;break;end; }:if pop{ then tt:=1;break;end; ]:if pop[ then tt:=1;break;end; :if pop then tt:=1;break;end; end; inc(i); end; if (t0) or (tt0) then writeln(No) else writeln(Yes); end.;var f:array[char] of char; a:array[0..200] of char; s:string; ch:char; p,i,n:longint; function pop:char; begin pop:=a[p];dec(p); end; procedure push(x:char); begin inc(p); a[p]:=x; end; procedure print(k:integer); begin writeln(k); halt;end; begin f[[]:=]; f[(]:=); f[{]:=}; f[]:=;; readln(s); p:=0; i:=1; n:=length(s); while i=n do begin if ord(f[s[i]])0 then push(s[i]) //左括号进栈 else //右括号判断 begin if p=0 then print(0); //有多余的右括号 if f[pop]s[i] then print(0); //和前面的不匹配 end; inc(i); end; if p=0 then p