实训项目：栈和队列的设计与应用解析

《实训项目：栈和队列的设计与应用解析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实训项目二：栈和队列的设计与应用课时：4课时目的：通过本项目的实训，掌握如下内容：Ø（1）理解栈和队列的特殊线性表特征；（2）掌握栈和队列的基本操作的实现；（3）理解栈和队列的应用方法；（4）学习使用栈和队列解决实际问题的能力。要求:实训步骤：一、栈的实训1、使用Java接口定义栈的基本操作利用Java集成开发环境Eclipse，创建一个Project2项目工程，在项目src目录下新建一个Interface接口，取名为Stack。由于存储元素的不确定性，使用泛型来定义存储和操作的数据。定义的接口修改如下：publicinterf

2、aceStack{publicvoidinit_Stack();//栈的初始化publicbooleanisEmpty_Stack();//判断栈是否为空publicbooleanisFull_Stack();//判断是否满publicbooleanpush_Stack(DataTypex);//入栈publicDataTypepop_Stack();//出栈publicDataTypetop_Stack();//提取栈顶元素}2、利用顺序表实现栈在工程project2中创建一个class，命名为SeqSta

3、ck，实现的Stack接口。定义的类增加泛型，修改完善如下代码：publicclassSeqStackimplementsStack{privatefinalstaticintMAXSIZE=100;privateinttop;privateObject[]data;;publicSeqStack(){init_Stack();}@Overridepublicvoidinit_Stack(){data=newObject[MAXSIZE];top=-1;}@Overridepublicbo

4、oleanisEmpty_Stack(){if(top==-1)returntrue;returnfalse;}@OverridepublicbooleanisFull_Stack(){if(top==MAXSIZE-1)returntrue;returnfalse;}@Overridepublicbooleanpush_Stack(DataTypex){}@OverridepublicDataTypepop_Stack(){}@OverridepublicDataTypetop_Stack(){if(isEmpty_Stack

5、())returnnull;elsereturn(DataType)data[top];}}3、利用链表实现栈在工程project2中创建一个class，命名为LinkStack，实现的Stack接口。定义的类增加泛型，修改完善如下代码：publicclassLinkStackimplementsStack{privateLinkNodetop;//引用变量非带头节点publicLinkStack(){init_Stack();}@Overridepublicvoidi

6、nit_Stack(){top=null;}@OverridepublicbooleanisEmpty_Stack(){if(top==null)returntrue;elsereturnfalse;}@OverridepublicbooleanisFull_Stack(){returnfalse;}@Overridepublicbooleanpush_Stack(DataTypex){LinkNodes=newLinkNode();//补充代码returntrue;}@Overridep

7、ublicDataTypepop_Stack(){LinkNodes;if(top==null)returnnull;else{//补充代码}}@OverridepublicDataTypetop_Stack(){if(top==null)returnnull;elsereturn(DataType)top.data;}}classLInkNode{DataTypedata;LinkNodenext;}4、栈的应用问题：利用栈找出所给出的迷宫从入口到出口的一条路径，入口为（1,1）点，出口为（6,8）点。迷宫

8、的1表示不可以到达点，0表示可以到达点。可以沿8个方向运动。实训过程：在工程project2中创建一个class,命名为MazeTest,并在该文档中定义如下两个类MovePoint和Item，完整的代码如下：publicclassMazeTest{public