《《数据结构堆栈》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构堆栈》PPT课件.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章 堆栈和队列提纲 4.1堆栈的概念及其运算 4.2堆栈的顺序存储结构 4.3堆栈的链式存储结构 4.4堆栈的应用4.1堆栈的概念及其运算堆栈的逻辑结构的逻辑结构堆栈：堆栈：堆栈：堆栈：限定仅在表尾进行插入和删除操作的限定仅在表尾进行插入和删除操作的限定仅在表尾进行插入和删除操作的限定仅在表尾进行插入和删除操作的线性表。线性表。线性表。线性表。空栈：不含任何数据元素的栈。空栈：不含任何数据元素的栈。空栈：不含任何数据元素的栈。空栈：不含任何数据元素的栈。允许插入和删除的一端称为栈顶，另一端称允许插入和删除的一端称为栈顶，另一端称允许插入和删除的一端称为栈顶，另一端称允许插入和删除的一端称为
2、栈顶，另一端称为栈底。为栈底。为栈底。为栈底。（a1,a2,an）栈顶栈顶栈底栈底abc入栈入栈出栈出栈栈底栈底栈顶栈顶插入：入栈、进栈、压栈插入：入栈、进栈、压栈插入：入栈、进栈、压栈插入：入栈、进栈、压栈删除：出栈、弹栈删除：出栈、弹栈删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈顶栈顶栈的示意图栈的示意图4.1堆栈的概念及其运算栈的操作特性：栈的操作特性：后进先出后进先出4.1堆栈的概念及其运算例：有三个元素按例：有三个元素按例：有三个元素按例：有三个元素按a a、b b、c c的次序依次进栈，且每个的次序依次进栈，且每个的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能
3、的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶情况情况1：出栈序列：出栈序列：c出栈序列：出栈序列：c、b出栈序列：出栈序列：c、b、a例：有三个元素按例：有三个元素按例：有三个元素按例：有三个元素按a a、b b、c c的次序依次进栈，且每个的次序依次进栈，且每个的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？元
4、素只允许进一次栈，则可能的出栈序列有多少种？栈底栈底栈顶栈顶ab栈顶栈顶情况情况2：出栈序列：出栈序列：b4.1堆栈的概念及其运算栈底栈底a出栈序列：出栈序列：b出栈序列：出栈序列：b、c出栈序列：出栈序列：b、c、ac栈顶栈顶栈顶栈顶注意：注意：栈只是对表插入和删除操作的位置进行了限栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。制，并没有限定插入和删除操作进行的时间。情况情况2：例：有三个元素按例：有三个元素按例：有三个元素按例：有三个元素按a a、b b、c c的次序依次进栈，且每个的次序依次进栈，且每个的次序依次进栈，且每个的次序依次进栈，且每个元素只允许
5、进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？4.1堆栈的概念及其运算堆栈的操作堆栈的操作堆栈的操作堆栈的操作Push(S,x)Push(S,x)Pop(S)Pop(S)Empty(S)Empty(S)Top(S)Top(S)Create(S)Create(S)4.1堆栈的概念及其运算如何改造数组实现栈的顺序存储？如何改造数组实现栈的顺序存储？如何改造数组实现栈的顺序存储？如何改造数组实现栈的顺序存储？012345678a1确定用数组的哪一端表示栈底。确定用数组的哪一
6、端表示栈底。附设指针附设指针top指示栈顶元素在数组中的位置。指示栈顶元素在数组中的位置。top4.2堆栈的顺序存储结构出栈：出栈：top减减1进栈：进栈：top加加1栈空：栈空：top=-1 012345678a1topa2topa3top栈满：栈满：top=MAX_SIZE4.2堆栈的顺序存储结构堆栈是否为空测试算法堆栈是否为空测试算法堆栈是否为空测试算法堆栈是否为空测试算法p70p70进栈算法进栈算法进栈算法进栈算法p71p71退栈算法退栈算法退栈算法退栈算法4.2堆栈的顺序存储结构解决方案解决方案解决方案解决方案1 1：直接解决：为每个栈开辟一个数组空间。直接解决：为每个栈开辟一个数组
7、空间。直接解决：为每个栈开辟一个数组空间。直接解决：为每个栈开辟一个数组空间。解决方案解决方案解决方案解决方案2 2：顺序栈单向延伸顺序栈单向延伸顺序栈单向延伸顺序栈单向延伸使用一个数组来存储两个栈使用一个数组来存储两个栈使用一个数组来存储两个栈使用一个数组来存储两个栈在一个程序中需要在一个程序中需要在一个程序中需要在一个程序中需要同时同时同时同时使用具有使用具有使用具有使用具有相同相同相同相同数据类型的数据类型的数据类型的数据类型的两个栈两个栈两个栈两个栈，如何顺序存储这两个栈？如何顺序存储这两个栈？如何顺序存储这两个栈？如何顺序存储这两个栈？会出现什么问题？如何解决？会出现什么问题？如何解
8、决？会出现什么问题？如何解决？会出现什么问题？如何解决？4.2堆栈的顺序存储结构两栈共享空间：两栈共享空间：两栈共享空间：两栈共享空间：使用一个数组来存储两个栈，让一个使用一个数组来存储两个栈，让一个使用一个数组来存储两个栈，让一个使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组栈的栈底为该数组的始端，另一个栈的栈底为该数组栈的栈底为该数组的始端，另一个栈的栈底为该数组栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。的末端，两个栈从各自的端点向中间延伸。的末端，两个栈从各自的端点向中间延伸。的末端，两个栈从各自的端点向中间延伸。
9、4.2堆栈的顺序存储结构栈栈栈栈1 1的底固定在下标为的底固定在下标为的底固定在下标为的底固定在下标为0 0的一端；的一端；的一端；的一端；栈栈栈栈2 2的底固定在下标为的底固定在下标为的底固定在下标为的底固定在下标为MaxSize-1MaxSize-1的一端。的一端。的一端。的一端。top1top1和和和和top2top2分别为栈分别为栈分别为栈分别为栈1 1和栈和栈和栈和栈2 2的栈顶指针；的栈顶指针；的栈顶指针；的栈顶指针；MaxSizeMaxSize为整个数组空间的大小（图中用为整个数组空间的大小（图中用为整个数组空间的大小（图中用为整个数组空间的大小（图中用S S表示）；表示）；表示
10、）；表示）；a1a2aitop10 1 2 S-1top2bj b2b1栈栈1底底栈栈2底底4.2堆栈的顺序存储结构top1=-1什么时候栈什么时候栈什么时候栈什么时候栈1 1为空？为空？为空？为空？a1a2aitop10 1 2 S-1top2bj b2b1top14.2堆栈的顺序存储结构top1=-1什么时候栈什么时候栈什么时候栈什么时候栈1 1为空？为空？为空？为空？a1a2aitop10 1 2 S-1top2bj b2b1什么时候栈什么时候栈什么时候栈什么时候栈2 2为空？为空？为空？为空？top2top2=MaxSize4.2堆栈的顺序存储结构top1=-1什么时候栈什么时候栈什么
11、时候栈什么时候栈1 1为空？为空？为空？为空？a1a2aitop10 1 2 S-1top2bj b2b1什么时候栈什么时候栈什么时候栈什么时候栈2 2为空？为空？为空？为空？top2=MaxSize什么时候栈满？什么时候栈满？什么时候栈满？什么时候栈满？top2=top1+14.2堆栈的顺序存储结构1.1.如果栈满，则抛出上溢异常；如果栈满，则抛出上溢异常；如果栈满，则抛出上溢异常；如果栈满，则抛出上溢异常；2.2.判断是插在栈判断是插在栈判断是插在栈判断是插在栈1 1还是栈还是栈还是栈还是栈2 2；2.12.1若在栈若在栈若在栈若在栈1 1插入，则插入，则插入，则插入，则2.1.1top1
12、2.1.1top1加加加加1;1;2.1.22.1.2在在在在top1top1处填入处填入处填入处填入x x；2.22.2若在栈若在栈若在栈若在栈2 2插入，则插入，则插入，则插入，则2.2.1top22.2.1top2减减减减1;1;2.2.22.2.2在在在在top2top2处填入处填入处填入处填入x x；操作接口：操作接口：操作接口：操作接口：voidPush(inti,Tx)voidPush(inti,Tx);4.2堆栈的顺序存储结构1.1.若是在栈若是在栈若是在栈若是在栈1 1删除，则删除，则删除，则删除，则1.11.1若栈若栈若栈若栈1 1为空栈，抛出下溢异常；为空栈，抛出下溢异常
13、；为空栈，抛出下溢异常；为空栈，抛出下溢异常；1.21.2删除并返回栈删除并返回栈删除并返回栈删除并返回栈1 1的栈顶元素；的栈顶元素；的栈顶元素；的栈顶元素；2.2.若是在栈若是在栈若是在栈若是在栈2 2删除，则删除，则删除，则删除，则2.12.1若栈若栈若栈若栈2 2为空栈，抛出下溢异常；为空栈，抛出下溢异常；为空栈，抛出下溢异常；为空栈，抛出下溢异常；2.22.2删除并返回栈删除并返回栈删除并返回栈删除并返回栈2 2的栈顶元素；的栈顶元素；的栈顶元素；的栈顶元素；操作接口：操作接口：操作接口：操作接口：TPop(inti)TPop(inti);4.2堆栈的顺序存储结构heada1a2an
14、ai链栈需要加头结点吗？链栈需要加头结点吗？链栈需要加头结点吗？链栈需要加头结点吗？如何改造链表实现栈的链接存储？如何改造链表实现栈的链接存储？如何改造链表实现栈的链接存储？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将哪一端作为栈顶？将哪一端作为栈顶？将哪一端作为栈顶？将链头作为栈顶，方便操作。将链头作为栈顶，方便操作。将链头作为栈顶，方便操作。将链头作为栈顶，方便操作。链栈不需要附设头结点。链栈不需要附设头结点。链栈不需要附设头结点。链栈不需要附设头结点。4.3堆栈的链式存储结构栈顶栈顶栈底栈底链栈：链栈：链栈：链栈：栈的链接存储结构栈的链接存储结构栈的链接存储结构栈的链接存储结构to
15、panan-1a1heada1a2anai两种示意图在内存中两种示意图在内存中两种示意图在内存中两种示意图在内存中对应同一种状态对应同一种状态对应同一种状态对应同一种状态topa1an-1an栈顶栈顶栈底栈底4.3堆栈的链式存储结构4.3堆栈的链式存储结构 入栈：入栈：入栈：入栈：p75p75 出栈：出栈：出栈：出栈：p75p75操作接口：操作接口：操作接口：操作接口：4.3堆栈的链式存储结构顺序栈和链栈的比较顺序栈和链栈的比较顺序栈和链栈的比较顺序栈和链栈的比较时间性能：相同，都是常数时间时间性能：相同，都是常数时间时间性能：相同，都是常数时间时间性能：相同，都是常数时间O(1)O(1)。空
16、间性能：空间性能：空间性能：空间性能：顺序栈：有元素个数的限制和空间浪费的问题。顺序栈：有元素个数的限制和空间浪费的问题。顺序栈：有元素个数的限制和空间浪费的问题。顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间链栈：没有栈满的问题，只有当内存没有可用空间链栈：没有栈满的问题，只有当内存没有可用空间链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，时才会出现栈满，但是每个元素都需要一个指针域，时才会出现栈满，但是每个元素都需要一个指针域，时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。从而产生了结
17、构性开销。从而产生了结构性开销。从而产生了结构性开销。总之，当栈的使用过程中元素个数变化较大时，总之，当栈的使用过程中元素个数变化较大时，总之，当栈的使用过程中元素个数变化较大时，总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。用链栈是适宜的，反之，应该采用顺序栈。用链栈是适宜的，反之，应该采用顺序栈。用链栈是适宜的，反之，应该采用顺序栈。1 1 递归的定义递归的定义递归的定义递归的定义 子程序（或函数）直接调用自己或通过一系列调用子程序（或函数）直接调用自己或通过一系列调用子程序（或函数）直接调用自己或通过一系列调用子程序（或函数）直接调用自己或通过一系列调用
18、语句间接调用自己，是一种描述问题和解决问题的语句间接调用自己，是一种描述问题和解决问题的语句间接调用自己，是一种描述问题和解决问题的语句间接调用自己，是一种描述问题和解决问题的基本方法。基本方法。基本方法。基本方法。2 2 递归的基本思想递归的基本思想递归的基本思想递归的基本思想 问题分解：把一个不能或不好解决的大问题转化为问题分解：把一个不能或不好解决的大问题转化为问题分解：把一个不能或不好解决的大问题转化为问题分解：把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成一个或几个小问题，再把这些小问题进一步分解成一个或几个小问题，再把这些小问题进一步分解成一个或几个
19、小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。更小的小问题，直至每个小问题都可以直接解决。更小的小问题，直至每个小问题都可以直接解决。更小的小问题，直至每个小问题都可以直接解决。4.4堆栈的应用递归3 递归的要素递归的要素递归边界条件：确定递归到何时终止，也称递归边界条件：确定递归到何时终止，也称递归边界条件：确定递归到何时终止，也称递归边界条件：确定递归到何时终止，也称为递归出口；为递归出口；为递归出口；为递归出口；递归模式：大问题是如何分解为小问题的，递归模式：大问题是如何分解为小问题的，递归模式：大问题是如何分解为小问题的，递归模式：大问题是如何分解为小问
20、题的，也称为递归体。也称为递归体。也称为递归体。也称为递归体。4.4堆栈的应用递归4.4堆栈的应用递归递归算法递归算法递归算法递归算法intfact(intn)intfact(intn)if(n=0)return1;if(n=0)return1;elsereturnn*fact(n-1);elsereturnn*fact(n-1);-*=时时当当时时当当)!1(1!n1n1nnn例例例例1 1 1 1 阶乘函数阶乘函数阶乘函数阶乘函数4.4堆栈的应用递归递归的经典问题递归的经典问题汉诺塔问题汉诺塔问题 在世界刚被创建的时候有一座钻石宝塔（塔在世界刚被创建的时候有一座钻石宝塔（塔在世界刚被创建的
21、时候有一座钻石宝塔（塔在世界刚被创建的时候有一座钻石宝塔（塔A A），其上有），其上有），其上有），其上有6464个金碟。所有碟子按从大到个金碟。所有碟子按从大到个金碟。所有碟子按从大到个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔小的次序从塔底堆放至塔顶。紧挨着这座塔小的次序从塔底堆放至塔顶。紧挨着这座塔小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔有另外两个钻石宝塔（塔有另外两个钻石宝塔（塔有另外两个钻石宝塔（塔B B和塔和塔和塔和塔C C）。从世）。从世）。从世）。从世界创始之日起，婆罗门的牧师们就一直在试界创始之日起，婆罗门的牧师们就一直在试界创始之日起，
22、婆罗门的牧师们就一直在试界创始之日起，婆罗门的牧师们就一直在试图把塔图把塔图把塔图把塔A A上的碟子移动到塔上的碟子移动到塔上的碟子移动到塔上的碟子移动到塔C C上去，其间借上去，其间借上去，其间借上去，其间借助于塔助于塔助于塔助于塔B B的帮助。每次只能移动一个碟子，的帮助。每次只能移动一个碟子，的帮助。每次只能移动一个碟子，的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟任何时候都不能把一个碟子放在比它小的碟任何时候都不能把一个碟子放在比它小的碟任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也子上面。当牧师们完成任务时，世界末日也子上面。当牧
23、师们完成任务时，世界末日也子上面。当牧师们完成任务时，世界末日也就到了。就到了。就到了。就到了。4.4堆栈的应用递归汉诺塔问题的递归求解汉诺塔问题的递归求解:如果如果如果如果 n=1 n=1，则将这一个盘子直接从，则将这一个盘子直接从，则将这一个盘子直接从，则将这一个盘子直接从 塔塔塔塔A A移移移移到塔到塔到塔到塔 C C 上。否则，执行以下三步：上。否则，执行以下三步：上。否则，执行以下三步：上。否则，执行以下三步：将塔将塔将塔将塔A A上的上的上的上的n-1n-1个碟子借助塔个碟子借助塔个碟子借助塔个碟子借助塔C C先移到塔先移到塔先移到塔先移到塔B B上；上；上；上；把塔把塔把塔把塔A
24、 A上剩下的一个碟子移到塔上剩下的一个碟子移到塔上剩下的一个碟子移到塔上剩下的一个碟子移到塔C C上；上；上；上；将将将将n-1n-1个碟子从塔个碟子从塔个碟子从塔个碟子从塔B B借助于塔借助于塔借助于塔借助于塔A A移到塔移到塔移到塔移到塔C C上。上。上。上。4.4堆栈的应用递归4.4堆栈的应用递归voidHanoivoidHanoi(intn,charA,charB,charCintn,charA,charB,charC)ifif(n=1n=1)MoveMove(A,CA,C);elseelseHanoiHanoi(n n-1,A,C,B1,A,C,B);MoveMove(A,CA,C)
25、;HanoiHanoi(n n-1,B,A,C1,B,A,C);4.4堆栈的应用递归递归函数的内部执行过程递归函数的内部执行过程递归函数的内部执行过程递归函数的内部执行过程 运行开始时，首先为递归调用建立一个工作栈，运行开始时，首先为递归调用建立一个工作栈，运行开始时，首先为递归调用建立一个工作栈，运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；其结构包括值参、局部变量和返回地址；其结构包括值参、局部变量和返回地址；其结构包括值参、局部变量和返回地址；每次执行递归调用之前，把递归函数的值参和局每次执行递归调用之前，把递归函数的值参和局每次执行递归调用之前，把递归函
26、数的值参和局每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；部变量的当前值以及调用后的返回地址压栈；部变量的当前值以及调用后的返回地址压栈；部变量的当前值以及调用后的返回地址压栈；每次递归调用结束后，将栈顶元素出栈，使相应每次递归调用结束后，将栈顶元素出栈，使相应每次递归调用结束后，将栈顶元素出栈，使相应每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返的值参和局部变量恢复为调用前的值，然后转向返的值参和局部变量恢复为调用前的值，然后转向返的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。回地址指定的位置
27、继续执行。回地址指定的位置继续执行。回地址指定的位置继续执行。Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move(A,C)Move(A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move(C,B)Hanio(1,C,A,B)Move(A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move(B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move(A,C)Hanio(2,B,A,C)Move(B,A)Hanio(1,A,B,C)结束结束4.4堆栈的应用表达式求值表达式求值中缀
28、表达式中缀表达式后缀表达式后缀表达式后缀表达式特点后缀表达式特点后缀表达式中不出现括号后缀表达式中不出现括号后缀表达式中不出现括号后缀表达式中不出现括号后缀表达式与中缀表达式的运算对象的先后次序后缀表达式与中缀表达式的运算对象的先后次序后缀表达式与中缀表达式的运算对象的先后次序后缀表达式与中缀表达式的运算对象的先后次序相同，只是所读到的运算符的先后次序可能有所相同，只是所读到的运算符的先后次序可能有所相同，只是所读到的运算符的先后次序可能有所相同，只是所读到的运算符的先后次序可能有所改变改变改变改变4.4堆栈的应用表达式求值表达式求值后缀表达式实例后缀表达式实例(1)ABCE/-E*+(1)(
29、1)对应中缀表达式对应中缀表达式对应中缀表达式对应中缀表达式 A+(B-C/D)*EA+(B-C/D)*E(2)ABCD/F*-E*+X+1.1.对应中缀表达式对应中缀表达式对应中缀表达式对应中缀表达式A+(B-C/D*F)*E+XA+(B-C/D*F)*E+X 4.4堆栈的应用后缀表达式求值后缀表达式求值后缀表达式计算算法：后缀表达式计算算法：后缀表达式计算算法：后缀表达式计算算法：Procedure EVAL(E)/EProcedure EVAL(E)/E为后缀表达式为后缀表达式为后缀表达式为后缀表达式toptop0 0looploopx x NEXT_TOKEN(E)NEXT_TOKEN
30、(E)casecase:x=“#”:x=“#”:returnreturn:x=:x=运算对象运算对象运算对象运算对象:call PUSH(STACK,M,top,x)call PUSH(STACK,M,top,x):else:else:从堆栈中取出相应的运算对象进行由从堆栈中取出相应的运算对象进行由从堆栈中取出相应的运算对象进行由从堆栈中取出相应的运算对象进行由x x执行的运算执行的运算执行的运算执行的运算并将结果入栈并将结果入栈并将结果入栈并将结果入栈endendforeverforeverendend4.4堆栈的应用中缀表达式转换中缀表达式转换算法思想算法思想p81-82关键点：关键点：运
31、算符堆栈运算符堆栈运算符优先关系表运算符优先关系表4.4堆栈的应用中缀表达式转换中缀表达式转换运算优先级运算优先级()#(#1 dowhile top1 doprint(STACKtop)print(STACKtop)/输出栈顶运算符输出栈顶运算符输出栈顶运算符输出栈顶运算符call POP(STATCK,top)/call POP(STATCK,top)/退栈退栈退栈退栈endendprint(“#”);print(“#”);returnreturn:x:x是运算对象是运算对象是运算对象是运算对象:print(x)print(x)/直接输出运算对象直接输出运算对象直接输出运算对象直接输出运算
32、对象endendforeverforeverendend4.4堆栈的应用中缀表达式转换中缀表达式转换:x=“:x=“）”:”:while STACKtop”(“dowhile STACKtop”(“doprint(STATCKtop)print(STATCKtop)call POP(STACK,top)call POP(STACK,top)endendtop top top-1/top-1/放弃当前读到的放弃当前读到的放弃当前读到的放弃当前读到的”)”)”，并且栈顶，并且栈顶，并且栈顶，并且栈顶“(”“(”退栈退栈退栈退栈:else:else:while ISP(STACKtop=ICP(x)dowhile ISP(STACKtop=ICP(x)doprint(STACKtop)print(STACKtop)call POP(STACK,top)call POP(STACK,top)endendcall PUSH(STACK,top,x)call PUSH(STACK,top,x)/运算符进栈运算符进栈运算符进栈运算符进栈endendforeverforeverendend