数据结构（Java语言） 课件 项目三 栈-两栈共享空间

项目三栈---两栈共享空间目录项目三5123

典型工作任务3.1栈项目需求分析典型工作任务3.2栈数据结构设计典型工作任务3.3栈软件代码设计典型工作任务3.4栈软件测试执行典型工作任务3.5栈软件文档编写46典型工作任务3.6栈项目验收交付知识目标熟悉栈的特点掌握顺序栈的表示和实现掌握链式栈的表示和实现技能目标能够分析栈的应用场合能够根据问题选择合理的存储结构能够熟练使用栈解决问题思政目标养成勤俭节约的品德养成自觉遵守公共秩序的行为养成良好的文明礼仪培养做事严谨、认真的态度总体要求

在日常生活栈的应用经常见到，比如我们往桶里放积木，取积木时，先放入的后取出，后放入的先取出。坐电梯先进去的人最后出来。浏览器浏览网页时，有个后退按钮，点击后会按钮访问的顺序逆序后退。

数学计算时也会遇到栈的应用，进制转换问题，一个十进制数转换为二进制数，是计算这个十进制数除以2的余数，再用商作为被除数继续计算除以2的余数，.....，直到商数为0，转换成的二进制数是得到的余数的逆序，即第一个余数为最低位，最后一个余数为二进制数的最高位。

栈的顺序存储结构在解决实际问题时，会出现空间溢出或者空间浪费的情况，为了解决这一问题，提出数据元素类型相同的两个栈可以共享空间，本项目实现共享栈的类型定义及基本操作。典型工作任务3.1栈项目需求分析3.2.1链表结构设计

栈是一种特殊的线性表，限定在表的一端进行插入元素和删除元素的操作。允许插入、删除元素的一端称为栈顶，另一端称为栈底。典型工作任务3.2栈数据结构设计元素入栈和出栈过程

典型工作任务3.2栈数据结构设计3.2.2栈的基本操作

典型工作任务3.2栈数据结构设计初始化：构造一个空的栈清空：使栈称为空栈入栈：在栈顶位置插入新元素出栈：删除栈顶元素取栈顶元素：获取栈顶元素的值判空：判断当前栈是否为空求长度：统计栈中元素个数加工型引用型3.2.3顺序栈1.顺序栈概念顺序栈利用一维数组来定义，数组下标为0的一端作为栈底，定义变量top来指示栈顶元素在顺序栈中的位置。top初始值为-1，指向栈底，top==-1也可以作为栈空的标志。当新的数据元素入栈时，先把栈顶指针top加1，再把新元素放到top指示的位置。删除元素时，先取出top指示的栈顶元素，再将栈顶指示器top的值减1。因此，非空的顺序栈，栈顶指示器top始终指向栈顶元素的位置入栈、出栈时top位置变化。

典型工作任务3.2栈数据结构设计3.2.3顺序栈2.顺序栈泛型类的定义如下：publicclassSeqStack{ privatefinalintmaxSize=10; privateObject[]stack; privateinttop; publicSeqStack(){} publicSeqStack(intn){} publicvoidpush(Objectobj){} publicObjectpop(){} publicObjectgetTop(){}publicbooleanisEmpty(){} publicintgetLength(){} publicvoidclear(){}}

典型工作任务3.2栈数据结构设计顺序栈中一维数组的初始长度存储元素的数组对象指示栈顶元素在顺序栈中的位置3.顺序栈的基本操作实现（1）栈的初始化publicSeqStack(){ top=-1; stack=newObject[maxSize];//初始化栈空间大小为默认值10 }publicSeqStack(intn){//初始化栈空间大小为n if(n<=0){ System.out.println("栈空间大小非法！"); System.exit(1); } top=-1; stack=newObject[n];/ }

典型工作任务3.2栈数据结构设计(2)入栈publicvoidpush(Objectobj){ if(top==stack.length-1){//如果栈满，将栈存储空间扩大到原来的2倍 Object[]temp=newObject[stack.length*2]; for(inti=0;i<stack.length;i++){//原栈数组中的元素复制到新数组中 temp[i]=stack[i]; } stack=temp;//栈引用新数组 } top++;//栈顶指示器增1 stack[top]=obj;//元素入栈 }

典型工作任务3.2栈数据结构设计如果栈满重新分配存储空间(3)出栈publicObjectpop(){ if(top==-1){ System.out.println("空栈！"); returnnull; } Objectt=stack[top]; top--; returnt; }

典型工作任务3.2栈数据结构设计出栈后top值要减一(4)取栈顶元素publicObjectgetTop(){ if(top==-1){ System.out.println("\t空栈！"); returnnull; } returnstack[top];//返回栈顶元素 }

典型工作任务3.2栈数据结构设计取栈顶元素top值不变(5)判断是否为空栈publicbooleanisEmpty(){ returntop==-1; }

（6）求栈长度publicintgetLength(){ returntop+1; }

(7)置空栈

publicvoidclear(){ top=-1; }

典型工作任务3.2栈数据结构设计4.

顺序栈类的测试publicclassTestSeqStack{publicstaticvoidmain(String[]args){SeqStackmyStack=newSeqStack();//创建空栈，存储空间为默认大小10myStack.push(2);//入栈操作myStack.push(3);myStack.push(4);System.out.println("\t栈顶元素："+myStack.getTop());//取栈顶元素并输出System.out.println("\t出栈元素："+myStack.pop());//出栈操作System.out.println("\t出栈元素："+myStack.pop());//获取栈中元素个数并输出

System.out.println("\t栈中元素个数："+myStack.getLength());for(inti=0;i<15;i++)//入栈元素超过栈的存储空间时，栈空间扩大到原来2倍

结合顺序栈的七种算法，

myStack.push(100);运行结果为：

}System.out.println("\t扩充空间后栈中元素个数："+myStack.getLength());myStack.clear();//置空栈System.out.println("\t置空后栈中元素个数："+myStack.getLength()); }}

典型工作任务3.2栈数据结构设计3.2.4链栈栈的链接存储结构称为链栈。每个结点有数据域和指针域，分别存储数据元素和直接后继的存储位置。栈顶指针就是链表的头指针，它唯一确定一个链栈。

典型工作任务3.2栈数据结构设计入栈和出栈过程

典型工作任务3.2栈数据结构设计2.链栈类的定义先定义链中结点类：publicclassNode{ publicObjectdata; publicNodenext; publicNode(){ } publicNode(Objectdata){ this.data=data; next=null; } publicNode(Objectdata,Nodenext){ this.data=data; this.next=next; }}

典型工作任务3.2栈数据结构设计链栈泛型类的实现如下：publicclassLinkStack{ publicNodetop;//栈顶指针 privateintlength;//栈的长度 publicLinkStack(){}//构造一个空栈 publicvoidpush(Objectobj){}//入栈 publicObjectpop(){}//出栈 publicObjectgetHead(){}//取栈顶元素 publicbooleanisEmpty(){}//判栈是否为空 publicvoidgetAll(){}//输出栈中所有元素 publicintgetLength(){}//取栈的长度 publicvoidclear(){}//清空栈}

典型工作任务3.2栈数据结构设计3.链栈基本操作实现（1）构造一个空栈链publicLinkStack(){ top=null; length=0; }

（2）入栈publicvoidpush(Objectobj){ Nodep=newNode(obj); p.next=top; top=p; length++; }

典型工作任务3.2栈数据结构设计（3）出栈publicObjectpop(){ if(top==null){ System.out.println("空栈，无法删除元素！"); returnnull; } Nodep=top; top=top.next; length--; returnp.data; }

典型工作任务3.2栈数据结构设计（4）取栈顶元素publicObjectgetHead(){ if(top==null){ System.out.println("空栈，无法读取栈顶元素！"); returnnull; } returntop.data; }

(5)判栈是否为空publicbooleanisEmpty(){ returntop==null; }

典型工作任务3.2栈数据结构设计（6）输出栈中所有元素publicvoidgetAll(){ if(top==null){ System.out.println("空栈，无法输出元素！"); } Nodep=top; while(p!=null){ System.out.println(p.data); p=p.next; } }

典型工作任务3.2栈数据结构设计（7）取栈的长度publicintgetLength(){ returnlength; }

（8）清空栈publicvoidclear(){ top=null; }

典型工作任务3.2栈数据结构设计4.链栈操作测试类publicclassTestLinkStack{ publicstaticvoidmain(String[]args){ LinkStackstack=newLinkStack(); stack.push("one"); stack.push("two"); stack.push("three"); stack.push("four"); System.out.println("执行4次入栈后，当前栈中从栈顶到栈底的元素："); stack.getAll(); stack.pop(); stack.pop(); System.out.println("执行2次出栈后，栈中元素个数："+stack.getLength()); System.out.println("执行2次出栈后，栈中从栈顶到栈底的元素："); stack.getAll(); stack.clear(); System.out.println("清空栈后，当前栈是否为空栈？"+stack.isEmpty()); }}

典型工作任务3.2栈数据结构设计结合链栈的8种操作算法，运行结果如下：3.3.1两栈共享空间设计

单如果有两个栈，存储的数据元素类型相同，为它们各自分配数组空间，可能会出现第一个栈已经满了还需要入栈，而再入栈空间就会溢出，另一个栈还有很多存储空间空闲。在两个栈存储的数据元素类型相同的情况下，完全可以共用一个数组空间，这样能够避免一个栈空间溢出而另一个栈空间闲置的情况，能够充分利用存储空间。两栈共用一个数组即两栈共享空间。

典型工作任务3.3栈软件代码设计3.3.2两栈共享空间设计的代码实现1.类的设计

典型工作任务3.3栈软件代码设计publicclassBothStackShared{privateObject[]stack;privatefinalintstackSize=10;privateinttop1;privateinttop2;publicBothStackShared(){}publicbooleanpush(intstackNum,Objectobj){}//入栈publicObjectpop(intstackNum){}//出栈publicbooleanisEmpty(inti){}//判断是否为空栈publicObjectgetTop(inti){}//取栈顶元素}3.3.2两栈共享空间设计的代码实现2.类的实现(1)初始化栈申请一维数组空间，大小为默认值10。

典型工作任务3.3栈软件代码设计publicBothStackShared(){ stack=newObject[stackSize]; top1=-1; top2=stackSize;}3.3.2两栈共享空间设计的代码实现(2)入栈入栈时要明确哪个栈入栈和入栈的数据元素，push()方法两个参数，一个接收栈的编号，一个接收入栈元素。入栈前先判断是否还有存储空间，即栈是否已满，如果未满再进行入栈操作。判断参数stackNum的值，如果是1，栈1要入栈，top1先增1，将数据元素obj放到top1指示的位置；如果stackNum值是2，栈2入栈，top2先减1，再将元素obj放到top2指示的位置。

典型工作任务3.3栈软件代码设计

publicbooleanpush(intstackNum,Objectobj){if(top1+1==top2){//判断栈空间是否已满 System.out.println("栈满，无法入栈！"); returnfalse; } if(stackNum==1){//栈1入栈 top1++; stack[top1]=obj; }else{//栈2入栈 top2--; stack[top2]=obj; } returntrue;}3.3.2两栈共享空间设计的代码实现(3)出栈出栈要知道是哪个栈出栈，pop()方法接收一个参数，即栈的编号。不论哪个栈出栈先判断是否为空栈，如果空栈返回null。栈1出栈，top1减1，栈2出栈top2增1，将栈顶元素作为方法值返回。

典型工作任务3.3栈软件代码设计publicObjectpop(intstackNum){ Objecttemp; if(stackNum==1&&top1==-1){ System.out.println("栈为空"); returnnull; } if(stackNum==2&&top2==stackSize){ System.out.println("栈为空"); returnnull; } if(stackNum==1){//栈1出栈 temp=stack[top1]; top1--; }else{//栈2出栈 temp=stack[top2]; top2++; } returntemp;}3.3.2两栈共享空间设计的代码实现(4)判断是否为空栈先判断哪个栈判空，再判断栈顶指示器的位置。栈1为空的条件是top1==-1,栈2为空的条件是top2==stackSize。

典型工作任务3.3栈软件代码设计publicbooleanisEmpty(intstackNum){if(stackNum==1){//判断栈1是否为空栈 if(top1==-1){ returntrue; }else{ returnfalse; } }else{//判断栈2是否为空栈 if(top2==stackSize){ returntrue; }else{ returnfalse; } }}3.3.2两栈共享空间设计的代码实现(5)取栈顶元素先判断是否为空栈，再取栈顶元素。栈1栈顶元素stack[top1]，栈2栈顶元素stack[top2]。。

典型工作任务3.3栈软件代码设计publicObjectgetTop(intstackNum){ if(stackNum==1){ if(top1==-1){ System.out.println("栈为空"); returnnull; }returnstack[top1];//取栈1的栈顶元素 }else{ if(top2==stackSize){ System.out.println("栈为空"); returnnull; }returnstack[top2];//取栈2的栈顶元素 }}3.测试类实现BothStackShared类实现了两栈共享空间。分别对栈1和栈2进行了入栈、出栈操作，判栈是否为空，获取栈顶元素操作，两个栈能够正常使用，运行结果如下：

典型工作任务3.3栈软件代码设计publicclassTestBothStackShared{publicstaticvoidmain(String[]args){ BothStackSharedstack=newBothStackShared(); stack.push(1,1); System.out.println("栈2是否为空"+stack.isEmpty(2)); stack.push(2,2); System.out.println("栈1是否为空"+stack.isEmpty(1)); stack.push(2,4); stack.push(1,3); stack.push(1,5); System.out.println("栈2出栈元素："+stack.pop(2)); stack.push(2,6); stack.push(2,8); System.out.println("栈1出栈元素："+stack.pop(1)); System.out.println("栈1栈顶元素："+stack.getTop(1)); System.out.println("栈2栈顶元素："+stack.getTop(2)); for(inti=0;i<5;i++) stack.push(2,10); stack.push(1,7); }}

两栈共享的项目测试主要为两个栈是否能够正常使用，并且合理利用空间。借助前面的测试类TestBothStackShared的输出结果，分析栈1和栈2的各种功能实现情况，如表3-1所示。表3-1两栈共享空间测试表

典型工作任务3.4栈软件测试执行测试的功能执行的操作输出的结果栈1数据元素入栈栈1中元素1、3、5入栈后，执行出栈栈1出栈元素：5，说明1、3、5均入栈1，并且5为栈顶元素。栈2数据元素入栈栈2中元素2、4入栈后，执行出栈栈2出栈元素：4，说明2、4均入栈2，并且4为栈顶元素。栈1数据元素出栈栈1中元素1、3、5入栈后，执行出栈栈1出栈元素：5，说明栈1出栈成功。栈2数据元素出栈栈2中元素2、4入栈后，执行出栈栈2出栈元素：4，说明栈2出栈成功。判断栈1是否为空栈1中元素1入栈后，判断栈1是否为空栈栈1是否为空：false，说明当栈1中有元素1时，判断栈1是否为空的操作执行正确。判断栈2是否为空栈2为空栈时，判断栈2是否为空栈栈2是否为空：true，说明当栈2为空时，判断栈2是否为空的操作执行正确。栈1中获取栈顶元素栈1中元素1、3、5入栈，5出栈后，取栈顶元素栈1出栈元素：3，5出栈后，栈1的栈顶元素变为3，说明栈1取栈顶元素操作正确。栈2中获取栈顶元素栈2中元素2、4入栈，4出栈，6、8入栈后取栈顶元素栈2栈顶元