数据结构实验报告三栈的实现

实验报告实验题目：栈的实现实验目的：掌握栈的特点。熟悉在栈上进行的各种操作。实验要求：1．建立一个接口，定义一些常用的基本方法；2．用类实现该接口的基本方法：入栈；出栈；取栈顶元素；判空、判满；3．定义客户类来调用接口中的方法；实验环境：一台PC机，Eclipse软件程序代码：a．栈的接口：packageStack;publicinterfaceStackInterface<T>{publicvoidpush(TnewEntry);publicTpop();publicTpeek();publicbooleanisEmpty();publicvoidclear();}b．基于链表的实现的方法类packageStack;publicclassLinkedStack<T>implementsStackInterface<T>,java.io.Serializable{privateNodetopNode;//引用链表中第一个结点publicLinkedStack(){ topNode=null;} publicvoidpush(TnewEntry){//将新元素插入栈顶 //TODOAuto-generatedmethodstub NodenewNode=newNode(newEntry,topNode); topNode=newNode;//将新结点指向栈顶结点 } publicTpop(){//删除并返回栈顶 //TODOAuto-generatedmethodstub Ttop=null; if(topNode!=null) { top=topNode.getData(); topNode=topNode.getNextNode(); } returntop; } publicTpeek(){//取出栈顶并且不以任何方式改变栈 //TODOAuto-generatedmethodstub Ttop=null; if(topNode!=null) top=topNode.getData(); returntop; } publicbooleanisEmpty(){检查栈是否为空 //TODOAuto-generatedmethodstub returntopNode==null; } publicvoidclear(){从栈中删除所有元素 //TODOAuto-generatedmethodstub topNode=null; } privateclassNodeimplementsjava.io.Serializable//构造私有类Node { privateTdata; privateNodenext; privateNode(TdataPortion) { data=dataPortion; next=null; } privateNode(TdataPortion,NodenextNode) { data=dataPortion; next=nextNode; } TgetData() { returndata; } voidsetData(TnewData) { data=newData; } NodegetNextNode() { returnnext; } voidsetNextNode(NodenextNode) { next=nextNode; } }}c.基于数组的实现的方法类packageStack;publicclassArrayStack<T>implementsStackInterface<T>{ privateT[]stack;//存放栈元素的数组 privateinttopIndex;//栈顶元素索引 privatestaticfinalintDEFAULF_MAX_SIZE=50; publicArrayStack() { this(DEFAULF_MAX_SIZE); } publicArrayStack(intinitialCapacity) { stack=(T[])newObject[initialCapacity]; topIndex=-1; } publicvoidpush(TnewEntry){//将新元素插入栈顶 //TODOAuto-generatedmethodstub topIndex++; if(topIndex>=stack.length)//若数组已满 doubleArray();//扩展数组 stack[topIndex]=newEntry;//将新元素插入栈顶 } privatevoiddoubleArray()//扩展数组 { T[]oldList=stack; intoldSize=oldList.length; stack=(T[])newObject[2*oldSize]; for(intindex=0;index<oldSize;index++) stack[index]=oldList[index]; } publicTpop(){//删除并返回栈顶 //TODOAuto-generatedmethodstub Ttop=null; if(!isEmpty()) { top=stack[topIndex]; stack[topIndex]=null; topIndex--; } returntop; } publicTpeek(){//取出栈顶并且不以任何方式改变栈 //TODOAuto-generatedmethodstub Ttop=null; if(!isEmpty()) top=stack[topIndex]; returntop; } publicbooleanisEmpty(){//检查栈是否为空 //TODOAuto-generatedmethodstub returntopIndex<0; } publicvoidclear(){从栈中删除所有元素 //TODOAuto-generatedmethodstub for(topIndex=stack.length;topIndex>0;topIndex--) pop(); }}d．基于链表的实现类packageStack;publicclassClientStack{ /** *@paramargs */ publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstubStackInterface<String>myStack=newLinkedStack<String>();myStack.push("Jim");myStack.push("Jess");myStack.push("Jill");myStack.push("Jane");myStack.push("Joe");Stringtop=(String)myStack.peek();System.out.println(top+"isatthetopofthestack.");top=(String)myStack.pop();System.out.println(top+"isremoveedfromthestack.");top=(String)myStack.peek();System.out.println(top+"isatthetopofthestack.");top=(String)myStack.pop();System.out.println(top+"isremoveedfromthestack."); }}e.基于数组的实现类packageStack;publicclassClientArrayStack{ publicstaticvoidmain(String[]args){StackInterfacetryRunArray=newArrayStack();tryRunArray.push("41");tryRunArray.push("42");tryRunArray.push("43");tryRunArray.push("44");tryRunArray.push("45");Objecttop=tryRunArray.peek();System.out.println(top+"isatthetopofthestack.");top=tryRunArray.pop();System.out.println(top+"isremoveedfromthestack.