文档介绍：栈与队列本章主要内容?栈?栈的应用:表达式求值?栈与递归?队列?队列的应用:电路布线 2 栈?定义:只允许在表的末端进行插入和删除的线性表?特点:先进后出?栈的操作?进栈 push() ?出栈 pop() ?栈顶 top() ?置空 setEmpty () ?判断是否为空 isEmpty () ?栈满 isFull () 3 栈?栈的数组表示?栈的操作?进栈 push() ?出栈 pop() ?栈顶 top() ?置空 makeEmpty () ?判断是否为空 isEmpty () ?栈满 isFull () 4 topa b top c top 空栈 top栈?栈的单链表表示?栈的数组表示可能栈满?栈的单链表表示无栈满问题?入栈在表头进行插入操作?出栈在表头进行删除操作 5 top cba null栈?进栈顺序为(1,2,3) ,出栈顺序能否为(3,1,2)? ?不能, 3出栈时,说明 2和1都在栈里,而且 2必须先于 1出栈 6 321 top 作业: 1,2,3,4,5,6依次进栈,若出栈顺序为 2,3,4,6,5,1 则栈大小至少为多少? 栈的应用:表达式求值?一个表达式由操作数(亦称运算对象)、操作符(亦称运算符) 和分界符组成。?算术表达式三种表示?中缀(infix) 表示?<操作数> < 操作符> < 操作数>,如 A+B ; ?前缀(prefix) 表示?<操作符> < 操作数> < 操作数>,如+AB ; ?后缀(postfix) 表示?<操作数> < 操作数> < 操作符>,如 AB+ ;7 栈的应用:表达式求值?中缀表达式: A + B * ( C - D ) - E / F ?后缀表达式: A B C D - * + E F / - ?表达式中相邻两个操作符的计算次序为: ?优先级高的先计算; ?优先级相同的自左向右计算; ?当使用括号时从最内层括号开始计算。?前缀和中缀表达式求值需要两个栈;后缀表达式求值只需一个栈,相对简单些。 8 栈的应用:表达式求值?从左向右扫描表达式,用一个栈暂存扫描到的操作数或计算结果。?后缀表达式的计算顺序中已隐含了加括号的优先次序,括号在后缀表达式中不出现 9R 1R 2R 3R 4R 5 A B C D -* + E F /- R 1R 2R 3R 4R 5 A+B * (C - D) -E/F 中缀表达式: 后缀表达式: 10 作业: 写出下列中缀表达式的后缀表达式 *B*C 2. -A+B-C+D * (-B)+C 4. (A+B) * D+E/(F+A * D)+C 5. A&&B||!(E>F) 6. !(A && !((B<C) || (C>D))) || (C<E)