數(shù)據(jù)結(jié)構（Java語言） 課件 項目三 棧-兩棧共享空間

項目三棧---兩棧共享空間目錄項目三5123

典型工作任務3.1棧項目需求分析典型工作任務3.2棧數(shù)據(jù)結(jié)構設計典型工作任務3.3棧軟件代碼設計典型工作任務3.4棧軟件測試執(zhí)行典型工作任務3.5棧軟件文檔編寫46典型工作任務3.6棧項目驗收交付知識目標熟悉棧的特點掌握順序棧的表示和實現(xiàn)掌握鏈式棧的表示和實現(xiàn)技能目標能夠分析棧的應用場合能夠根據(jù)問題選擇合理的存儲結(jié)構能夠熟練使用棧解決問題思政目標養(yǎng)成勤儉節(jié)約的品德養(yǎng)成自覺遵守公共秩序的行為養(yǎng)成良好的文明禮儀培養(yǎng)做事嚴謹、認真的態(tài)度總體要求

在日常生活棧的應用經(jīng)常見到，比如我們往桶里放積木，取積木時，先放入的后取出，后放入的先取出。坐電梯先進去的人最后出來。瀏覽器瀏覽網(wǎng)頁時，有個后退按鈕，點擊后會按鈕訪問的順序逆序后退。

數(shù)學計算時也會遇到棧的應用，進制轉(zhuǎn)換問題，一個十進制數(shù)轉(zhuǎn)換為二進制數(shù)，是計算這個十進制數(shù)除以2的余數(shù)，再用商作為被除數(shù)繼續(xù)計算除以2的余數(shù)，.....，直到商數(shù)為0，轉(zhuǎn)換成的二進制數(shù)是得到的余數(shù)的逆序，即第一個余數(shù)為最低位，最后一個余數(shù)為二進制數(shù)的最高位。

棧的順序存儲結(jié)構在解決實際問題時，會出現(xiàn)空間溢出或者空間浪費的情況，為了解決這一問題，提出數(shù)據(jù)元素類型相同的兩個?？梢怨蚕砜臻g，本項目實現(xiàn)共享棧的類型定義及基本操作。典型工作任務3.1棧項目需求分析3.2.1鏈表結(jié)構設計

棧是一種特殊的線性表，限定在表的一端進行插入元素和刪除元素的操作。允許插入、刪除元素的一端稱為棧頂，另一端稱為棧底。典型工作任務3.2棧數(shù)據(jù)結(jié)構設計元素入棧和出棧過程

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計3.2.2棧的基本操作

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計初始化：構造一個空的棧清空：使棧稱為空棧入棧：在棧頂位置插入新元素出棧：刪除棧頂元素取棧頂元素：獲取棧頂元素的值判空：判斷當前棧是否為空求長度：統(tǒng)計棧中元素個數(shù)加工型引用型3.2.3順序棧1.順序棧概念順序棧利用一維數(shù)組來定義，數(shù)組下標為0的一端作為棧底，定義變量top來指示棧頂元素在順序棧中的位置。top初始值為-1，指向棧底，top==-1也可以作為棧空的標志。當新的數(shù)據(jù)元素入棧時，先把棧頂指針top加1，再把新元素放到top指示的位置。刪除元素時，先取出top指示的棧頂元素，再將棧頂指示器top的值減1。因此，非空的順序棧，棧頂指示器top始終指向棧頂元素的位置入棧、出棧時top位置變化。

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計3.2.3順序棧2.順序棧泛型類的定義如下：publicclassSeqStack{ privatefinalintmaxSize=10; privateObject[]stack; privateinttop; publicSeqStack(){} publicSeqStack(intn){} publicvoidpush(Objectobj){} publicObjectpop(){} publicObjectgetTop(){}publicbooleanisEmpty(){} publicintgetLength(){} publicvoidclear(){}}

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計順序棧中一維數(shù)組的初始長度存儲元素的數(shù)組對象指示棧頂元素在順序棧中的位置3.順序棧的基本操作實現(xiàn)（1）棧的初始化publicSeqStack(){ top=-1; stack=newObject[maxSize];//初始化?？臻g大小為默認值10 }publicSeqStack(intn){//初始化棧空間大小為n if(n<=0){ System.out.println("?？臻g大小非法！"); System.exit(1); } top=-1; stack=newObject[n];/ }

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計(2)入棧publicvoidpush(Objectobj){ if(top==stack.length-1){//如果棧滿，將棧存儲空間擴大到原來的2倍 Object[]temp=newObject[stack.length*2]; for(inti=0;i<stack.length;i++){//原棧數(shù)組中的元素復制到新數(shù)組中 temp[i]=stack[i]; } stack=temp;//棧引用新數(shù)組 } top++;//棧頂指示器增1 stack[top]=obj;//元素入棧 }

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計如果棧滿重新分配存儲空間(3)出棧publicObjectpop(){ if(top==-1){ System.out.println("空棧！"); returnnull; } Objectt=stack[top]; top--; returnt; }

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計出棧后top值要減一(4)取棧頂元素publicObjectgetTop(){ if(top==-1){ System.out.println("\t空棧！"); returnnull; } returnstack[top];//返回棧頂元素 }

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計取棧頂元素top值不變(5)判斷是否為空棧publicbooleanisEmpty(){ returntop==-1; }

（6）求棧長度publicintgetLength(){ returntop+1; }

(7)置空棧

publicvoidclear(){ top=-1; }

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計4.

順序棧類的測試publicclassTestSeqStack{publicstaticvoidmain(String[]args){SeqStackmyStack=newSeqStack();//創(chuàng)建空棧，存儲空間為默認大小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());//獲取棧中元素個數(shù)并輸出

System.out.println("\t棧中元素個數(shù)："+myStack.getLength());for(inti=0;i<15;i++)//入棧元素超過棧的存儲空間時，棧空間擴大到原來2倍

結(jié)合順序棧的七種算法，

myStack.push(100);運行結(jié)果為：

}System.out.println("\t擴充空間后棧中元素個數(shù)："+myStack.getLength());myStack.clear();//置空棧System.out.println("\t置空后棧中元素個數(shù)："+myStack.getLength()); }}

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計3.2.4鏈棧棧的鏈接存儲結(jié)構稱為鏈棧。每個結(jié)點有數(shù)據(jù)域和指針域，分別存儲數(shù)據(jù)元素和直接后繼的存儲位置。棧頂指針就是鏈表的頭指針，它唯一確定一個鏈棧。

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計入棧和出棧過程

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計2.鏈棧類的定義先定義鏈中結(jié)點類：publicclassNode{ publicObjectdata; publicNodenext; publicNode(){ } publicNode(Objectdata){ this.data=data; next=null; } publicNode(Objectdata,Nodenext){ this.data=data; this.next=next; }}

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計鏈棧泛型類的實現(xiàn)如下：publicclassLinkStack{ publicNodetop;//棧頂指針 privateintlength;//棧的長度 publicLinkStack(){}//構造一個空棧 publicvoidpush(Objectobj){}//入棧 publicObjectpop(){}//出棧 publicObjectgetHead(){}//取棧頂元素 publicbooleanisEmpty(){}//判棧是否為空 publicvoidgetAll(){}//輸出棧中所有元素 publicintgetLength(){}//取棧的長度 publicvoidclear(){}//清空棧}

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計3.鏈?；静僮鲗崿F(xiàn)（1）構造一個空棧鏈publicLinkStack(){ top=null; length=0; }

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

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計（3）出棧publicObjectpop(){ if(top==null){ System.out.println("空棧，無法刪除元素！"); returnnull; } Nodep=top; top=top.next; length--; returnp.data; }

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計（4）取棧頂元素publicObjectgetHead(){ if(top==null){ System.out.println("空棧，無法讀取棧頂元素！"); returnnull; } returntop.data; }

(5)判棧是否為空publicbooleanisEmpty(){ returntop==null; }

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計（6）輸出棧中所有元素publicvoidgetAll(){ if(top==null){ System.out.println("空棧，無法輸出元素！"); } Nodep=top; while(p!=null){ System.out.println(p.data); p=p.next; } }

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計（7）取棧的長度publicintgetLength(){ returnlength; }

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

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計4.鏈棧操作測試類publicclassTestLinkStack{ publicstaticvoidmain(String[]args){ LinkStackstack=newLinkStack(); stack.push("one"); stack.push("two"); stack.push("three"); stack.push("four"); System.out.println("執(zhí)行4次入棧后，當前棧中從棧頂?shù)綏５椎脑兀?); stack.getAll(); stack.pop(); stack.pop(); System.out.println("執(zhí)行2次出棧后，棧中元素個數(shù)："+stack.getLength()); System.out.println("執(zhí)行2次出棧后，棧中從棧頂?shù)綏５椎脑兀?); stack.getAll(); stack.clear(); System.out.println("清空棧后，當前棧是否為空棧？"+stack.isEmpty()); }}

典型工作任務3.2棧數(shù)據(jù)結(jié)構設計結(jié)合鏈棧的8種操作算法，運行結(jié)果如下：3.3.1兩棧共享空間設計

單如果有兩個棧，存儲的數(shù)據(jù)元素類型相同，為它們各自分配數(shù)組空間，可能會出現(xiàn)第一個棧已經(jīng)滿了還需要入棧，而再入棧空間就會溢出，另一個棧還有很多存儲空間空閑。在兩個棧存儲的數(shù)據(jù)元素類型相同的情況下，完全可以共用一個數(shù)組空間，這樣能夠避免一個?？臻g溢出而另一個?？臻g閑置的情況，能夠充分利用存儲空間。兩棧共用一個數(shù)組即兩棧共享空間。

典型工作任務3.3棧軟件代碼設計3.3.2兩棧共享空間設計的代碼實現(xiàn)1.類的設計

典型工作任務3.3棧軟件代碼設計publicclassBothStackShared{privateObject[]stack;privatefinalintstackSize=10;privateinttop1;privateinttop2;publicBothStackShared(){}publicbooleanpush(intstackNum,Objectobj){}//入棧publicObjectpop(intstackNum){}//出棧publicbooleanisEmpty(inti){}//判斷是否為空棧publicObjectgetTop(inti){}//取棧頂元素}3.3.2兩棧共享空間設計的代碼實現(xiàn)2.類的實現(xiàn)(1)初始化棧申請一維數(shù)組空間，大小為默認值10。

典型工作任務3.3棧軟件代碼設計publicBothStackShared(){ stack=newObject[stackSize]; top1=-1; top2=stackSize;}3.3.2兩棧共享空間設計的代碼實現(xiàn)(2)入棧入棧時要明確哪個棧入棧和入棧的數(shù)據(jù)元素，push()方法兩個參數(shù)，一個接收棧的編號，一個接收入棧元素。入棧前先判斷是否還有存儲空間，即棧是否已滿，如果未滿再進行入棧操作。判斷參數(shù)stackNum的值，如果是1，棧1要入棧，top1先增1，將數(shù)據(jù)元素obj放到top1指示的位置；如果stackNum值是2，棧2入棧，top2先減1，再將元素obj放到top2指示的位置。

典型工作任務3.3棧軟件代碼設計

publicbooleanpush(intstackNum,Objectobj){if(top1+1==top2){//判斷?？臻g是否已滿 System.out.println("棧滿，無法入棧！"); returnfalse; } if(stackNum==1){//棧1入棧 top1++; stack[top1]=obj; }else{//棧2入棧 top2--; stack[top2]=obj; } returntrue;}3.3.2兩棧共享空間設計的代碼實現(xiàn)(3)出棧出棧要知道是哪個棧出棧，pop()方法接收一個參數(shù)，即棧的編號。不論哪個棧出棧先判斷是否為空棧，如果空棧返回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兩棧共享空間設計的代碼實現(xiàn)(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兩棧共享空間設計的代碼實現(xiàn)(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.測試類實現(xiàn)BothStackShared類實現(xiàn)了兩棧共享空間。分別對棧1和棧2進行了入棧、出棧操作，判棧是否為空，獲取棧頂元素操作，兩個棧能夠正常使用，運行結(jié)果如下：

典型工作任務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的輸出結(jié)果，分析棧1和棧2的各種功能實現(xiàn)情況，如表3-1所示。表3-1兩棧共享空間測試表

典型工作任務3.4棧軟件測試執(zhí)行測試的功能執(zhí)行的操作輸出的結(jié)果棧1數(shù)據(jù)元素入棧棧1中元素1、3、5入棧后，執(zhí)行出棧棧1出棧元素：5，說明1、3、5均入棧1，并且5為棧頂元素。棧2數(shù)據(jù)元素入棧棧2中元素2、4入棧后，執(zhí)行出棧棧2出棧元素：4，說明2、4均入棧2，并且4為棧頂元素。棧1數(shù)據(jù)元素出棧棧1中元素1、3、5入棧后，執(zhí)行出棧棧1出棧元素：5，說明棧1出棧成功。棧2數(shù)據(jù)元素出棧棧2中元素2、4入棧后，執(zhí)行出棧棧2出棧元素：4，說明棧2出棧成功。判斷棧1是否為空棧1中元素1入棧后，判斷棧1是否為空棧棧1是否為空：false，說明當棧1中有元素1時，判斷棧1是否為空的操作執(zhí)行正確。判斷棧2是否為空棧2為空棧時，判斷棧2是否為空棧棧2是否為空：true，說明當棧2為空時，判斷棧2是否為空的操作執(zhí)行正確。棧1中獲取棧頂元素棧1中元素1、3、5入棧，5出棧后，取棧頂元素棧1出棧元素：3，5出棧后，棧1的棧頂元素變?yōu)?，說明棧1取棧頂元素操作正確。棧2中獲取棧頂元素棧2中元素2、4入棧，4出棧，6、8入棧后取棧頂元素棧2棧頂元