栈满isFull一东南大学计算机科学与工程学院

1、栈满isFull一东南大学计算机科学与工程学院本章主要内容本章主要内容n栈栈n栈的应用：表达式求值栈的应用：表达式求值n栈与递归栈与递归n队列队列n队列的应用：电路布线队列的应用：电路布线2栈栈n定义：只允许在表的末端进行插入和删除的线性定义：只允许在表的末端进行插入和删除的线性表表n特点：先进后出特点：先进后出n栈的操作栈的操作n进栈进栈 push三三n出栈出栈 pop三三n栈顶栈顶 top三三n置空置空 setEmpty三三n判断是否为空判断是否为空 isEmpty三三n栈满栈满 isFull三三3栈栈n栈的数组表示栈的数组表示n栈的操作栈的操作n进栈进栈 push三三n出栈出栈 pop三

2、三n栈顶栈顶 top三三n置空置空 makeEmpty三三n判断是否为空判断是否为空 isEmpty三三n栈满栈满 isFull三三4topabtopctop空栈空栈top栈栈n栈的单链表表示栈的单链表表示r栈的数组表示可能栈满栈的数组表示可能栈满r栈的单链表表示无栈满问题栈的单链表表示无栈满问题r入栈在表头进行插入操作入栈在表头进行插入操作r出栈在表头进行删除操作出栈在表头进行删除操作5topcbanull栈栈n进栈顺序为进栈顺序为(1,2,3)，出栈顺序能否为，出栈顺序能否为(3,1,2)?r不能，不能，3出栈时，说明出栈时，说明2和和1都在栈里，而且都在栈里，而且2必须先于必须先于1出栈

3、出栈6321top作业：作业：1，2，3，4，5，6依次进栈，若出栈顺序为依次进栈，若出栈顺序为2，3，4，6，5，1则栈大小至少为多少？则栈大小至少为多少？栈的应用：表达式求值栈的应用：表达式求值n一个表达式由操作数一个表达式由操作数(亦称运算对象亦称运算对象)、操作符、操作符 (亦亦称运算符称运算符) 和分界符组成。和分界符组成。n算术表达式三种表示算术表达式三种表示r中缀中缀(infix)表示表示 ，如，如 A+B；r前缀前缀(prefix)表示表示 ，如，如 +AB；r后缀后缀(postfix)表示表示 ，如，如 AB+；7栈的应用：表达式求值栈的应用：表达式求值n中缀表达式：中缀表达

4、式：A + B * ( C - D ) - E / Fn后缀表达式：后缀表达式：A B C D - * + E F / -n表达式中相邻两个操作符的计算次序为：表达式中相邻两个操作符的计算次序为：r优先级高的先计算；优先级高的先计算；r优先级相同的自左向右计算；优先级相同的自左向右计算；r当使用括号时从最内层括号开始计算。当使用括号时从最内层括号开始计算。n前缀和中缀表达式求值需要两个栈；后缀表达式求值前缀和中缀表达式求值需要两个栈；后缀表达式求值只需一个栈，相对简单些。只需一个栈，相对简单些。8栈的应用：表达式求值栈的应用：表达式求值n从左向右扫描表达式，用一个栈暂存扫描到的操作数从左向右扫

5、描表达式，用一个栈暂存扫描到的操作数或计算结果。或计算结果。n后缀表达式的计算顺序中已隐含了加括号的优先次序后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现，括号在后缀表达式中不出现9R1R2 2R3R4R5A B C D - * + E F / -R1R2 2R3R4R5A+B*(C-D)-E/F中缀表达式：中缀表达式：后缀表达式：后缀表达式：10作业：作业：写出下列中缀表达式的后缀表达式写出下列中缀表达式的后缀表达式A*B*C-A+B-C+DA*(-B)+C(A+B)*D+E/(F+A*D)+CA&B|!(EF)1.!(A & !(BD) | (CE

6、)栈的应用：表达式求值栈的应用：表达式求值n后缀表达式求值过程后缀表达式求值过程r顺序扫描后缀表达式每一项顺序扫描后缀表达式每一项r若该项是操作数，则进栈若该项是操作数，则进栈r若该项是操作符若该项是操作符，若是单目运算符，则出栈一个操作数若是单目运算符，则出栈一个操作数X，并将计算结果，并将计算结果X进栈进栈若是双目运算符，则连续出栈两个操作数若是双目运算符，则连续出栈两个操作数X和和Y，并将计算，并将计算结果结果X Y进栈进栈r当表达式的所有项都扫描并处理完后，栈顶存放的就是当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。最后的计算结果。11栈的应用：表达式求值栈的应用：表

7、达式求值12步步输入输入类型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作符操作符D、C退栈，计算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=A+R2进栈进栈R39E操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计

8、算退栈，计算R5=R3-R4进栈进栈R5top空栈空栈topBACDtoptoptopA B C D - * + E F / -后缀表达式求值过程：后缀表达式求值过程：栈的应用：表达式求值栈的应用：表达式求值13步步输入输入类型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作符操作符D、C退栈，计算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=A+

9、R2进栈进栈R39E操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计算退栈，计算R5=R3-R4进栈进栈R5BACDtoptoptopR1=C-DA B C D - * + E F / -后缀表达式求值过程：后缀表达式求值过程：栈的应用：表达式求值栈的应用：表达式求值14步步输入输入类型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作符

10、操作符D、C退栈，计算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=A+R2进栈进栈R39E操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计算退栈，计算R5=R3-R4进栈进栈R5BAtopR1=C-DtoptopA B C D - * + E F / -R2=B*R1后缀表达式求值过程：后缀表达式求值过程：栈的应用：表达式求值栈的应用：表达式求

11、值15步步输入输入类型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作符操作符D、C退栈，计算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=A+R2进栈进栈R39E操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计算退栈

12、，计算R5=R3-R4进栈进栈R5AtoptopA B C D - * + E F / -R2=B*R1R3=A+R2空栈空栈top后缀表达式求值过程：后缀表达式求值过程：栈的应用：表达式求值栈的应用：表达式求值16步步输入输入类型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作符操作符D、C退栈，计算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=

13、A+R2进栈进栈R39E操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计算退栈，计算R5=R3-R4进栈进栈R5toptopA B C D - * + E F / -R3=A+R2EFtop后缀表达式求值过程：后缀表达式求值过程：栈的应用：表达式求值栈的应用：表达式求值17步步输入输入类型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作

14、符操作符D、C退栈，计算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=A+R2进栈进栈R39E操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计算退栈，计算R5=R3-R4进栈进栈R5A B C D - * + E F / -R3=A+R2EFtopR4=E/Ftoptop后缀表达式求值过程：后缀表达式求值过程：栈的应用：表达式求值栈的应用：表达式

15、求值18步步输入输入类型类型动作动作栈中内容栈中内容1置空栈置空栈2A操作数操作数进栈进栈A3B操作数操作数进栈进栈A B4C操作数操作数进栈进栈A B C5D操作数操作数进栈进栈A B C D6-操作符操作符D、C退栈，计算退栈，计算R1=C-D进栈进栈A B R17*操作符操作符R1、B退栈，计算退栈，计算R2=B*R1进栈进栈A R28+操作符操作符R2、A退栈，计算退栈，计算R3=A+R2进栈进栈R39E操作数操作数进栈进栈R3 E10F操作数操作数进栈进栈R3 E F11/操作符操作符F、E退栈，计算退栈，计算R4=E / F进栈进栈R3 R412-操作符操作符R4、R3退栈，计算退

16、栈，计算R5=R3-R4进栈进栈R5A B C D - * + E F / -R3=A+R2R4=E/FtoptopR5=R3-R4空栈空栈top后缀表达式求值过程：后缀表达式求值过程：栈的应用：表达式求值栈的应用：表达式求值n中缀表达式转换为后缀表达式中缀表达式转换为后缀表达式r使用栈将中缀表达式转换成前缀或后缀表达式。使用栈将中缀表达式转换成前缀或后缀表达式。r为了实现转换，需要考虑各操作符的优先级。为了实现转换，需要考虑各操作符的优先级。结束符结束符“#”优先级最低优先级最低左括号左括号“(”栈外优先级最高，进栈后极低栈外优先级最高，进栈后极低右括号右括号“)”栈外优先级极低栈外优先级极

17、低其他进栈后优先级加其他进栈后优先级加1，这可满足自左向右计算要求，这可满足自左向右计算要求19各个算术操作符的优先级各个算术操作符的优先级操作符操作符#(* / %+ - )isp(栈内优先级栈内优先级)01536icp(栈外优先级栈外优先级)06421栈的应用：表达式求值栈的应用：表达式求值n中缀表达式转换为后缀表达式算法中缀表达式转换为后缀表达式算法r操作符栈初始化，结束符操作符栈初始化，结束符#进栈，读入中缀表达式的首字进栈，读入中缀表达式的首字符符chr重复执行以下步骤，直到重复执行以下步骤，直到ch=#，同时栈顶操作符也是，同时栈顶操作符也是#，停止循环停止循环若若ch是操作数直接

18、输出，读入下一字符是操作数直接输出，读入下一字符ch若若ch是操作符，比较是操作符，比较ch和栈顶操作符和栈顶操作符op优先级：优先级：若icp(ch) isp(op)，令ch进栈，读入下一字符ch若icp(ch) isp(op)，退栈，并输出若icp(ch)=isp(op)，退栈不输出；若退出的是(，则读入下一个字符chr算法结束，输出序列即为所得后缀表达式算法结束，输出序列即为所得后缀表达式20栈的应用：表达式求值栈的应用：表达式求值 21步步输入输入类型类型动作动作栈内容栈内容后缀输出后缀输出0#进栈进栈#1A操作数操作数# A 2+操作符操作符isp(#) icp(+), 进栈进栈#

19、+A3B操作数操作数# + AB4*操作符操作符isp(+) icp(*), 进栈进栈# + *AB5(操作符操作符isp(*) icp( ( ), 进栈进栈# + * (AB6C操作数操作数# + * (ABC7-操作符操作符isp( ( ) icp( ) ), 退栈退栈# + * (ABCDisp( ) = icp( ), 退栈退栈# + *ABCD-中缀表示转换为后缀表示过程：中缀表示转换为后缀表示过程：ABCD-*+EF/-)(AC后缀输出：后缀输出：#+toptop空栈空栈top*（-toptoptopB栈的应用：表达式求值栈的应用：表达式求值 22步步输入输入类型类型动作动作栈内容

20、栈内容后缀输出后缀输出0#进栈进栈#1A操作数操作数# A 2+操作符操作符isp(#) icp(+), 进栈进栈# +A3B操作数操作数# + AB4*操作符操作符isp(+) icp(*), 进栈进栈# + *AB5(操作符操作符isp(*) icp( ( ), 进栈进栈# + * (AB6C操作数操作数# + * (ABC7-操作符操作符isp( ( ) icp( ) ), 退栈退栈# + * (ABCDisp( ( ) = icp( ) ), 退栈退栈# + *ABCD-中缀表示转换为后缀表示过程：中缀表示转换为后缀表示过程：ABCD-*+EF/-)(AB CD-后缀输出：后缀输出：#

21、+*（-toptoptop栈的应用：表达式求值栈的应用：表达式求值 23步步输入输入类型类型动作动作栈内容栈内容后缀输出后缀输出10-操作符操作符isp(*) icp(-), 退栈退栈# + ABCD-*isp(+) icp(-), 退栈退栈#ABCD-*+isp(#) icp(-), 进栈进栈# -ABCD-*+11E操作数操作数# -ABCD-*+E12/操作符操作符isp(-) icp(/), 进栈进栈# - /ABCD-*+E13F操作数操作数# - /ABCD-*+EF14#操作符操作符isp(/) icp(#), 退栈退栈# -ABCD-*+EF/isp(-) icp(-), 退栈

22、退栈# + ABCD-*isp(+) icp(-), 退栈退栈#ABCD-*+isp(#) icp(-), 进栈进栈# -ABCD-*+11E操作数操作数# -ABCD-*+E12/操作符操作符isp(-) icp(/), 进栈进栈# - /ABCD-*+E13F操作数操作数# - /ABCD-*+EF14#操作符操作符isp(/) icp(#), 退栈退栈# -ABCD-*+EF/isp(-) data = x) return f; else Search(f-link, x); 29a1firsta2a3annullstruct LinkNode Type data; LinkNode *

23、link;栈与递归栈与递归n问题解法是递归的问题解法是递归的r例如，汉诺塔例如，汉诺塔 (Tower of Hanoi) 问题的解法问题的解法有有3根标号为根标号为A、B、C的柱子，的柱子，A柱上又叠着柱上又叠着64个从小到大排个从小到大排放的盘子。目的是要将放的盘子。目的是要将A柱的盘子全部移到柱的盘子全部移到C柱上。移动条柱上。移动条件是一次只能移动一个盘子，移动过程中大盘子不能放在小盘件是一次只能移动一个盘子，移动过程中大盘子不能放在小盘子上面子上面r求解汉诺塔问题的递归算法求解汉诺塔问题的递归算法若若 n = 1，将盘子直接从，将盘子直接从 A 柱移到柱移到 C 柱。柱。否则，执行以下

24、三步：否则，执行以下三步：用 C 柱做过渡，将 A 柱上的(n-1) 个盘子移到 B 柱上；将 A 柱上最后一个盘子直接移到 C 柱上；用 A 柱做过渡，将 B 柱上的(n-1) 个盘子移到 C 柱上。30栈与递归栈与递归n问题解法是递归的问题解法是递归的r例如，汉诺塔例如，汉诺塔 (Tower of Hanoi) 问题的解法问题的解法31void Hanoi ( int n, char A, char B, char C ) if (n = 1) printf( move %s, A, to %s , C ); else Hanoi ( n-1, A, C, B ); printf ( mo

25、ve %s, A, to %s , C ); Hanoi ( n-1, B, A, C ); 3个圆盘的汉诺塔的移动个圆盘的汉诺塔的移动栈与递归栈与递归n问题解法是递归的问题解法是递归的r例如，汉诺塔例如，汉诺塔 (Tower of Hanoi) 问题的解法问题的解法324个圆盘的汉诺塔的移动个圆盘的汉诺塔的移动栈与递归栈与递归n用栈将递归转换为非递归用栈将递归转换为非递归r汉诺塔汉诺塔 (Tower of Hanoi) 问题的解法问题的解法33void Hanoi ( int n, char a, char b, char c) Stack S; initStack(S); Node q;

26、q.n = n; q.A = a; q.B = b; q.C = c; Push (S, q); while ( ! StackEmpty(S) ) Pop(S, q); n = q. n; a = q.A; b = q.B; c = q.C; if ( n = 1 ) printf (“Move %c”, a, “ to %c”, c); else q.n = n-1; q.A = b; q.B = a; q.C = c; Push (S, q); q.n = 1; q.A = a; q.B = b; q.C = c; Push (S, q); q.n = n-1; q.A = a; q.B

27、 = c; q.C = b; Push (S, q); Struct Node int n; char A,B,C;(3,A,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-C栈与递归栈与递归n用栈将递归转换为非递归用栈将递归转换为非递归r汉诺塔汉诺塔 (Tower of Hanoi) 问题的解法问题的解法34(3,A,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A

28、,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-Ctop(3,A,B,C)空栈空栈top栈与递归栈与递归n用栈将递归转换为非递归用栈将递归转换为非递归r汉诺塔汉诺塔 (Tower of Hanoi) 问题的解法问题的解法35(3,A,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-Ctop(1,A,B,C)(2,B,A,C)(2,A,C,B)toptop栈与递归栈与递归n用栈将递归转换为非

29、递归用栈将递归转换为非递归r汉诺塔汉诺塔 (Tower of Hanoi) 问题的解法问题的解法36(3,A,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-Ctop(1,A,B,C)(2,B,A,C)(1,C,A,B)toptop(1,A,C,B)(1,A,B,C)toptop空栈空栈top栈与递归栈与递归n用栈将递归转换为非递归用栈将递归转换为非递归r汉诺塔汉诺塔 (Tower of Hanoi) 问题的解法问题的解法37(3,A

30、,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-C(1,A,B,C)(1,B,A,C)toptop(1,B,C,A)top空栈空栈top寻找凸包寻找凸包n给定平面上给定平面上n个点的集合个点的集合Q，求，求Q的凸包的凸包38Q的的convex hull是一个凸多边形是一个凸多边形P，Q的点或者在的点或者在P上或者在上或者在P内内凸多边形凸多边形P是具有如下性质多边形：是具有如下性质多边形：连接连接P内任意两点的边都在内任意两点的边都

31、在P内内寻找凸包寻找凸包nGraham-scan的基本思想的基本思想r找到最下最左顶点，其他顶点与它连线找到最下最左顶点，其他顶点与它连线r按夹角从小到大排序按夹角从小到大排序r夹角最小的开始，寻找凸包点夹角最小的开始，寻找凸包点39寻找凸包寻找凸包nGraham-scan的基本思想的基本思想寻找凸包寻找凸包nGraham-scan的基本思想的基本思想寻找凸包寻找凸包nGraham-scan的基本思想的基本思想寻找凸包寻找凸包nGraham-scan的基本思想的基本思想寻找凸包寻找凸包nGraham-scan的基本思想的基本思想寻找凸包寻找凸包nGraham-scan的基本思想的基本思想寻找凸

32、包寻找凸包nGraham-scan的基本思想的基本思想寻找凸包寻找凸包nGraham-scan的基本思想的基本思想47Graham-scan(Q)1. 求求Q中中y-坐标值最小的点坐标值最小的点p0；2. 按照与按照与p0极角极角(逆时针方向逆时针方向)大小排序大小排序Q中其余点，中其余点， 结果为结果为；3. Push(p0, S); Push(p1, S); Push(p2, S);4. FOR i=3 TO m DO5. While Next-to-top(S)、Top(S)和和pi形成非左移动形成非左移动 Do6. Pop(S);7. Push(pi, S);8. Rerurn S；O(nlogn)O(n)O(1)O(n)总时间复杂度总时间复杂度O(nlogn)循环为什么是循环为什么是O(n)最多最多n次入栈，次入栈，那么出栈也是最多那么出栈也是最多n次次队列队列n定义定义n队列是只允许