第第三三章章 栈与队列栈与队列东南大学计算机学院东南大学计算机学院 方效林方效林本课件借鉴了清华大学殷人昆老师和哈尔滨工业大学张岩老师的课件本章主要内容本章主要内容n栈栈n栈的应用：表达式求值栈的应用：表达式求值n栈与递归栈与递归n队列队列n队列的应用：电路布线队列的应用：电路布线2栈栈n定义：只允许在表的末端进行插入和删除的线定义：只允许在表的末端进行插入和删除的线性表性表n特点：先进后出特点：先进后出n栈的操作栈的操作r进栈进栈 push()r出栈出栈 pop()r栈顶栈顶 top()r置空置空 setEmpty()r判断是否为空判断是否为空 isEmpty()r栈满栈满 isFull()3栈栈n栈的数组表示栈的数组表示n栈的操作栈的操作r进栈进栈 push()r出栈出栈 pop()r栈顶栈顶 top()r置空置空 makeEmpty()r判断是否为空判断是否为空 isEmpty()r栈满栈满 isFull()4topabtopctop空栈空栈top栈栈n栈的单链表表示栈的单链表表示r栈的数组表示可能栈满栈的数组表示可能栈满r栈的单链表表示无栈满问题栈的单链表表示无栈满问题r入栈在表头进行插入操作入栈在表头进行插入操作r出栈在表头进行删除操作出栈在表头进行删除操作5topcbanull栈栈n进栈顺序为进栈顺序为(1,2,3)，出栈顺序能否为，出栈顺序能否为(3,1,2)?r不能，不能，3出栈时，说明出栈时，说明2和和1都在栈里，而且都在栈里，而且2必须必须先于先于1出栈出栈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中缀表达式：中缀表达式：A + B * ( C - D ) - E / Fn后缀表达式：后缀表达式：A B C D - * + E F / -n表达式中相邻两个操作符的计算次序为：表达式中相邻两个操作符的计算次序为：r优先级高的先计算；优先级高的先计算；r优先级相同的自左向右计算；优先级相同的自左向右计算；r当使用括号时从最内层括号开始计算。当使用括号时从最内层括号开始计算。n前缀和中缀表达式求值需要两个栈；后缀表达前缀和中缀表达式求值需要两个栈；后缀表达式求值只需一个栈，相对简单些。式求值只需一个栈，相对简单些。8栈的应用：表达式求值栈的应用：表达式求值n从左向右扫描表达式，用一个栈暂存扫描到的从左向右扫描表达式，用一个栈暂存扫描到的操作数或计算结果。操作数或计算结果。n后缀表达式的计算顺序中已隐含了加括号的优后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现先次序，括号在后缀表达式中不出现9R1R2 2R3R4R5A B C D - * + E F / -R1R2 2R3R4R5A+B*(C-D)-E/F中缀表达式：中缀表达式：后缀表达式：后缀表达式：10作业：作业：写出下列中缀表达式的后缀表达式写出下列中缀表达式的后缀表达式1.A*B*C2.-A+B-C+D3.A*(-B)+C4.(A+B)*D+E/(F+A*D)+C5.A&B|!(EF)6.!(A & !(BD) | (CE)栈的应用：表达式求值栈的应用：表达式求值n后缀表达式求值过程后缀表达式求值过程r顺序扫描后缀表达式每一项顺序扫描后缀表达式每一项r若该项是若该项是操作数操作数，则进栈，则进栈r若该项是若该项是操作符操作符，若是单目运算符，则出栈一个操作数若是单目运算符，则出栈一个操作数X，并将计算结，并将计算结果果X进栈进栈若是双目运算符，则连续出栈两个操作数若是双目运算符，则连续出栈两个操作数X和和Y，并将，并将计算结果计算结果X Y进栈进栈r当表达式的所有项都扫描并处理完后，栈顶存放的当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。就是最后的计算结果。11栈的应用：表达式求值栈的应用：表达式求值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退栈，计算退栈，计算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+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-操作符操作符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后缀表达式求值过程：后缀表达式求值过程：栈的应用：表达式求值栈的应用：表达式求值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退栈，计算退栈，计算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=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-操作符操作符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后缀表达式求值过程：后缀表达式求值过程：栈的应用：表达式求值栈的应用：表达式求值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退栈，计算退栈，计算R5=R3-R4进栈进栈R5A B C D - * + E F / -R3=A+R2R4=E/FtoptopR5=R3-R4空栈空栈top后缀表达式求值过程：后缀表达式求值过程：栈的应用：表达式求值栈的应用：表达式求值n中缀表达式转换为后缀表达式中缀表达式转换为后缀表达式r使用栈将中缀表达式转换成前缀或后缀表达式。使用栈将中缀表达式转换成前缀或后缀表达式。r为了实现转换，需要考虑各操作符的优先级。为了实现转换，需要考虑各操作符的优先级。结束符结束符“#”优先级最低优先级最低左括号左括号“(”栈外优先级最高，进栈后极低栈外优先级最高，进栈后极低右括号右括号“)”栈外优先级极低栈外优先级极低其他进栈后优先级加其他进栈后优先级加1，这可满足自左向右计算要求，这可满足自左向右计算要求19各个算术操作符的优先级各个算术操作符的优先级操作符操作符#(* / %+ - )isp(栈内优先级栈内优先级)01536icp(栈外优先级栈外优先级)06421栈的应用：表达式求值栈的应用：表达式求值n中缀表达式转换为后缀表达式算法中缀表达式转换为后缀表达式算法r操作符栈初始化，结束符操作符栈初始化，结束符#进栈，读入中缀表达式进栈，读入中缀表达式的首字符的首字符chr重复执行以下步骤，直到重复执行以下步骤，直到ch=#，同时栈顶操作符，同时栈顶操作符也是也是#，停止循环，停止循环若若ch是操作数直接输出，读入下一字符是操作数直接输出，读入下一字符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(+), 进栈进栈# +A3B操作数操作数# + AB4*操作符操作符isp(+) icp(*), 进栈进栈# + *AB5(操作符操作符isp(*) icp( ( ), 进栈进栈# + * (AB6C操作数操作数# + * (ABC7-操作符操作符isp( ( ) icp( ) ), 退栈退栈# + * (ABCDisp( ) = icp( ), 退栈退栈# + *ABCD-中缀表示转换为后缀表示过程：中缀表示转换为后缀表示过程：ABCD-*+EF/-)(AC后缀输出：后缀输出：#+toptop空栈空栈top*（-toptoptopB栈的应用：表达式求值栈的应用：表达式求值 22步步输入输入类型类型动作动作栈内容栈内容后缀输出后缀输出0#进栈进栈#1A操作数操作数# A 2+操作符操作符isp(#) icp(+), 进栈进栈# +A3B操作数操作数# + AB4*操作符操作符isp(+) icp(*), 进栈进栈# + *AB5(操作符操作符isp(*) icp( ( ), 进栈进栈# + * (AB6C操作数操作数# + * (ABC7-操作符操作符isp( ( ) icp( ) ), 退栈退栈# + * (ABCDisp( ( ) = icp( ) ), 退栈退栈# + *ABCD-中缀表示转换为后缀表示过程：中缀表示转换为后缀表示过程：ABCD-*+EF/-)(A B C D -后缀输出：后缀输出：#+*（-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(-), 退栈退栈# + 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 *link;栈与递归栈与递归n问题解法是递归的问题解法是递归的r例如，汉诺塔例如，汉诺塔 (Tower of Hanoi) 问题的解法问题的解法有有3根标号为根标号为A、B、C的柱子，的柱子，A柱上又叠着柱上又叠着64个从小个从小到大排放的盘子。目的是要将到大排放的盘子。目的是要将A柱的盘子全部移到柱的盘子全部移到C柱柱上。移动条件是一次只能移动一个盘子，移动过程中上。移动条件是一次只能移动一个盘子，移动过程中大盘子不能放在小盘子上面大盘子不能放在小盘子上面r求解汉诺塔问题的递归算法求解汉诺塔问题的递归算法若若 n = 1，将盘子直接从，将盘子直接从 A 柱移到柱移到 C 柱。柱。否则，执行以下三步：否则，执行以下三步：用 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 ( move %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; 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 = 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,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用栈将递归转换为非递归用栈将递归转换为非递归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,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内任意两点的边都在内任意两点的边都在P内内寻找凸包寻找凸包nGraham-scan的基本思想的基本思想r找到最下最左顶点，其他顶点与它连线找到最下最左顶点，其他顶点与它连线r按夹角从小到大排序按夹角从小到大排序r夹角最小的开始，寻找凸包点夹角最小的开始，寻找凸包点39寻找凸包寻找凸包nGraham-scan的基本思想的基本思想p p0 0p p2 2p p1 1p p7 7p p8 8p p6 6p p5 5p p4 4p p3 3p p1010p p9 9寻找凸包寻找凸包nGraham-scan的基本思想的基本思想p p0 0p p2 2p p1 1p p7 7p p8 8p p6 6p p5 5p p4 4p p3 3p p1010p p9 9寻找凸包寻找凸包nGraham-scan的基本思想的基本思想p p0 0p p2 2p p1 1p p7 7p p8 8p p6 6p p5 5p p4 4p p3 3p p1010p p9 9寻找凸包寻找凸包nGraham-scan的基本思想的基本思想p p0 0p p2 2p p1 1p p7 7p p6 6p p8 8p p5 5p p4 4p p3 3p p1010p p9 9寻找凸包寻找凸包nGraham-scan的基本思想的基本思想p p0 0p p2 2p p1 1p p7 7p p6 6p p8 8p p5 5p p4 4p p3 3p p1010p p9 9寻找凸包寻找凸包nGraham-scan的基本思想的基本思想p p0 0p p2 2p p1 1p p7 7p p6 6p p8 8p p5 5p p4 4p p3 3p p1010p p9 9寻找凸包寻找凸包nGraham-scan的基本思想的基本思想p p0 0p p2 2p p1 1p p7 7p p6 6p p8 8p p5 5p p4 4p p3 3p p1010p p9 9寻找凸包寻找凸包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定义定义r队列是只允许在一端删除，在另一端插入的线性表队列是只允许在一端删除，在另一端插入的线性表r允许删除的一端叫做队头允许删除的一端叫做队头 (front)，允许插入的一，允许插入的一端叫做队尾端叫做队尾 (rear)。n特点：先进先出特点：先进先出n队列的操作队列的操作r入队入队 EnQueue()r出队出队 DeQueue()r判断是否为空判断是否为空 isEmpty()r队列满队列满 isFull()48队列队列n队列的数组表示队列的数组表示 r入队：在入队：在rear 位置加入数据，位置加入数据，rear = rear + 1r出队：在出队：在front位置取出数据，位置取出数据，front = front + 149ABCDEFfrontrear空队列空队列A入队入队B、C入队入队A出队出队B出队出队D、E、F入队入队rearrearrearfront front队列队列n队列的数组表示队列的数组表示 (循环队列循环队列)r入队：在入队：在rear 处加入数据，处加入数据，rear=(rear+1)%SIZEr出队：在出队：在front处取出数据，处取出数据，front=(front+1)%SIZEr队满：队满：(rear+1)%SIZE = frontr队空：队空：rear = front5012345670DEFGH ABC空队列空队列A入队入队B、C、D入队入队A、B出队出队E、F、G、H、I入队入队rearfrontrearrearfrontI队列队列n队列的单链表表示队列的单链表表示r队列的数组表示可能队列满队列的数组表示可能队列满r队列的单链表表示无队列满问题队列的单链表表示无队列满问题r入队在表尾进行插入操作入队在表尾进行插入操作r出队在表头进行删除操作出队在表头进行删除操作51ABCnullfrontrear打印二项展开式打印二项展开式 (a+b)i 的系数的系数n杨辉三角形杨辉三角形52(a+b)1=a+b(a+b)2=a2+2ab+b2(a+b)3=a3+3a2b+3ab2+b3打印二项展开式打印二项展开式 (a+b)i 的系数的系数n第第i行与第行与第i+1行关系行关系53i = 2i = 3i = 40 1 3 3 1 01 4 6 4 10 1 2 1 00 1 1 0打印二项展开式打印二项展开式 (a+b)i 的系数的系数540012101113310出队列时与前一个出队列的数相加，结果入队列出队列时与前一个出队列的数相加，结果入队列0作为被加数时，作为被加数时，0入队列，作为分隔符入队列，作为分隔符队列的应用：电路布线队列的应用：电路布线n找最短路径找最短路径n网格方式布线，布线不能有重叠，转弯用直角网格方式布线，布线不能有重叠，转弯用直角55(0,0)(0,1)(0,2)(0,3)(1,0)(1,1)(1,2)(1,3)(2,0)(2,1)(2,2)(2,3)(3,0)(3,1)(3,2)(3,3)起点起点终点终点已布线已布线队列的应用：电路布线队列的应用：电路布线n找最短路径找最短路径56(0,0)(0,1)(0,2)(0,3)(1,0)(1,1)(1,2)(1,3)(2,0)(2,1)(2,2)(2,3)(3,0)(3,1)(3,2)(3,3)起点起点终点终点已布线已布线(1,1)(0,1)(1,0)(2,1)(2,0)(3,1)(3,0)(3,2)(3,3)frontrear已访问已访问rearrear rearrear rear rear rearfront front front front front front front front frontnull(1,1)(1,1)(1,1)(1,0)(2,1)(2,0)(3,1)(3,2)