资源描述：
《数据结构 3章栈和队.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2010-7-21数据结构第三章栈和队列引言：对线性表L=(a1,a2,,...,an),可在任意第i(i=1,2,,...n,n+1)个位置插入新元素，或删除任意第i(i=1,2,,...n)个元素受限数据结构----插入和删除受限制的线性表。1.栈(stack),2.队列(queue).3.1栈(stack)3.1.1栈的定义和操作1.定义和术语▲栈----限定在表尾作插入、删除操作的线性表。(a1,a2,,...，an）←插入元素(进栈)↑↑↘删除元素(出栈）表头表尾(栈底)(栈顶）ana1栈顶(top)栈
2、底(bottom)出栈(pop)进栈(push)▲进栈----插入一个元素到栈中。或:入栈、推入、压入、push。▲出栈----从栈删除一个元素。或：退栈、上托、弹出、pop。▲栈顶----表中允许插入、删除元素的一端(表尾)。▲栈顶元素----处在栈顶位置的元素。▲栈底----表中不允许插入、删除元素的一端。▲空栈----不含元素的栈。栈的示意图▲栈的元素的进出原则:“后进先出”,“LastInFirstOut”。▲栈的别名:“后进先出”表、“LIFO”表、反转存储器、地窖。2.栈的基本操作(1)Initsta
3、ck(s)----置s为空栈。(2)Push(s,e)----元素e进栈s。若s已满，则发生溢出。若不能解决溢出，重新分配空间失败，则插入失败。(3)Pop(s,e)----删除栈s的顶元素，并送入e。若s为空栈,发生“下溢”(underflow)；为空栈时，表示某项任务未开始或已完成。(4)Gettop(s,e)----栈s的顶元素拷贝到e。若s为空栈，则结束拷贝。(5)Empty(s)----判断s是否为空栈。若s为空栈,则Empty(s)为true；否则为false。(1)输入A,B,C,产生输出A,B,C
4、的过程：AB,C(1)A进栈B,C(2)A出栈BC(3)B进栈(4)B出栈C(5)C进栈(6)C出栈CA,B,CAA,BA,BA(2)输入A,B,C,产生输出C,B,A的过程：AB,C(1)A进栈BAC(2)B进栈CBA(3)C进栈BA(4)C出栈C(5)B出栈(6)A出栈C,B,ACC,B(3)输入A,B,C,产生输出B,C,A的过程:AB,C(1)A进栈BAC(2)B进栈AC(3)B出栈CA(4)C进栈A(5)C出栈(6)A出栈B,C,ABB,CB当A,B,C依次进栈，C出栈后，由于栈顶元素是B,栈底元素是A
5、,而A不能先于B出栈,所以不能在输出序列中,使A成为C的直接后继,即不可能由输入A,B,C产生输出C,A,B。一般地，输入序列(...,ai,...,aj,...,ak,...)到栈中,不能得到输出序列(...,ak,...,ai,...,aj,...)。(1)初始状态CBA(2)A,B,C进栈BA(3)C出栈CA,B,C(4)输入A,B,C,不能产生输出C,A,B:设依次输入元素A,B,C到栈中,可得哪几种输出?设依次输入元素C,B,A到栈中,可得哪几种输出?A,B,C(1)A,B,C(2)A,C,B(3)B,
6、A,C(4)B,C,A(5)C,A,B(6)C,B,AC,B,A(1)A,B,C(2)A,C,B(3)B,A,C(4)B,C,A(5)C,A,B(6)C,B,A讨论：假定输入元素A,B,C,D到栈中,能得当哪几种输出?不能得到哪几种输出序列？(1)A,B,C,D(7)B,A,C,D(13)C,A,B,D(19)D,B,C,A(2)A,B,D,C(8)B,A,D,C(14)C,A,D,B(20)D,B,A,C(3)A,C,B,D(9)B,C,A,D(15)C,B,A,D(21)D,C,B,A(4)A,C,D,B(1
7、0)B,C,D,A(16)C,B,D,A(22)D,C,A,B(5)A,D,B,C(11)B,D,A,C(17)C,D,A,B(23)D,A,B,C(6)A,D,C,B(12)B,D,C,A(18)C,D,B,A(24)D,A,C,B共5+5+3+1=14种输出序列。A,B,C,D输入输出5种5种3种1种顺序栈的基本操作及算法：顺序栈的类型定义如下所示：#defineSackSize100typedefstruct{Datatypedata[SackSize];inttop;}SeqStack定义一个指向顺序栈的
8、指针：SeqStack*s;3.1.2栈的存储表示和操作实现1.顺序栈----用顺序空间表示的栈。假设栈空间为data[0..SackSize-1](1)顶指针指向顶元素所在位置：top→栈顶指针栈顶栈底SackSize-1n10//////////////////SackSize-110-1自由区自由区(a)非空栈(b)空栈,s→top==-1若删除元素，将发生“下溢”
