东南大学：《数据结构》课程教学资源（PPT课件讲稿）第三章 栈与队列

第三章栈与队列 东南大学计算机学院方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件

第三章 栈与队列 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件

本章主要内容 栈 ■栈的应用:表达式求值 栈与递归 队列 队列的应用:电路布线

本章主要内容 ◼ 栈 ◼ 栈的应用：表达式求值 ◼ 栈与递归 ◼ 队列 ◼ 队列的应用：电路布线 2

■定义:只允许在表的末端进行插入和删除的线 性表 特点:先进后出 栈的操作 口进栈push 出栈pp0 口栈顶top( 置空 setEmpty() 判断是否为空 isEmpty() 口栈满 isFul(

栈 ◼ 定义：只允许在表的末端进行插入和删除的线 性表 ◼ 特点：先进后出 ◼ 栈的操作  进栈 push()  出栈 pop()  栈顶 top()  置空 setEmpty()  判断是否为空 isEmpty()  栈满 isFull() 3

栈的数组表示 ■栈的操作 进栈push0 push( 口出栈pop0 口栈顶top( 置空 makeEmpty0 top→ 判断是否为空 isEmpty0 口栈满 isFull( top→ top→空栈

栈 ◼ 栈的数组表示 ◼ 栈的操作  进栈 push()  出栈 pop()  栈顶 top()  置空 makeEmpty()  判断是否为空 isEmpty()  栈满 isFull() 4 top a top b top c top 空栈

■栈的单链表表示 栈的数组表示可能栈满 栈的单链表表示无栈满问题 口入栈在表头进行插入操作 top c 出栈在表头进行删除操作 a null

栈 ◼ 栈的单链表表示  栈的数组表示可能栈满  栈的单链表表示无栈满问题  入栈在表头进行插入操作  出栈在表头进行删除操作 5 top c b a null

a进栈顺序为(1,23),出栈顺序能否为(3,1,2)? 口不能,3出栈时,说明2和1都在栈里,而且2必须 先于仙出栈 top→ 321 作业: 1,2,3,4,5,6依次进栈,若出栈顺序为2,3,4,6,5,1 则栈大小至少为多少?

栈 ◼ 进栈顺序为(1,2,3)，出栈顺序能否为(3,1,2)?  不能，3出栈时，说明2和1都在栈里，而且2必须 先于1出栈 6 3 2 1 top 作业： 1，2，3，4，5，6依次进栈，若出栈顺序为2，3，4，6，5，1 则栈大小至少为多少？

桤的应用:表达式求值 个表达式由操作数亦称运算对象)、操作符 亦称运算符)和分界符组成。 算术表达式三种表示 a中缀(nfx表示 ,如A+B; 前缀( prefix)表示 ,如+AB 后缀( postfix表示 ,如AB+;

栈的应用：表达式求值 ◼ 一个表达式由操作数(亦称运算对象)、操作符 (亦称运算符) 和分界符组成。 ◼ 算术表达式三种表示  中缀(infix)表示 ➢ ，如 A+B；  前缀(prefix)表示 ➢ ，如 +AB；  后缀(postfix)表示 ➢ ，如 AB+； 7

桤的应用:表达式求值 n中缀表达式:A+B*(c-D)-E/F n后缀表达式:ABcD-*+EF|- 表达式中相邻两个操作符的计算次序为: 口优先级高的先计算; 优先级相同的自左向右计算; 口当使用括号时从最内层括号开始计算。 前缀和中缀表达式求值需要两个栈;后缀表达 式求值只需一个栈,相对简单些

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

栈的应用:表达式求值 从左向右扫描表达式,用一个栈暂存扫描到的 操作数或计算结果。 后缀表达式的计算顺序中已隐含了加括号的优 先次序,括号在后缀表达式中不出现 中缀表达式: 后缀表达式: A+B(C-D)-E/F ABCD一+EF/ R1 R R R R

栈的应用：表达式求值 ◼ 从左向右扫描表达式，用一个栈暂存扫描到的 操作数或计算结果。 ◼ 后缀表达式的计算顺序中已隐含了加括号的优 先次序，括号在后缀表达式中不出现 9 R1 R2 R3 R4 R5 A B C D - * + E F / - R1 R2 R3 R4 R5 A+B*(C-D)-E/F 中缀表达式： 后缀表达式：

作业: 写出下列中缀表达式的后缀表达式 1. AB*C 2. -A+B-C+D 3.A(B)+C 4.(A+B D+E/(F+AD)+C 5.A&&B‖(E>F) 6.!(A&&!(BD))‖!(C<E) 10

10 作业： 写出下列中缀表达式的后缀表达式 1. A*B*C 2. -A+B-C+D 3. A*(-B)+C 4. (A+B)*D+E/(F+A*D)+C 5. A&&B||!(E>F) 6. !(A && !((BD))) || (C<E)