項目描述相關知識項目實施項目總結CONTANTS目錄

項目描述某公司的播放器軟件程序的研發工作。播放器的其中一個功能是：從播放列表中順序播放歌曲。設計一個程序，模擬播放器的播放順序功能。項目描述introduction具體系統功能需求如下：（1）可在待播放歌曲列表添加歌曲。（2）當前點擊播放的歌曲因為是最想聽的，應先播放，即后加入歌曲列表的歌曲先播放。（3）待播放列表設定最大長度作為任務1，不設定最大長度作為任務2。（4）輸入錯誤提示：最大長度設定值只能為數字，如輸入字符，系統自動將其設置為默認值20。項目描述introduction本項目利用棧結構存儲待播歌曲。“添加歌曲”功能對應入棧操作，新加的歌曲放在棧頂（待播歌曲欄的最上方），“播放歌曲”功能對應出棧操作，即從棧頂取出最后放入的歌曲，添加到已播歌曲列表。項目描述圖2-1播放器示意圖圖2-2播放器程序界面

相關知識棧的定義棧的基本運算順序棧鏈棧Usefulknowleage相關知識棧的定義棧的基本運算順序棧鏈棧棧是一種特殊的線性表，它僅允許在表的一端進行運算。在表中，允許插入和刪除的一端稱為“棧頂”，另一端稱為“棧底”，將元素插入棧頂的操作成為“進棧”，稱刪除棧頂元素的操作為“出棧”，如圖2-3所示。因為出棧操作時后進棧的元素先出，所以棧也被稱為是一種“后進先出”表，簡稱為LIFO（LastInFirstOut）。1棧的定義圖2-3堆棧根據實際應用，通常認為，棧應該包含了以下一些基本運算：（1）棧初始化——置棧為空棧。（2）判斷棧是否為空——若棧為空，則返回true，否則返回false。（3）求棧的長度——返回棧的元素個數。（4）進棧——將一個元素下推進棧。（5）出棧——將棧頂元素托出棧。（6）讀棧頂——返回棧頂元素。2棧的基本運算抽象數據類型(abstractdatatype,ADT)是帶有一組操作的一些對象的集合，在ADT的定義中只定義了一些基本的操作，沒有提到關于這組操作是如何實現的任何解釋。在Java中，我們用棧的接口IStack表示棧這些功能操作的集合。在后面的例子中，我們將實現這個接口，通過展示不同的實現代碼，詳細解釋順序棧和鏈棧的不同之處。但不管怎樣，只要這些類實現了棧的接口，你就可以將其成為棧。2棧的基本運算棧的接口代碼如下:publicinterfaceIStack{ publicvoidpush(Objectobj)throwsException;//進棧 publicObjectpop()throwsException;//出棧 publicObjectgetTop()throwsException;//取棧頂 publicbooleanisEmpty();//判斷棧是否為空 publicintgetSize();//求棧長}2棧的基本運算與線性表類似，棧的存儲結構也分為順序存儲結構和鏈式存儲結構。順序存儲結構的棧簡稱為順序棧，鏈式存儲結構的棧稱為鏈棧。1)順序存儲定義2)順序棧的基本運算3)順序棧的動手實踐3順序棧1)順序存儲定義與順序線性表類似，順序棧也需要通過一個一維數組存儲元素，同時設置棧頂元素的位置下標，如圖2-4所示。順序棧=一維數組+棧頂指示圖2-4順序棧的存儲結構順序棧用一個類SeqStack實現，其數據類型描述如下:publicclassSeqStackimplementsIStack{ finalintdefaultSize=10; intmaxSize; inttop;//棧頂指示

Object[]stack;//一維數組}順序棧用一維數組stack存放數據，序號為i的元素a_i對應數組的下標是i-1，即用stack[i-1]表示，棧頂用stack[top]表示。棧空及棧滿條件：棧空條件：top=-1。棧滿條件：top=MaxSize-1。2)棧的基本運算

Usefulknowleage判斷棧是否為空2求棧的長度3進棧操作4出棧操作5獲取棧頂元素6棧初始化1打印棧中所有元素72)棧的基本運算出棧操作棧是否為空棧的長度進棧操作棧初始化棧頂元素打印棧中所有元素棧的初始化實現比較簡單，通過添加一個initiate方法，在該方法中將棧頂top的值設置為-1即可，同時創建一個用于存儲棧中元素的一維數組stack，參數sz表示棧的大小。然后在構造函數中調用此方法。publicclassSeqStackimplementsIStack{ finalintdefaultSize=10; intmaxSize; inttop;//棧頂指示 Object[]stack;//一維數組

publicSeqStack(){ initiate(defaultSize); } publicSeqStack(intsz){ initiate(sz); } privatevoidinitiate(intsz){ maxSize=sz; top=-1; stack=newObject[sz]; }}2)棧的基本運算出棧操作棧是否為空棧的長度進棧操作棧初始化棧頂元素打印棧中所有元素此處實現接口中的isEmpty方法。在判斷棧是否為空時，只需將棧頂指示top值與-1相比即可，若top值為-1，則表示順序棧中不包含任何元素，代碼如下。publicbooleanisEmpty(){

returntop==-1;}2)棧的基本運算出棧操作棧是否為空棧的長度進棧操作棧初始化棧頂元素打印棧中所有元素此處實現接口中的getSize方法。棧的長度即為棧中數組的元素個數，因為top值總是指向最后一個元素，考慮到當top值為0時，已經有一個元素存在，則元素的個數為top+1，代碼如下。publicintgetSize(){ returntop+1; }2)棧的基本運算出棧操作棧是否為空棧的長度進棧操作棧初始化棧頂元素打印棧中所有元素此處實現接口中的push方法。假設順序棧中包含元素(a1,a2,a3),將元素e入棧時，實際就是要在棧頂位置插入該元素。相關過程如圖2-5所示，具體步驟為：（1）棧頂指示top朝棧的增長方向前進一步（即top值增1）。（2）將元素放入棧中由當前棧頂top指向的位置上。在棧的這種靜態實現中，進行進棧運算時，必須先進行棧滿檢查，以避免錯誤。

圖2-5將元素入棧2)棧的基本運算出棧操作棧是否為空棧的長度進棧操作棧初始化棧頂元素打印棧中所有元素

publicvoidpush(Objectobj)throwsException{ if(top==maxSize-1) thrownewException("棧滿無法進棧！"); else{ top++; stack[top]=obj; } }2)棧的基本運算出棧操作棧是否為空棧的長度進棧操作棧初始化棧頂元素打印棧中所有元素

此處實現接口中的pop方法。同樣假設順序棧中包含元素(a1,a2,a3),現將a3元素出棧，只需將棧頂指示top后退一步（即top值減1）即可，如圖所示。同時若需在出棧的同時返回該出棧元素，還需通過一個臨時變量獲取a3并返回。應該注意的是，出棧前應進行棧空檢查。 publicObjectpop()throwsException{ if(top==-1) returnnull; else{ Objecte=stack[top]; top--; return(e); } }2)棧的基本運算出棧操作棧是否為空棧的長度進棧操作棧初始化棧頂元素打印棧中所有元素

此處實現接口中的getTop方法。根據棧頂指示top，可以直接獲取最后入棧的元素。應該注意的是，在進行讀取之前，也要進行棧空檢查，代碼如下: publicObjectgetTop()throwsException{ if(top==-1) returnnull; returnstack[top]; }2)棧的基本運算出棧操作棧是否為空棧的長度進棧操作棧初始化棧頂元素打印棧中所有元素

此方法非接口中定義的功能，但可以在SeqStack類中進行擴展，代碼如下: publicvoidprint(){

for(inti=0;i<=top;i++)

System.out.print(stack[i]+"");

System.out.println(); } publicstaticvoidmain(String[]args)throwsException{ //創建一個棧

SeqStackss=newSeqStack(); //判斷是否為空

System.out.println("是否為空："+ss.isEmpty()); //進棧操作,1-10依次進棧

for(inti=0;i<10;i++) ss.push(i+1); //打印棧中元素

ss.print(); //顯示棧頂元素

System.out.println("當前棧頂元素為"+ss.getTop()); //出棧5次，并顯示每一次的出棧元素

for(inti=0;i<5;i++) System.out.println("出棧元素為"+ss.pop()); //顯示棧長

System.out.println("當前棧長為"+ss.getSize()); }測試端代碼圖2-7堆棧程序運行結果3)順序棧的動手實踐12345實現思路實訓內容關鍵代碼運行結果實訓目的掌握順序棧的進棧、出棧等操作，學會較為復雜問題的求解。3)順序棧的動手實踐12345實現思路實訓內容關鍵代碼運行結果實訓目的給定一個只包括'('，')'，'{'，'}'，'['，']'的字符串s，判斷字符串是否有效。有效字符串需滿足：①左括號必須用相同類型的右括號閉合。②左括號必須以正確的順序閉合。示例1示例2示例3示例4示例5輸入：s="()"輸出：true輸入：s="()[]{}"輸出：true輸入：s="(]"輸出：false輸入：s="([)]"輸出：false輸入：s="{[]}"輸出：true3)順序棧的動手實踐12345實現思路實訓內容關鍵代碼運行結果實訓目的如果計算出左括號的數量，和右括號的數量，如果每種括號左右數量相同，會不會就是有效的括號了呢？事實上不是的，假如輸入是[{]}，每種括號的左右數量分別相等，但不是有效的括號。這是因為結果還與括號的位置有關。仔細分析我們發現，對于有效的括號，它的部分子表達式仍然是有效的括號，比如{()[()]}是一個有效的括號，()[{}]是有效的括號，[()]也是有效的括號。并且當我們每次刪除一個最小的括號對時，我們會逐漸將括號刪除完。這個思考的過程其實就是棧的實現過程。因此我們考慮使用棧，當遇到匹配的最小括號對時，我們將這對括號從棧中刪除（即出棧），如果最后棧為空，那么它是有效的括號，反之不是。3)順序棧的動手實踐12345實現思路實訓內容關鍵代碼運行結果實訓目的括號匹配棧的原理圖3)順序棧的動手實踐12345實現思路實訓內容關鍵代碼運行結果實訓目的請讀者理解代碼并填空，運行得到相應結果。 publicstaticbooleanisValid(Strings)throwsException{ SeqStackstk=newSeqStack(s.length()); for(charc:s.toCharArray()) //如果c是({[則入棧

if(c=='('||c=='{'||c=='[')

//如果c是)}]并且棧不為空則判斷棧頂是否為與之對應的左括號。是則出棧，不是則返回fasle elseif(c==')'&&!stk.isEmpty()&&(char)stk.getTop()=='('){

}elseif(c=='}'&&!stk.isEmpty()&&(char)stk.getTop()=='{'){

}elseif(c==']'&&!stk.isEmpty()&&(char)stk.getTop()=='['){

}else{ //如果c是)}]棧為空那么返回false //如果c是)}]棧不為空，但是棧頂不是與c對應的左括號那么返回false returnfalse; } //例如"(){}["，如果最后棧不為空，那么就是有多余的左括號了

returnstk.isEmpty();

}3)順序棧的動手實踐12345實現思路實訓內容關鍵代碼運行結果實訓目的 publicstaticvoidmain(String[]args)throwsException{ Scannerinput=newScanner(System.in); System.out.println("請輸入一個字符串："); Stringtext=input.next(); booleanflag=isValid(text); if(flag) System.out.println(text+"括號匹配"); else System.out.println(text+"括號不匹配"); }測試端代碼3)順序棧的動手實踐12345實現思路實訓內容關鍵代碼運行結果實訓目的順序存儲實現下，每個棧都需要按最大需求留足存儲空間，這必將造成存儲空間的大量浪費。解決此問題的方法之一就是采取棧的鏈式存儲實現。1)棧的鏈式存儲結構2)鏈棧的基本運算3)鏈棧的動手實踐4鏈棧1)棧的鏈式存儲結構棧的鏈式存儲表示也稱為鏈棧，它實際上是一個單鏈表，并以其鏈頭指針作為棧頂指針。鏈棧的結構示意圖如下：因此，進出棧的運算都只能在鏈頭進行。即鏈棧=單鏈表+棧頂指針4鏈棧鏈棧LinkStack類同樣實現了IStack接口，其數據類型描述如下： publicclassLinkStackimplementsIStack{ Nodetop;//棧頂節點

intsize;//節點個數 }其中節點類Node符合單鏈表中節點類的設計思路，即由兩個類成員組成，一個表示元素本身，一個存儲下一個節點的引用，其類型描述如下:publicclassNode{ Objectdata; //數據元素

Nodenext; //表示下一個結點的對象引用

Node(Nodenextval){//用于頭結點的構造函數1 next=nextval; } Node(Objectobj,Nodenextval){//用于其他結點的構造函數2 data=obj; next=nextval; }}4鏈棧棧空條件：top==null；2)鏈棧的基本運算4鏈棧棧初始化進棧操作判斷棧是否為空出棧操作求棧的長度獲取棧頂元素棧初始化2)鏈棧的基本運算棧初始化publicclassLinkStackimplementsIStack{ Nodetop;//棧頂節點

intsize;//節點個數 //構造函數 publicLinkStack(){ top=null;//空棧

size=0;

}}2)鏈棧的基本運算判斷棧是否為空此處實現接口中的isEmpty方法。在判斷棧是否為空時，只需將棧頂節點top與null相比即可，代碼如下: publicbooleanisEmpty(){ returntop==null; }2)鏈棧的基本運算求棧的長度此處實現接口中的getSize方法，代碼如下: publicintgetSize(){ returnsize; }2)鏈棧的基本運算進棧操作此處實現接口中的push方法。假設元素e要進棧，進棧過程如圖所示:相關的操作可按以下步驟進行。(1)形成元素e對應的節點p；Nodep=newNode(e,null);(2)p結點指向原棧頂節點top；p.next=top;(3)棧頂節點top指向p結點。top=p;此外，當進棧時，表示棧長的size也要加1，代碼如下: publicvoidpush(Objecte)throwsException{ Nodep=newNode(e,null); p.next=top; top=p; size++; }2)鏈棧的基本運算出棧操作現接口中的pop方法。假設棧頂節點top要出棧，出棧過程如圖：出棧操作可按照以下步驟進行。(1)首先判斷棧是否為空，為空則無法進行出棧操作，拋出一個異常；if(size==0)thrownewException("堆棧已空");(2)獲取當前棧頂節點top的元素值，用于返回該出棧元素Objectobj=top.data;(3)棧頂節點top沿鏈指向下一節點；釋放之前top的存儲空間。top=top.next;2)鏈棧的基本運算出棧操作當出棧時，表示棧長的size也要減1，代碼如下： publicObjectpop()throwsException{ if(size==0) thrownewException("堆棧已空"); Objectobj=top.data; top=top.next; size--; returnobj;

}2)鏈棧的基本運算打印棧中所有元素此方法非接口中定義的功能，可利用單鏈表的特點進行棧的元素遍歷，實現代碼如下： publicvoidprint(){ Nodecurr=top; while(curr!=null){ System.out.print(curr.data+""); curr=curr.next; } System.out.println(); }2)鏈棧的基本運算打印棧中所有元素要測試上述這些方法，可以編寫測試端代碼如下所示，相關結果如圖所示：

publicstaticvoidmain(String[]args)throwsException{ //創建一個棧類

LinkStackls=newLinkStack(); //判斷是否為空

System.out.println("是否為空："+ls.isEmpty()); //進棧操作,10個隨機數進棧

Randomrnd=newRandom(); for(inti=0;i<10;i++) ls.push(rnd.nextInt(100)); //顯示棧中元素

ls.print(); //顯示棧頂元素

System.out.println("當前棧頂元素為"+ls.getTop()); //出棧5次，并顯示每一次的出棧元素

for(inti=0;i<5;i++) System.out.println("出棧元素為"+ls.pop()); //顯示棧長

System.out.println("當前棧長為"+ls.size()); }在順序棧的遍歷中，我們是從下標為0的數組進行遍歷，因此出棧元素為遍歷序列的最后一個元素。而鏈棧的遍歷中，我們從top棧頂開始進行遍歷，因此出棧元素為遍歷序列的第一個元素。2)鏈棧的基本運算獲取棧頂元素實現接口中的getTop方法。此處直接返回棧頂節點top的數值域部分即可，代碼如下： publicObjectgetTop()throwsException{ returntop.data;

}3)鏈棧的動手實踐實訓目的掌握鏈棧的進棧、出棧等操作，學會較為復雜問題的求解。實訓內容十進制數N和其他d進制數的轉換是計算機實現計算的基本問題，其解決方法很多，其中一個簡單算法基于下列原理：N=(Ndivd)×d+Nmodd(其中:div為整除運算,mod為求余運算)假設現要編制一個滿足下列要求的程序：對于輸入的任意一個非負十進制整數N，選擇一個要轉換的進制d，打印輸出與其等值的d進制數。4鏈棧3)鏈棧的動手實踐實現思路首先你需要先了解這幾種數據類型之間的轉換規則4鏈棧3)鏈棧的動手實踐實現思路在上述計算過程中，第一次求出的值為最低位，最后一次求出的值為最高位。而打印時應從高位到低位進行，恰好與計算過程相反。根據這個特點，我們可以通過入棧出棧來實現，即將計算過程中依次得到的d進制數碼按順序進棧，計算結束后，再順序出棧，并按出棧順序打印輸出，即可得到給定的二進制數。這是利用棧后進先出特性的經典例子。4鏈棧3)鏈棧的動手實踐關鍵代碼 publicstaticvoiddataConversion(intN,intd)throwsException{ LinkStackls=newLinkStack(); while(N!=0){ intx=N%d; //將x入棧

N=N/d; } //打印ls

}4鏈棧 3)鏈棧的動手實踐關鍵代碼 publicstaticvoidmain(String[]args)throwsException{ Scannerinput=newScanner(System.in); System.out.println("請輸入待轉換的十進制正整數："); intnumber=input.nextInt(); System.out.println("請輸入要轉換的進制："); inttype=input.nextInt(); System.out.println("轉換結果"); dataConversion(number,type); }4鏈棧 3)鏈棧的動手實踐運行結果

4鏈棧圖2-16括號匹配運行結果截圖

項目實現任務1：限制隊長的歌曲播放器任務2：不限制隊長的歌曲播放器這個任務要求限制隊長，考慮用順序棧實現，隊長可由用戶手動輸入限制。用順序棧實現點歌程序代碼如下:publicclassPutPlateActionextendsBaseAction{

//順序棧

privateintlistCount=1; privateSeqStackseqStack; privateList<String>listStack;

/** *設置長度 */ publicActionForwardtoPutPlateList(ActionMappingmapping, ActionFormform,HttpServletRequestrequest, HttpServletResponseresponse)throwsException{ listCount=1; intlength=Integer.valueOf(request.getParameter("length")); seqStack=newSeqStack(length); listStack=newArrayList<String>(); request.setAttribute("length",length); returnnewActionForward("/pages/three/putPlateList.jsp"); }任務1：限制隊長的歌曲播放器

/** *更新長度 */ publicActionForwardajaxUpdateLength(ActionMappingmapping, ActionFormform,HttpServletRequestrequest, HttpServletResponseresponse)throwsException{ listCount=1; intlength=Integer.valueOf(request.getParameter("length")); seqStack=newSeqStack(length); listStack=newArrayList<String>(); returnnull; } /** *裝載已播歌曲 */ publicActionForwardajaxLoadList(ActionMappingmapping, ActionFormform,HttpServletRequestrequest, HttpServletResponseresponse)throwsException{ List<ShowBean>list=seqStack.getObjs(); for(Stringstr:listStack){ list.add(newShowBean(str,true)); } renderText(response,getJSON(list)); returnnull; }任務1：限制隊長的歌曲播放器/** *添加歌曲 */ publicActionForwardajaxPushList(ActionMappingmapping, ActionFormform,HttpServletRequestrequest, HttpServletResponseresponse)throwsException{ Stringobj="歌曲"+listCount; try{ seqStack.push(obj);//進入待播棧 }catch(Exceptione){ renderText(response,"1"); returnnull; } listCount++;//待播歌曲加1 renderText(response,"0"); returnnull; }任務1：限制隊長的歌曲播放器 /** *播放歌曲 */ publicActionForwardajaxPopList(ActionMappingmapping, ActionFormform,HttpServletRequestrequest, HttpServletResponseresponse)throwsException{ if(!seqStack.notEmpty()){//待播列表為空則返回 renderText(response,"1"); returnnull; } Stringobj=seqStack.pop()+"";//獲取棧頂的待播歌曲 listStack.add(obj);//添加到已播歌曲列表 renderText(response,"0"); returnnull; }任務1：限制隊長的歌曲播放器該播放器程序包括兩個功能按鈕和兩個展示待播歌曲和已播歌曲的文本框。當用戶點擊“添加歌曲”按鈕后，將把第n首歌曲推入棧中，并放在第n-1首歌曲的上面，此過程顯示在待播歌曲一欄；點擊“播放歌曲”按鈕，則從待播歌曲欄的最上方移動一條歌曲進入已播歌曲欄，如圖所示:任務2：不限制隊長的歌曲播放器圖2-17播放器程序界面任務2和任務1的區別在于，沒有限制待播歌曲的個數。而在之前的項目實現中，我們采用順序棧的方式實現，這種方式需要用到數組，而數組是需要事先給定大小的，這也要求在使用順序棧之前，先要預設一個最大的棧空間。接下來，我們將采用鏈棧的方式解決項目2。鏈棧采用單鏈表的方式實現棧的特點，因此理論上無需考慮棧的最大空間，其大小會隨著鏈表的元素自動變化。任務2：不限制隊長的歌曲播放器用鏈棧實現不限制歌曲數的點歌程序代碼如下:publicclassPutPlateActionextendsBaseAction{ //鏈棧 privateintlinCount=1; privateLinStacklinStack; privateList<String>linList;

publicActionForwardtoPutPlateLin