栈满isFull()-东南大学计算机科学与工程学院讲课讲稿.ppt

《栈满isFull()-东南大学计算机科学与工程学院讲课讲稿.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈满isFull()-东南大学计算机科学与工程学院栈定义：只允许在表的末端进行插入和删除的线性表特点：先进后出栈的操作进栈push()出栈pop()栈顶top()置空setEmpty()判断是否为空isEmpty()栈满isFull()2栈栈的数组表示栈的操作进栈push()出栈pop()栈顶top()置空makeEmpty()判断是否为空isEmpty()栈满isFull()topabtopctop空栈top3栈栈的单链表表示栈的数组表示可能栈满栈的单链表表示无栈满问题入栈在表头进行插入操作出栈在表头进行删除操作topcbanull4栈进栈顺序为(1,2,3

2、)，出栈顺序能否为(3,1,2)?不能，3出栈时，说明2和1都在栈里，而且2必须先于1出栈321top作业：1，2，3，4，5，6依次进栈，若出栈顺序为2，3，4，6，5，1则栈大小至少为多少？5栈的应用：表达式求值一个表达式由操作数(亦称运算对象)、操作符(亦称运算符)和分界符组成。算术表达式三种表示中缀(infix)表示<操作数><操作符><操作数>，如A+B；前缀(prefix)表示<操作符><操作数><操作数>，如+AB；后缀(postfix)表示<操作数><操作数><操作符>，如AB+；6栈的应用：表达式求值中缀表达式：A+B*(C-D)-E/F后缀

3、表达式：ABCD-*+EF/-表达式中相邻两个操作符的计算次序为：优先级高的先计算；优先级相同的自左向右计算；当使用括号时从最内层括号开始计算。前缀和中缀表达式求值需要两个栈；后缀表达式求值只需一个栈，相对简单些。7栈的应用：表达式求值从左向右扫描表达式，用一个栈暂存扫描到的操作数或计算结果。后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现R1R2R3R4R5ABCD-*+EF/-R1R2R3R4R5A+B*(C-D)-E/F中缀表达式：后缀表达式：8作业：写出下列中缀表达式的后缀表达式A*B*C-A+B-C+DA*(-B)+C(A+B

4、)*D+E/(F+A*D)+CA&&B

5、

6、!(E>F)!(A&&!((B

7、

8、(C>D)))

9、

10、(C，若是单目运算符，则出栈一个操作数X，并将计算结果X进栈若是双目运算符，则连续出栈两个操作数X和Y，并将计算结果XY进栈当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。10栈的应用：表达式求值步输入类型动作栈中内容1置空栈2A操作数进栈A3B操作数进栈AB4C操作数进栈ABC5D操作数进栈ABCD6-操作符D、C退

11、栈，计算R1=C-D进栈ABR17*操作符R1、B退栈，计算R2=B*R1进栈AR28+操作符R2、A退栈，计算R3=A+R2进栈R39E操作数进栈R3E10F操作数进栈R3EF11/操作符F、E退栈，计算R4=E/F进栈R3R412-操作符R4、R3退栈，计算R5=R3-R4进栈R5top空栈topBACDtoptoptopABCD-*+EF/-后缀表达式求值过程：11栈的应用：表达式求值步输入类型动作栈中内容1置空栈2A操作数进栈A3B操作数进栈AB4C操作数进栈ABC5D操作数进栈ABCD6-操作符D、C退栈，计算R1=C-D进栈ABR17*操作符R1、

12、B退栈，计算R2=B*R1进栈AR28+操作符R2、A退栈，计算R3=A+R2进栈R39E操作数进栈R3E10F操作数进栈R3EF11/操作符F、E退栈，计算R4=E/F进栈R3R412-操作符R4、R3退栈，计算R5=R3-R4进栈R5BACDtoptoptopR1=C-DABCD-*+EF/-后缀表达式求值过程：12栈的应用：表达式求值步输入类型动作栈中内容1置空栈2A操作数进栈A3B操作数进栈AB4C操作数进栈ABC5D操作数进栈ABCD6-操作符D、C退栈，计算R1=C-D进栈ABR17*操作符R1、B退栈，计算R2=B*R1进栈AR28+操作符R2、

13、A退栈，计算R3=A+R2进栈R39E操作数进栈R3E10F操作数进栈R3EF11/操作符F、E退栈，计算R4=E/F进栈R3R412-操作符R4、R3退栈，计算R5=R3-R4进栈R5BAtopR1=C-DtoptopABCD-*+EF/-R2=B*R1后缀表达式求值过程：13栈的应用：表达式求值步输入类型动作栈中内容1置空栈2A操作数进栈A3B操作数进栈AB4C操作数进栈ABC5D操作数进栈ABCD6-操作符D、C退栈，计算R1=C-D进栈ABR17*操作符R1、B退栈，计算R2=B*R1进栈AR28+操作符R2、A退栈，计算R3=A+R2进栈R39E操作

14、数进栈R3E10F操作数进栈R3EF1