数据结构-堆栈

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

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

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

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

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

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

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

8、是一种描述问题和解决问题的基本方法。 2 递归的基本思想问题分解：把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。 4.4堆栈的应用递归233 递归的要素递归边界条件：确定递归到何时终止，也称为递归出口；递归模式：大问题是如何分解为小问题的，也称为递归体。 4.4堆栈的应用递归244.4堆栈的应用递归递归算法int fact ( int n ) if ( n = 0 ) return 1; else return n * fact (n-1);-*=时当时当)!1(1!n1n1nnn例1 阶乘函数254.4堆栈的应用递归

9、递归的经典问题汉诺塔问题 在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。264.4堆栈的应用递归汉诺塔问题的递归求解:如果 n = 1，则将这一个盘子直接从 塔A移到塔 C 上。否则，执行以下三步： 将塔A上的n-1个碟子借助塔C先移到塔B上； 把塔A上剩下的一个碟子移到塔C上； 将n-1个碟

10、子从塔B借助于塔A移到塔C上。 274.4堆栈的应用递归284.4堆栈的应用递归 void Hanoi(int n, char A, char B, char C) if (n=1) Move(A, C); else Hanoi(n-1, A, C, B); Move(A, C); Hanoi(n-1, B, A, C); 294.4堆栈的应用递归递归函数的内部执行过程 运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址； 每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈； 每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复

11、为调用前的值，然后转向返回地址指定的位置继续执行。30Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move (A,C)Move (A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move (C,B)Hanio(1,C,A,B)Move (A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move (B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move (A,C)Hanio(2,B,A,C)Move (B,A)Hanio(1,A,B,C)结束314.4堆栈的应用表达式求值中缀表达

12、式后缀表达式后缀表达式特点后缀表达式中不出现括号后缀表达式与中缀表达式的运算对象的先后次序相同，只是所读到的运算符的先后次序可能有所改变324.4堆栈的应用表达式求值后缀表达式实例ABCE/-E*+ 对应中缀表达式 A+(B-C/D)*E(2)ABCD/F*-E*+X+对应中缀表达式A+(B-C/D*F)*E+X334.4堆栈的应用后缀表达式求值后缀表达式计算算法：Procedure EVAL(E) /E为后缀表达式top0loopx NEXT_TOKEN(E)case:x=“#”:return:x=运算对象:call PUSH(STACK,M,top,x):else: 从堆栈中取出相应的运算

13、对象进行由x执行的运算并将结果入栈endforeverend344.4堆栈的应用中缀表达式转换算法思想p81-82关键点：运算符堆栈运算符优先关系表354.4堆栈的应用中缀表达式转换运算优先级当前运算符栈顶运算符364.4堆栈的应用中缀表达式转换算法： /将中缀表达式E转换为后缀表达式Procedure POSTFIX(E)STACK1=“#”top1loopx NEXT_TOKEN(E)case:x=“#”:while top1 doprint(STACKtop) /输出栈顶运算符call POP(STATCK,top) /退栈endprint(“#”);return:x是运算对象:print(x)/直接输出运算对象endforeverend374.4堆栈的应用中缀表达式转换:x=“）”