3栈队列数组.ppt

《3栈队列数组.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构DataStructure第三章栈、队列和数组第三章栈、队列和数组3.1栈3.2队列3.3数组3.4栈的应用——栈和递归3.1栈－定义栈——只能在一端插入和删除元素的线性表特点：后进先出（LIFO）术语：栈顶栈底入栈（压栈）出栈（弹栈）a1a2…ananan-1……a1入栈入栈栈顶栈底3.1栈－运算栈的基本运算（1）初始化栈：init_stack(S);（2）判栈空：stack_empty(S);（3）判栈满：stack_full(S);（4）读栈顶元素：stack_top(S,x);（5）入

2、栈：push_stack(S,x);（6）出栈：pop_stack(S);3.1栈－顺序栈存储结构1、顺序栈存储结构——采用顺序表来存储的栈#definemaxsize最大容量typedefstruct{elementtypedata[maxsize];inttop;//指示栈顶元素的位置}seqstack;a1a2a3a4…andatatopseqstack3.1栈－顺序栈图例a2a3a1top3210-13210-1top空栈栈顶元素为a33.1栈－顺序栈运算实现(1)初始化:voidinit_s

3、tack(seqstack*S){S->top=-1;}(2)判栈空:BOOLstack_empty(seqstackS){return(S.top==-1);}(3)判栈满:BOOLstack_full(seqstackS){if(S.top==maxsize-1)return(TRUE);elsereturnFALSE;}(4)读栈顶元素:voidstack_top(seqstack*S,elementtype&x){if(S->top==-1)error(“栈空”);elsex=S->data[

4、s->top];}3.1栈－顺序栈运算实现(入栈/出栈)(5)入栈:voidpush_stack(seqstack*S,elementtypex){if(S->top==maxsize-1)error(“栈满”);else{S->top++;S->data[S->top]=x;}}(6)出栈:voidpop_stack(seqstack*S,elementtype&x){if(stack_empty(*S))error(“栈空,不能删除”);elsex=S->data［S->top--］;}3.1栈－

5、链栈链栈结构图—采用链表来存储的栈a1a2a3a4^top链栈出栈：a1a2a3a4^top链栈入栈：a1a2a3a4^topxP3.1栈－栈的应用表达式的计算：模拟表达式：12+5*(2+3)*6/2-4的求解过程。例运算符操作数#12+5*(2+3)*6/2-4#操作数运算符各自依次入栈。出栈规则：当前入栈的运算符比栈顶的运算符优先级低。3.1栈－栈的应用（表达式计算）表达式的计算以表达式12+5*(2+3)*6/2-4的计算过程的实现为例来讨论栈结构在实现对任意输入的通用表达式的计算中的作用#

6、12+5*(2+3)*6/2-4#开始时，指向第一个位置，准备读入，此时的两个栈均为空。CurrentS=‘#’3.1栈－栈的应用（表达式计算）表达式的计算以表达式12+5*(2+3)*6/2-4的计算过程的实现为例来讨论栈结构在实现对任意输入的通用表达式的计算中的作用#12+5*(2+3)*6/2-4#开始时，指向第一个位置，准备读入，此时的两个栈均为空。#12+5*(2+3)*6/2-4#＃12CurrentS=‘＋’栈顶算符‘#’比当前运算符‘＋’优先级低，故算符‘＋’要入栈CurrentS=‘

7、#’3.1栈－栈的应用（表达式计算）#12+5*(2+3)*6/2-4#CurrentS=‘＋’依次读入5、×、（、2和＋后，栈顶算符‘（’比当前算符‘＋’优先级低，故‘＋’要入栈(X+#25123.1栈－栈的应用（表达式计算）#12+5*(2+3)*6/2-4##12+5*(2+3)*6/2-4#CurrentS=‘＋’依次读入5、×、（、2和＋后，栈顶算符‘（’比当前算符‘＋’优先级低，故‘＋’要入栈(X+#2512CurrentS=‘)’+(X+#32512栈顶算符‘＋’比当前运算符‘）’优先级

8、高，故要执行其运算2+3并入栈3.1栈－栈的应用（表达式计算）#12+5*(2+3)*6/2-4#CurrentS=‘)’(X+#5512栈顶算符‘（’与当前运算符‘）’相对应，故要出栈，一同释放3.1栈－栈的应用（表达式计算）#12+5*(2+3)*6/2-4##12+5*(2+3)*6/2-4#CurrentS=‘)’(X+#5512CurrentS=‘X’X+#5512栈顶算符‘（’与当前运算符‘）’相对应，故要出栈，一同释放栈顶算符‘×’比当前运