数据结构_堆栈.ppt

《数据结构_堆栈.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章堆栈和队列提纲4.1堆栈的概念及其运算4.2堆栈的顺序存储结构4.3堆栈的链式存储结构4.4堆栈的应用4.1堆栈的概念及其运算堆栈的逻辑结构堆栈：限定仅在表尾进行插入和删除操作的线性表。空栈：不含任何数据元素的栈。允许插入和删除的一端称为栈顶，另一端称为栈底。（a1,a2,……,an）栈顶栈底abc入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈顶栈的示意图4.1堆栈的概念及其运算栈的操作特性：后进先出4.1堆栈的概念及其运算例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶c栈顶

2、情况1：出栈序列：c出栈序列：c、b出栈序列：c、b、a例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶情况2：出栈序列：b4.1堆栈的概念及其运算栈底a出栈序列：b出栈序列：b、c出栈序列：b、c、ac栈顶栈顶注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。情况2：例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？4.1堆栈的概念及其运算堆栈的操作Push(S,x)Pop(S)Empty(S)Top(S)Create

3、(S)4.1堆栈的概念及其运算如何改造数组实现栈的顺序存储？012345678a1确定用数组的哪一端表示栈底。附设指针top指示栈顶元素在数组中的位置。top4.2堆栈的顺序存储结构出栈：top减1进栈：top加1栈空：top=-1012345678a1topa2topa3top栈满：top=MAX_SIZE4.2堆栈的顺序存储结构堆栈是否为空测试算法p70进栈算法p71退栈算法4.2堆栈的顺序存储结构解决方案1：直接解决：为每个栈开辟一个数组空间。解决方案2：顺序栈单向延伸——使用一个数组来存储两个栈在一个程序中需要同时使用具有相同数据类型的两个栈，如何顺

4、序存储这两个栈？会出现什么问题？如何解决？4.2堆栈的顺序存储结构两栈共享空间：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。4.2堆栈的顺序存储结构栈1的底固定在下标为0的一端；栈2的底固定在下标为MaxSize-1的一端。top1和top2分别为栈1和栈2的栈顶指针；MaxSize为整个数组空间的大小（图中用S表示）；a1a2…aitop1012……S-1top2bj……b2b1栈1底栈2底4.2堆栈的顺序存储结构top1=-1什么时候栈1为空？a1a2…aitop1012……S-1t

5、op2bj……b2b1top14.2堆栈的顺序存储结构top1=-1什么时候栈1为空？a1a2…aitop1012……S-1top2bj……b2b1什么时候栈2为空？top2top2=MaxSize4.2堆栈的顺序存储结构top1=-1什么时候栈1为空？a1a2……aitop1012……S-1top2bj……b2b1什么时候栈2为空？top2=MaxSize什么时候栈满？top2=top1+14.2堆栈的顺序存储结构1.如果栈满，则抛出上溢异常；2.判断是插在栈1还是栈2；2.1若在栈1插入，则2.1.1top1加1;2.1.2在top1处填入x；2.2若在

6、栈2插入，则2.2.1top2减1;2.2.2在top2处填入x；操作接口：voidPush(inti,Tx);4.2堆栈的顺序存储结构1.若是在栈1删除，则1.1若栈1为空栈，抛出下溢异常；1.2删除并返回栈1的栈顶元素；2.若是在栈2删除，则2.1若栈2为空栈，抛出下溢异常；2.2删除并返回栈2的栈顶元素；操作接口：TPop(inti);4.2堆栈的顺序存储结构heada1a2an∧ai链栈需要加头结点吗？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将链头作为栈顶，方便操作。链栈不需要附设头结点。4.3堆栈的链式存储结构栈顶栈底链栈：栈的链接存储结构

7、topanan-1a1∧heada1a2an∧ai两种示意图在内存中对应同一种状态topa1an-1an∧栈顶栈底4.3堆栈的链式存储结构4.3堆栈的链式存储结构入栈：p75出栈：p75操作接口：4.3堆栈的链式存储结构顺序栈和链栈的比较时间性能：相同，都是常数时间O(1)。空间性能：顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。1递归的定义子程序（或函数）直接调用自己或通

8、过一系列调用语句间接调用自己，是一种描述问题和解决问