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

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

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

2、如下：publicinterfaceStack{publicvoidinit_Stack();//栈的初始化publicbooleanisEmpty_Stack();//判断栈是否为空publicbooleanisFull_Stack();//判断是否满publicbooleanpush_Stack(DataTypex);〃入栈publicDataTypepop_Stack();//lJLl栈publicDataTypetop_Stack();//提取栈顶元素}2、利用顺序表实

3、现栈在匸程project2中创建一个class,命名为SeqStack,实现的Stack接口。定义的类增加泛型,修改完善如下代码：publicclassSeqStackimplementsStack{privatefinalstaticintMAXSIZE=100;privateinttop;privateObject[]data;;publicSeqStack(){init_Stack();}(©Overridepublicvoidinit_Stack()

4、{data=newObject[MAXSIZE];top=-1;}(©OverridepublicbooleanisEmpty_Stack(){if(top==-l)returntrue;returnfalse;}@OverridepublicbooleanisFull_Stack(){if(top==MAXSIZE-l)returntrue;returnfalse;}@Overridepublicbooleanpush_Stack(DataTypex){}@OverridepublicDataT

5、ypepop_Stack(){}@OverridepublicDataTypetop_Stack(){if(isEmpty_Stack())returnnull;elsereturn(DataType)data(top];}}3、利用链表实现栈在工程project2中创建一个class,命名为LinkStack,实现的Stack接口。定义的类增加泛型，修改完善如下代码：publicclassLinkStackimplementsStack{privateLi

6、nkNodetop;//引用变量非带头节点publicLinkStack(){init_Stack();}@Overridepublicvoidinit_Stack(){top=null;}@OverridepublicbooleanisEmpty_Stack(){if(top==null)returntrue;elsereturnfalse;}(©OverridepublicbooleanisFull_Stack(){returnfalse;@Overridepublicbo

7、oleanpush_Stack(DataTypex){LinkNodes=newLinkNode();〃补充代码returntrue;}(1)OverridepublicDataTypepop_Stack(){LinkNodes;if(top==null)returnnull;else{〃补充代码}}(©OverridepublicDataTypetop_Stack(){if(top=二null)returnnull;elsereturn(DataType)

8、top.data;}}classLlnkNode{DataTypedata;LinkNodenext;}4、栈的应用问题：利用栈找出所给出的迷宫从入口到出口的一条路径,入口为(:L,l)点，出口为(6,8)点。迷宫的1表示不可以到达点，0表示可以到达点。可以沿8个方向运动。实训过程：在匸程project2屮创建一个class,命名为MazeTest,并在该文档屮定义如下两个类MovePoint和Item,完整的代码如下：publicclassMazeTest{p