资源描述：
《数据结构教学全套课件Java版杨淑萍教学资料教学演示文稿 堆栈Stack).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、堆栈（Stack)内容提要：堆栈的定义堆栈的存储方式堆栈的操作堆栈的应用实践项目：穿越迷宫使用java类库中的java.util.Stack类实现穿越迷宫堆栈的应用文字处理软件需要通过一个堆栈来实现撤消操作IE浏览器中的后退功能也是通过栈来实现的算术运算式的转换（ExpressionConversion）子程序调用（SubroutineCall）中断处理（InterruptProcessing）编译错误处理（CompilerSyntaxProcessing）汉诺塔问题（TowersofHanoi）迷宫问题（MazingProblem）八
2、皇后问题（EightQueenProblem）用栈实现递归调用问题引入对于下图所给出的迷宫，从左上角开始出发，到达右下角结束，问是否可以穿越？穿越的规则是，每行走一步，只能选择上、下、左、右四个方向之一。穿越过程中可能有回退的可能.如何表示一个迷宫?如何编一程序实现这种穿越？堆栈的定义堆栈是一种线性集合，其元素的添加(进栈)和删除(出栈)操作都在同一端(栈顶)完成。元素的进出栈按照后进先出（last-in-first-out，LIFO)的原则进行,即最后进栈的元素第一个出栈。堆栈一般用来保存一些尚未处理和等待处理的数据项。栈顶想一想生活
3、中具有栈操作现象的实例有哪些?堆栈的存储方式顺序存储方式（数组）链式存储方式（链表）堆栈的操作在栈顶添加一个元素（压栈）从栈顶删除一个元素（出栈）确定堆栈是否为空确定堆栈中的元素个数解决迷宫问题（MazingProblem）迷宫的表示:将一个迷宫表示为一个二维数组a[m][n].如果a[i][j]=0,则表示位置(i,j)处是障碍物,不可通过.如果a[i][j]=1,则表示位置(i,j)处可通过.要求寻找一条从a[0][0]到a[m][n]的通路.这里,规定在位置(i,j)处只能向上、下、左、右4个方向移动，不可以在对角线方向上移动。迷
4、宫表示本节所给出的迷宫的可表示为下面的二维数组.int[][]grid={{1,1,1,0,1,1,0,0,0,1,1,1,1},{1,0,1,1,1,0,1,1,1,1,0,0,1},{0,0,0,0,1,0,1,0,1,0,1,0,0},{1,1,1,0,1,1,1,0,1,0,1,1,1},{1,0,1,0,0,0,0,1,1,1,0,0,1},{1,0,1,1,1,1,1,1,0,1,1,1,1},{1,0,0,0,0,0,0,0,0,0,0,0,0},{1,1,1,1,1,1,1,1,1,1,1,1,1}};这个迷宫有一条通路
5、，粉色的1代表一条通路解题思路从(0,0)位置开始，对该位置相邻的上、下、左、右四个位置进行判断，通过选取一个可能畅通的位置作为下一步穿越的位置。这里用一个栈来存放要穿越的迷宫位置坐标，并首先将坐标(0,0)进栈。然后用循环语句重复执行下面操作。弹出栈顶元素，若该位置上的值为1，则将其置为TRIED标识，然后将该位置的4个可能穿越的位置坐标（下、右、左、上）进栈，进行下一次循环，直到到达最后一个位置。如果最后一个位置上的元素也被标识为TRIED，则说明成功穿越迷宫。当栈为空时结束循环。穿越迷宫程序设计思路首先对数据元素（迷宫的点坐标）和
6、数据操作进行设计，然后设计栈实现所定义的数据操作，最后使用栈完成穿越迷宫程序。程序共包含下面三个类，一个接口，都放在一个源程序文件TraversMaze.java中。Position类。定义数据元素，迷宫点的坐标位置。StackADT类。定义数据元素的操作。ArrayStack类。用数组实现的栈，用来存储在穿越过程中迷宫点坐标位置。TraverseMaze类。完成穿越迷宫的判断并输出相关信息。解题步骤项目实践调试运行例题3-1穿越迷宫算法分析booleantraverse(introw,intcol){定义TRIED为已尝试过标志定义d
7、one为是否成功穿越标志创建起点的位置坐标对象start创建一个栈用来存放迷宫位置坐标start进栈当栈不空时,循环做如下操作{出栈一个位置坐标对象获取该坐标的x和y值将该坐标对应的数组元素置为TRIED标志如果该坐标对应数组最后一个元素的下标(迷宫出口位置),则置done为true将当前位置坐标的上一个位置坐标压栈(如果该位置坐标有效,且可通过)将当前位置坐标的左一个位置坐标压栈(如果该位置坐标有效,且可通过)将当前位置坐标的右一个位置坐标压栈(如果该位置坐标有效,且可通过)将当前位置坐标的下一个位置坐标压栈(如果该位置坐标有效,且可
8、通过)}returndone;}课堂实训通过例题3-1的学习，我们掌握了顺序栈的设计与实现，那么链式栈应如何设计并实现呢？。请按47页的指导步骤进行实训.Java类库中的栈Stack类对于J2SDK1.4.
