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

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

2、public void init_stack();/栈的初始化public booleanisempty_stack();/判断栈是否为空public booleanisfull_stack();/判断是否满public booleanpush_stack(datatype x);入栈public datatypepop_stack();/ljll栈public datatypetop_stack();/提取栈顶元素2、利用顺序表实现栈在匸程project2中创建一个class,命名为seqstack,实现的stack接口。定义的类增加泛型, 修改完善如下代码：public class seq

3、stack<datatype> implements stack<datatype> private final static int maxsize=100;privateint top;private object data;publicseqstack() init_stack();(©overridepublic void init_stack() data = new objectmaxsize;top = -1;(©overridepublicbooleanisempty_stack() if(top=-l)return true;ret

4、urn false;override publicbooleanisfull_stack() if(top=maxsize-l)return true; return false;overridepublic booleanpush_stack(datatype x) overridepublicdatatypepop_stack() overridepublicdatatypetop_stack() if(isempty_stack()return null; else return (datatype)data(top;3、利用链表实现栈在工程project2中创建一个class,命名为l

5、inkstack,实现的stack接口。定义的类增加 泛型，修改完善如下代码：public class linkstack<datatype> implements stack<datatype>private linknode<datatype> top;/引用变量非带头节点publiclinkstack()init_stack();overridepublic void init_stack() top=null;overridepublicbooleanisempty_stack() if(top=null)return true; else retu

6、rn false;(©overridepublicbooleanisfull_stack() return false;overridepublicbooleanpush_stack(datatype x) linknode<datatype> s=new linknode<datatype>();补充代码return true;(5) overridepublicdatatypepop_stack() linknode s;if(top=null)return null;else补充代码(©overridepublicdatatypetop_sta

7、ck() if(top=二null)return null;elsereturn (datatype)top.data;classllnknode<datatype>datatype data;linknode next;4、栈的应用问题：利用栈找出所给出的迷宫从入口到出口的一条路径,入口为(:l,l)点，出口为(6,8) 点。迷宫的1表示不可以到达点，0表示可以到达点。可以沿8个方向运动。实训过程：在匸程project2屮创建一个class,命名为mazetest,并在该文档屮定义如下两个类movepoint 和item,完整的代码如下： public class mazetes

8、t public static void main(string args) int maze=14,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,14,1,0,0,1,0,1,04,1,1,1,1,1,1,0,1,0,0,1,11,1,0,1,0,1,1,1,04,1,1,1,0,1,1,1,0,0,04,1,0,1,1,0,0,1,1,04,1,1,1,1,1,1,1,1,14;ltem move=new ltem8;int tmp=0/llull,0/l,-lk0,4,1, 1,£,"for(inti=0;i<8;i+)movei=new lt

9、em(tmpio，tmpi);if (path(mazezmove)system.out.println(n 迷宫有路”);else system.out.println("迷宫无路!")；public static boolean path(int maze,ltem move)intm,n;m=mazeen gth;n=maze 0en gth;seqstack<movepoint> s=new seqstack<movepoint>();/使用链式栈,也可以使用顺序栈movepoint temp = new movepoint(); intx,

10、y,d,i,j;temp.i=l;temp.j=l;temp.d=-l;mazell=-l;s.push_stack(temp);while) !s.isempty_stack()temp=s.top_sta ck();x=temp.i;y=temp.j;d=temp.d+l;while(d<8)i=x+moved.x;j=y+moved.y;if(mazeij=o)temp=new movepoint(); temp.i=i;temp.j=j;temp.d=d; s.push_stack(temp);x=i;y=j;mazexy二 if(x=m-2 && y=n-2)w

11、hile(!s.isempty_stack() temp=s.pop_stack(); systemoutprint(y'+tempi+t+tempj+”>)；system.out.printlnf);return true;else d=0;else d+;if (d=8)s.pop_stack();return false;class ltemintx,y;public ltem(inti,int j)x=i;y=j;classmovepointintijd;注意：要求完成栈的设计后便用该应用测试你所设计的栈是否正确，并釆用两种实现方式来测试，说明栈的不同实现方式对于应用问题

12、的解决没有实质的应用。二、队列的实训1、便用java接口定义队列的基本操作在工程project2中创建一个接口，命名为queue,参考代码如下： public interface queue <datatype>public void init_queue();publicboolea nisempty_queue();publicboolea nisfull_queue();public <datatype>booleanin_queue(datatype x);入队public <datatype>datatypeout_queue();/ 出队publ

13、ic <datatype>datatypegetfro nt_queue(); 查看队头元素2、利用顺序表实现队列在工程project2中创建-一个class,命名为seqqueue,实现的queue接口。定义的类增 加泛型，修改完善如下代码：public class seqqueue<datatype> implements queue<datatype> private static final int maxsize = 100;int front;队头标志int rear;/队尾标志intnum;入队个数public object data;publ

14、icseqqueue()in it_queue();overridepublic void init_queue() data = new objectmaxsize; front = -1;rear =(©overridepublicbooleanisempty_queue() if(num=0)return true; return false;(©overridepublicbooleanisfull_queue() if(num=maxsize)return true; return false;(©overridepublic<datatype&g

15、t;booleanin_queue(datatype x) if(num=maxsize)system.out.println(n 队满”); return false;elsereturn true;override public<datatype>datatypeout_queue() if(num二=0)system.out.println(n 队空”);return null;elsefront=(front+l)%maxsize;num；return (datatype)data(front;overridepublic<datatype>datatypege

16、tfront_queue() if(n um=0)system.out.println("队空”)；return null;elsereturn (datatype)data(front+l)%maxsize;3、利用链表实现队列在工程project2中创建一个class,命名为linkqueue,实现的queue接口。定义的类增加泛型，修改完善如下代码：public class linkqueue<datatype> implements queue<datatype> lin knode front;linknode rear;publicli nkque

17、ue()in it_queue();overridepublic void init_queue() front = new linknode();rear = front;(©overridepublicbooleanisempty_queue() if(front = rear)return true;return false;overridepublicbooleanisfull_queue() return false;overridepublic<datatype>booleanin_queue(datatype x) linknode<datatype&

18、gt; node= new linknode<datatype>(); 完善代码 return true;overridepublic<datatype>datatypeout_queue() if(front=rear)return null; elselinknode p;完善代码if(p.next = n ull)rear = front;return (datatype)p.data; overridepublic<datatype>datatypegetfront_queue() if(front = rear)return null;else r

19、eturn (datatype)front.next.data;4、队列的应用问题：利用顺序队列找出所给出的迷宫从入口到出口的-条最短路径，入口为(“)点， 出口为(6,8)点。迷宫的1表示不可以到达点,0表示可以到达点。可以沿8个方向运动。 实训过程：在工程project2中创建一个class,命名为mazeshortpathtest,并在该文档中定义类 movepoint2,完整的代码如下：public class mazeshortpathtest public static void main(string args) int maze=1,0,1,0,1,0,1,1,14,1,0,0

20、,1,0,1,0,144,1,1,0,0,0,1,0,0,14,1,0,1,0,1,0,1,0,14,1,1,o,o,1,1,o,1a1,1,0,1,1,0,04,0,0,1,1,1,1,1,1,1,1,1,14;ltem move=new ltem8;int tmp=0,lzl,l,1,0,1,-1,for(inti=0;i<8;i+)movei=new ltem(tmpio,tmpil);if(!shortpath(maze/move)system.out.printlnc，无路径”)；public static booleanshortpath(int mazejtem move)seqqueue<movepoint2> q=new seq