Ch3.栈和队列-栈.ppt

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

1、第三章栈和队列3.1栈3.1.1抽象数据类型栈的定义3.1.2顺序栈3.1.3链栈本章节的基本内容是：1栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出（LIFO）或下推表。3.1.1栈的定义及基本运算2栈的逻辑结构空栈：不含任何

2、数据元素的栈。（a1,a2,……,an）栈：限定仅在表尾进行插入和删除操作的线性表。栈顶栈底允许插入和删除的一端称为栈顶，另一端称为栈底。3a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈顶栈的示意图4栈的操作特性：后进先出a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈的示意图5例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶c栈顶情况1：栈的逻辑结构6栈底栈顶ab栈顶c栈顶出栈序列：c出栈序列：c、b出栈序列：c、b、a例：有三个元素按a

3、、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构情况1：7栈底栈顶ab栈顶出栈序列：b情况2：例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构8栈底a出栈序列：b出栈序列：b、c出栈序列：b、c、ac栈顶栈顶注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构情况2：9栈的抽象数据类型定义ADTStack{Data栈中

4、元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系OperationInitStack(S)构造一个空栈Push(S,x)在栈顶插入一个元素x,如果插入不成功，抛出异常;否则栈顶增加了一个元素。10Pop（S,e）删除栈顶元素,如果删除成功，返回被删元素值e，否则，抛出异常;否则栈减少了一个元素.Stacktop(S,e)读取当前的栈顶元素,若栈不空，返回当前的栈顶元素值e,栈不变.Stackempty(S)判断栈S是否非空，空返回1，非空返回0。}ADTStack栈的抽象数据类型定义11由于栈是运算受限的线性表，因此线性表的存储结构对栈也适

5、应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。3.1.2顺序栈12栈的顺序存储结构及实现顺序栈——栈的顺序存储结构如何改造数组实现栈的顺序存储？012345678a1确定用数组的哪一端表示栈底。附设指针top指示栈顶元素在数组中的位置。top3.1.2顺序栈13出栈：top减1进栈：top加1栈空：top=-1012345678a1

6、topa2topa3top栈满：top=MAX_SIZE-1栈的顺序存储结构及实现3.1.2顺序栈14因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下：#defineStackSize100typedefchardatatype;typedefstruct{datatypedata[stacksize];inttop;}seqstack;顺序栈的类型定义15设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即s–>data[0]是栈底元素，那么栈顶指针s–>top是正向增加的，即进栈时需将s–>

7、top加1，退栈时需将s–>top减1。因此，s–>top<0表示空栈，s–>top=stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。为了避免溢出，在对栈进行进栈和出展运算前，应分别判断栈是否已满或者是否已空。161、置空栈voidinitstack(seqstack*s){s–>top=-1;}//initstack172、判断栈空intstackempty(seqstack*s){return(s–>top==-1);}//stackempty183、判断栈满in

8、tstackfull(seqstack*s){return(s–>top==stacksize-1);}19