《數(shù)據(jù)結(jié)構(gòu)與算法項(xiàng)目化教程》課件第3章

學(xué)習(xí)情境３棧和隊(duì)列3.1任務(wù)一棧3.2任務(wù)二隊(duì)列3.3任務(wù)三整合棧和隊(duì)列的操作棧和隊(duì)列是兩種特殊的線性表，線性表增加和刪除操作的位置受到限制，如果插入和刪除操作只允許在線性表的一端進(jìn)行，則為棧；若插入和刪除操作分別在線性表的兩端進(jìn)行，則為隊(duì)列。因此，棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。棧和隊(duì)列在軟件設(shè)計(jì)中廣泛應(yīng)用。由于棧和隊(duì)列的操作比線性表更簡(jiǎn)單，完全可以利用線性表已經(jīng)實(shí)現(xiàn)的操作來實(shí)現(xiàn)棧和隊(duì)列的操作。為了讓學(xué)習(xí)者能更多地學(xué)習(xí)Java操作的思想和方法，與學(xué)習(xí)情境2不同，本學(xué)習(xí)情境的程序?qū)崿F(xiàn)中使用接口和泛型。3.1任務(wù)一棧3.1.1子任務(wù)1認(rèn)識(shí)棧

1．棧棧(stack)是一種特殊的線性表，其插入和刪除操作只允許在線性表的一端進(jìn)行。允許操作的一端稱為棧頂(top)，不允許操作的一端稱為棧底(bottom)。棧中插入數(shù)據(jù)的操作稱為入棧(push)，刪除數(shù)據(jù)的操作稱為出棧(pop)，沒有數(shù)據(jù)的棧稱為空棧，如圖3-1所示。圖3-1棧

2．棧的基本操作棧的操作比較簡(jiǎn)單，基本操作主要有判斷棧是否為空、取出棧頂數(shù)據(jù)值(棧中的數(shù)據(jù)不變)、進(jìn)棧和出棧。進(jìn)棧使得棧中數(shù)據(jù)增加，出棧使得棧中數(shù)據(jù)減少。由于棧的插入和刪除操作只允許在棧頂進(jìn)行，每次入棧數(shù)據(jù)即成為當(dāng)前棧頂數(shù)據(jù)，每次出棧數(shù)據(jù)是最后一個(gè)入棧數(shù)據(jù)，因此棧也稱為后進(jìn)先出(LastInFirstOut)表，就像一摞盤子放進(jìn)一個(gè)尺寸稍大些的桶里，每次進(jìn)出只能一只盤子放在最上面或者從最上面取走一只盤子，不能從中間插入或抽出。如圖3-2所示，如果進(jìn)棧是順序A、B、C、D，全部進(jìn)棧，再全部出棧，則出棧的順序是D、C、B、A。圖3-2進(jìn)棧和出棧

3．定義棧的Java程序接口棧中的數(shù)據(jù)可以是任意數(shù)據(jù)類型。棧的基本類型操作有判斷棧是否為空、進(jìn)棧、出棧和取棧頂數(shù)據(jù)值等。與線性表不同，不能對(duì)棧頂以外的位置index進(jìn)行插入或刪除等操作。創(chuàng)建包，命名為ch3StackQueue，在ch3StackQueue包中創(chuàng)建描述棧操作的接口，并使用泛型，程序如下：packagech3StackQueue;publicinterfaceStack<E> //棧接口{

booleanisEmpty(); //判斷是否空棧，若空棧則返回true

booleanpush(Edata); //數(shù)據(jù)data入棧，若操作成功則返回true

Epop(); //出棧，返回當(dāng)前棧頂數(shù)據(jù)，若?？談t返回null

EgetTop(); //取棧頂數(shù)據(jù)值，未出棧，若棧空則返回null}3.1.2子任務(wù)2操作棧的順序存儲(chǔ)結(jié)構(gòu)

1．順序存儲(chǔ)結(jié)構(gòu)的棧采用順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序棧，操作菜單為：

【1-判斷棧】【2-進(jìn)?！俊?-出棧】【4-取棧頂數(shù)據(jù)】【5-顯示棧所有數(shù)據(jù)】其中“5-顯示棧所有數(shù)據(jù)”本來不是棧的基本操作，只是為了使得程序操作中可以更全面地查看操作結(jié)果是否正確而增加的。操作菜單的程序代碼參閱Menu.java中的SeqStackMenu()。

2．創(chuàng)建順序棧類在ch3StackQueue包中創(chuàng)建SeqStack.java順序棧類，value為存儲(chǔ)棧的數(shù)據(jù)值，top為棧頂數(shù)據(jù)下標(biāo)，空棧則top值為-1，創(chuàng)建帶參數(shù)(棧容量)和無參構(gòu)造方法(固定容量為100或其他值)。程序如下：publicclassSeqStack<E>implementsStack<E> //順序棧類{privateObjectvalue[]; //存儲(chǔ)棧的數(shù)據(jù)值

privateinttop; //top為棧頂數(shù)據(jù)下標(biāo)

publicSeqStack(intcapacity) //帶參構(gòu)造方法，創(chuàng)建指定容量的空棧

{this.value=newObject[capacity];this.top=-1;}publicSeqStack() //默認(rèn)構(gòu)造方法，創(chuàng)建指定容量的空棧

{this(100);}}

3．順序棧基本算法

(1)判斷棧是否為空。中文描述算法： 如果?？? 返回真 否則 返回假用程序設(shè)計(jì)語(yǔ)言描述算法：

if(this.top==-1) returntrue else returnfalse;因?yàn)樵贘ava中this.top==-1本身就是兩個(gè)結(jié)果true或false，所以此處可以直接用一個(gè)語(yǔ)句代替上述四行程序：

returnthis.top==-1;這樣程序更簡(jiǎn)潔。

(2)進(jìn)棧。中文描述算法(如圖3-3所示)：如果棧滿則擴(kuò)充容量 棧的指針上移 將進(jìn)棧數(shù)據(jù)賦值給棧單元圖3-3順序存儲(chǔ)進(jìn)棧操作

(3)出棧。中文描述算法(如圖3-4所示)：如果棧空則返回空取出棧頂數(shù)據(jù)棧的指針下移

(4)取出棧頂數(shù)據(jù)值。取出棧頂數(shù)據(jù)值，棧中的數(shù)據(jù)不變，此時(shí)指針不動(dòng)即可。圖3-4順序存儲(chǔ)出棧操作

(5)顯示棧中各數(shù)據(jù)的內(nèi)容。這不是棧的基本操作，而是為了使得程序操作中可以更全面地查看操作結(jié)果是否正確而增加的，所以不能對(duì)top指針進(jìn)行直接增減操作，可以將top值賦給一個(gè)變量i，讀出棧中所有數(shù)據(jù)值。中文描述算法： 如果棧非空

top賦給i

從i到0將棧的數(shù)據(jù)值加到字符串str

返回串str

4．程序?qū)崿F(xiàn)順序棧順序棧類SeqStack.java操作的完整代碼如下：

packagech3StackQueue;

publicclassSeqStack<E>implementsStack<E> //順序棧類

{

privateObject[]value; //存儲(chǔ)棧的數(shù)據(jù)值

privateinttop; //top為棧頂數(shù)據(jù)下標(biāo)

publicSeqStack(intcapacity) //帶參構(gòu)造方法，創(chuàng)建指定容量的空棧

{

this.value=newObject[capacity];

this.top=-1;

}publicSeqStack() //默認(rèn)構(gòu)造方法，創(chuàng)建指定容量的空棧

{this(100);}publicbooleanisEmpty() //判斷是否空棧，若空棧則返回true{returnthis.top==-1;}

publicbooleanpush(Edata) //數(shù)據(jù)data入棧，若操作成功則返回true{if(data==null){returnfalse; //空對(duì)象(null)不能入棧

}if(this.top==value.length-1) //若棧滿，則擴(kuò)充容量

{Object[]temp=this.value;this.value=newObject[temp.length*2];for(inti=0;i<temp.length;i++){

this.value[i]=temp[i];}}this.top++;this.value[this.top]=data;returntrue;}

publicEpop()

//出棧，返回當(dāng)前棧頂數(shù)據(jù)，若?？談t返回null{if(!isEmpty()){return(E)this.value[this.top--];}else{returnnull;}}

publicEgetTop()

//取棧頂數(shù)據(jù)值，未出棧，棧頂數(shù)據(jù)未改變

{if(!isEmpty()){return(E)this.value[this.top];}else{returnnull;}}@OverridepublicStringtoString() //返回棧中各數(shù)據(jù)的字符串

{Stringstr="[";if(this.top!=-1){str+=this.value[this.top].toString();}

for(inti=this.top-1;i>=0;i--){

str+=","+this.value[i].toString();}returnstr+"]";}}3.1.3子任務(wù)3操作棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

1．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧稱為鏈棧，操作菜單與順序存儲(chǔ)一樣：

【1-判斷?！俊?-進(jìn)?！俊?-出?！俊?-取棧頂數(shù)據(jù)】【5-顯示棧所有數(shù)據(jù)】同樣，“5-顯示棧所有數(shù)據(jù)”本來不是棧的基本操作，只是為了使得程序操作中可以更全面地查看操作結(jié)果是否正確而增加的。操作菜單的程序代碼參閱Menu.java中的linkStackMenu()。

2．創(chuàng)建鏈?zhǔn)酱鎯?chǔ)棧類

(1)在ch3StackQueue包中創(chuàng)建鏈?zhǔn)酱鎯?chǔ)的單鏈表節(jié)點(diǎn)類Node.java，data為數(shù)據(jù)域，用于保存棧的數(shù)據(jù)，next為地址域，引用后繼節(jié)點(diǎn)。程序代碼如下：//單鏈表節(jié)點(diǎn)類packagech3StackQueue;publicclassNode<E> //單鏈表節(jié)點(diǎn)類{privateEdata;

//數(shù)據(jù)域，保存數(shù)據(jù)

privateNode<E>next; //地址域，引用后繼節(jié)點(diǎn)

publicNode(Edata,Node<E>next) //構(gòu)造節(jié)點(diǎn)，指定數(shù)據(jù)和后繼節(jié)點(diǎn)

{this.data=data;this.next=next;}publicNode(Edata) //構(gòu)造節(jié)點(diǎn)，指定數(shù)據(jù)，后繼節(jié)點(diǎn)為空

{this(data,null);}publicNode() //構(gòu)造節(jié)點(diǎn)，數(shù)據(jù)和后繼節(jié)點(diǎn)均為空

{this(null,null);}publicStringtoString() //返回節(jié)點(diǎn)數(shù)據(jù)值對(duì)應(yīng)的字符串

{returnthis.getData().toString();}publicEgetData(){returndata;}publicvoidsetData(Edata){this.data=data;}publicNode<E>getNext(){returnnext;}publicvoidsetNext(Node<E>next){this.next=next;}}

(2)在ch3StackQueue包中創(chuàng)建LinkStack.java鏈棧類，使用節(jié)點(diǎn)類Node構(gòu)造棧頂數(shù)據(jù)top，并創(chuàng)建LinkStack()構(gòu)造方法，程序代碼如下：

publicclassLinkStack<E>implementsStack<E> //鏈?zhǔn)綏ｎ?/p>

{

privateNode<E>top;

publicLinkStack() //構(gòu)造空棧

{

this.top=null; //棧頂節(jié)點(diǎn)

}

}

3．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的?；舅惴?/p>

(1)判斷棧是否為空。算法：如果棧頂數(shù)據(jù)top==null則棧為空

(2)進(jìn)棧。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的出棧如圖3-5所示。圖3-5鏈?zhǔn)酱鎯?chǔ)進(jìn)棧操作算法： 構(gòu)造新節(jié)點(diǎn)(指向棧頂)

棧頂引用指向新節(jié)點(diǎn)如果鏈?zhǔn)酱鎯?chǔ)棧底節(jié)點(diǎn)作為頭節(jié)點(diǎn)，如圖3-6所示，則進(jìn)棧操作算法：先構(gòu)造新節(jié)點(diǎn)，新節(jié)點(diǎn)引用為空棧頂節(jié)點(diǎn)的引用指向新節(jié)點(diǎn)頭節(jié)點(diǎn)引用指向新節(jié)點(diǎn)這樣算法每次進(jìn)棧前都要從棧底通過引用到尋找棧頂節(jié)點(diǎn)，再進(jìn)行進(jìn)棧操作，消耗時(shí)間，出棧類似，所以本教程的程序采用圖3-5所示的操作。圖3-6鏈?zhǔn)酱鎯?chǔ)棧底為頭節(jié)點(diǎn)

(3)出棧。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的出棧如圖3-7所示。中文描述算法：如果棧空則返回空 取出棧頂數(shù)據(jù)棧頂引用指向其下一個(gè)數(shù)據(jù)(Java垃圾自動(dòng)回收機(jī)制會(huì)處理原來?xiàng)ｍ數(shù)臄?shù)據(jù))

(4)取出棧頂數(shù)據(jù)值。取出棧頂數(shù)據(jù)值，棧中的數(shù)據(jù)不變，此時(shí)棧頂?shù)囊貌蛔?。圖3-7鏈?zhǔn)酱鎯?chǔ)出棧操作

(5)顯示棧中各數(shù)據(jù)的內(nèi)容。這不是棧的基本操作，而是為了使得程序操作中可以更全面地查看操作結(jié)果是否正確而增加的，所以不能對(duì)top引用進(jìn)行直接移動(dòng)操作，可以將top引用值賦給一個(gè)臨時(shí)引用p，若p非空則循環(huán)讀出棧中所有數(shù)據(jù)值。中文描述算法： 棧頂引用賦給臨時(shí)引用如果臨時(shí)引用非空將棧的數(shù)據(jù)值加到字符串str臨時(shí)引用指向其下一個(gè)數(shù)據(jù) 返回串str

4．程序?qū)崿F(xiàn)鏈?zhǔn)酱鎯?chǔ)棧鏈?zhǔn)酱鎯?chǔ)棧類LinkStack.java操作的完整代碼如下：

packagech3StackQueue;

publicclassLinkStack<E>implementsStack<E> //鏈?zhǔn)綏ｎ?/p>

{

privateNode<E>top;

publicLinkStack() //構(gòu)造空棧

{

this.top=null; //棧頂節(jié)點(diǎn)

}

publicbooleanisEmpty() //判斷是否空棧

{

returnthis.top==null;

}

publicbooleanpush(Edata) //數(shù)據(jù)data入棧，若操作成功則返回true

{

if(data==null)

returnfalse; //空對(duì)象(null)不能入棧

//在原棧頂之前插入節(jié)點(diǎn)作為新的棧頂節(jié)點(diǎn)

this.top=newNode(data,this.top);

returntrue;

}

publicEpop() //出棧，返回當(dāng)前棧頂數(shù)據(jù)，若?？談t返回null{if(!isEmpty()){Etemp=this.top.getData(); //取得棧頂節(jié)點(diǎn)值

this.top=this.top.getNext(); //刪除棧頂節(jié)點(diǎn)

returntemp;}returnnull;}

publicEgetTop() //取棧頂數(shù)據(jù)值，未出棧，若?？談t返回null{if(!isEmpty())returnthis.top.getData();returnnull;}@OverridepublicStringtoString() //返回棧中各數(shù)據(jù)的字符串描述

{Stringstr="[";Node<E>p=this.top;while(p!=null)

{str+=p.getData().toString();p=p.getNext();if(p!=null)str+=",";}returnstr+"]";}}3.2任務(wù)二隊(duì)列3.2.1子任務(wù)1認(rèn)識(shí)隊(duì)列

1．隊(duì)列(queue)隊(duì)列是一種特殊的線性表，其插入和刪除操作分別在線性表的兩端進(jìn)行。在隊(duì)列某一端插入數(shù)據(jù)稱為入隊(duì)(enqueue)；在另外一端刪除數(shù)據(jù)的過程稱為出隊(duì)(dequeue)。允許入隊(duì)的一端稱為后端或隊(duì)尾(rear)，允許出隊(duì)的一端稱為前端或隊(duì)頭(front)。沒有數(shù)據(jù)的隊(duì)列稱為空隊(duì)列。隊(duì)列如圖3-8所示。圖3-8隊(duì)列

2．隊(duì)列的基本操作隊(duì)列的操作也比較簡(jiǎn)單，基本操作主要有判斷隊(duì)列是否為空、進(jìn)隊(duì)、出隊(duì)和顯示隊(duì)頭數(shù)據(jù)等。進(jìn)隊(duì)列使得隊(duì)列中的數(shù)據(jù)增加，出隊(duì)列使得隊(duì)列中的數(shù)據(jù)減少。由于隊(duì)列的插入和刪除操作只允許在隊(duì)列的兩端進(jìn)行，每次入隊(duì)列數(shù)據(jù)即成為當(dāng)前隊(duì)尾數(shù)據(jù)，每次出隊(duì)列數(shù)據(jù)是最早入隊(duì)的數(shù)據(jù)，因此隊(duì)列也稱為先進(jìn)先出(FirstInFirstOut)表，就像火車經(jīng)過中途站臺(tái)，先進(jìn)入站臺(tái)的車廂先離開站臺(tái)一樣。如圖3-8所示，如果進(jìn)隊(duì)的順序是A、B、C，則出隊(duì)列的順序是A、B、C。

3．定義隊(duì)列的Java程序接口隊(duì)列中的數(shù)據(jù)可以是任意數(shù)據(jù)類型。隊(duì)列的基本類型操作有判斷隊(duì)是否為空、進(jìn)隊(duì)、出隊(duì)和取隊(duì)頭數(shù)據(jù)值等。與普通線性表不同，不能對(duì)隊(duì)尾以外的位置index進(jìn)行插入操作或隊(duì)頭以外的位置index進(jìn)行刪除操作。在ch3StackQueue包中創(chuàng)建描述隊(duì)操作的接口Queue.java，并使用泛型，程序如下：

packagech3StackQueue;

publicinterfaceQueue<E> //隊(duì)列接口

{

booleanisEmpty();//判斷隊(duì)列是否為空，若空則返回true

booleanenQueue(Eelement); //數(shù)據(jù)element入隊(duì)，若操作成功則返回true

EdeQueue(); //出隊(duì)，返回當(dāng)前隊(duì)頭數(shù)據(jù)，若隊(duì)列空則返回null

EgetFront(); //取隊(duì)頭數(shù)據(jù)值，未出隊(duì)，若隊(duì)空則返回null

}3.2.2子任務(wù)2操作隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

1．順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列采用順序存儲(chǔ)結(jié)構(gòu)的隊(duì)稱為順序隊(duì)，操作菜單為：

【1-判斷隊(duì)空】【2-進(jìn)隊(duì)】【3-出隊(duì)】【4-顯示隊(duì)頭數(shù)據(jù)】【5-顯示隊(duì)所有數(shù)據(jù)】“5-顯示隊(duì)所有數(shù)據(jù)”本來不是隊(duì)的基本操作，只是為了使得程序操作中可以更全面地查看操作結(jié)果是否正確而增加的。操作菜單的程序代碼參閱Menu.java中的seqqueueMenu()。

2．創(chuàng)建順序隊(duì)列類在ch3StackQueue包中創(chuàng)建SeqQueue.java順序隊(duì)類，value為存儲(chǔ)隊(duì)的數(shù)據(jù)值，front為隊(duì)頭數(shù)據(jù)的下標(biāo)，rear為隊(duì)尾數(shù)據(jù)的下標(biāo)，空隊(duì)則front等于rear，創(chuàng)建帶參數(shù)(隊(duì)容量)和無參構(gòu)造方法(固定容量為100或其他值)的隊(duì)。程序代碼如下：

packagech3StackQueue;

publicclassSeqQueue<E>implementsQueue<E> //順序循環(huán)隊(duì)列類

{

publicObject[]value; //存儲(chǔ)隊(duì)列的數(shù)據(jù)

publicintfront,rear; //front、rear為隊(duì)列頭、尾下標(biāo)

publicSeqQueue(intcapacity) //構(gòu)造指定容量的空隊(duì)列

{

this.value=newObject[capacity];

this.front=this.rear=0;

}

publicSeqQueue() //構(gòu)造默認(rèn)容量的空隊(duì)列

{

this(100);

}

}

3．順序隊(duì)列基本算法

(1)判斷隊(duì)是否為空。中文描述算法： 如果隊(duì)空(front等于rear)

返回真 否則 返回假

(2)進(jìn)隊(duì)。中文描述算法(如圖3-9所示)：如果隊(duì)滿則擴(kuò)充容量 隊(duì)尾的指針加1圖 將進(jìn)隊(duì)數(shù)據(jù)賦值給隊(duì)尾存儲(chǔ)單元圖3-9順序存儲(chǔ)隊(duì)列的進(jìn)隊(duì)操作

(3)出隊(duì)。中文描述算法(如圖3-10所示)：如果隊(duì)空則返回空 取出隊(duì)頭數(shù)據(jù)隊(duì)的指針加1

(4)取出隊(duì)頭數(shù)據(jù)值。取出隊(duì)頭數(shù)據(jù)值，隊(duì)中的數(shù)據(jù)不變，此時(shí)指針不改變即可。3-10順序存儲(chǔ)隊(duì)列的出隊(duì)操作

(5)顯示隊(duì)中各數(shù)據(jù)的內(nèi)容。這不是隊(duì)的基本操作，將隊(duì)頭front值賦給一個(gè)變量i，從i開始到隊(duì)尾rear讀出隊(duì)中所有數(shù)據(jù)值。中文描述算法： 如果隊(duì)非空

front賦給i

從i到rear將隊(duì)的數(shù)據(jù)值加到字符串str

返回串str

4．程序?qū)崿F(xiàn)順序隊(duì)列順序隊(duì)類SeqQueue.java操作的完整代碼如下：

packagech3StackQueue;

publicclassSeqQueue<E>implementsQueue<E>//順序循環(huán)隊(duì)列類

{

publicObject[]value; //存儲(chǔ)隊(duì)列的數(shù)據(jù)

publicintfront,rear; //front、rear為隊(duì)列頭、尾下標(biāo)

publicSeqQueue(intcapacity)//構(gòu)造指定容量的空隊(duì)列

{

this.value=newObject[capacity];

this.front=this.rear=0;

}

publicSeqQueue() //構(gòu)造默認(rèn)容量的空隊(duì)列

{

this(100);

}

publicbooleanisEmpty()

//判斷隊(duì)列是否空，若空則返回true

{

returnthis.front==this.rear;

//

}

publicbooleanenQueue(Edata) //數(shù)據(jù)data進(jìn)隊(duì)，若操作成功則返回true

{

if(data==null){

returnfalse; //空對(duì)象(null)不能進(jìn)隊(duì)

}if(this.front==(this.rear+1)%this.value.length){//若隊(duì)列滿，則擴(kuò)充容量

Object[]temp=this.value;this.value=newObject[temp.length*2];inti=this.front,j=0;while(i!=this.rear) //按隊(duì)列數(shù)據(jù)次序復(fù)制數(shù)組數(shù)據(jù)

{this.value[j]=temp[i];i=(i+1)%temp.length;j++;}this.front=0;this.rear=j;}

this.value[this.rear]=data; //this.rear=(this.rear+1)%this.value.length;returntrue;}publicEdeQueue() //出隊(duì)，返回當(dāng)前隊(duì)頭數(shù)據(jù)，若隊(duì)列空則返回null{if(!isEmpty())//隊(duì)列不空

{Etemp=(E)this.value[this.front]; //取得隊(duì)頭數(shù)據(jù)

this.front=(this.front+1)%this.value.length;returntemp;}returnnull;}publicEgetFront(){if(!isEmpty()){ //隊(duì)列不空

Etemp=(E)this.value[this.front]; //取得隊(duì)頭數(shù)據(jù)

returntemp;}else{returnnull;}}@OverridepublicStringtoString() //返回隊(duì)列中各數(shù)據(jù)的字符串描述

{Stringstr="[";if(!isEmpty()){str+=this.value[this.front].toString();inti=(this.front+1)%this.value.length;while(i!=this.rear){str+=","+this.value[i].toString();i=(i+1)%this.value.length;}}returnstr+"]";}}3.2.3子任務(wù)3操作棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

1．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列稱為鏈?zhǔn)疥?duì)列，操作菜單為：

【1-判斷隊(duì)空】【2-進(jìn)隊(duì)】【3-出隊(duì)】【4-顯示隊(duì)頭數(shù)據(jù)】【5-顯示隊(duì)所有數(shù)據(jù)】與順序存儲(chǔ)結(jié)構(gòu)的隊(duì)操作一樣，“5-顯示隊(duì)所有數(shù)據(jù)”本來不是鏈隊(duì)的基本操作，只是為了使得程序操作中可以更全面地查看操作結(jié)果是否正確而增加的。操作菜單的程序代碼參閱Menu.java中的linkqueueMenu()。

2．創(chuàng)建鏈?zhǔn)疥?duì)列類在“3.1.3子任務(wù)3操作棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)”中已經(jīng)創(chuàng)建鏈?zhǔn)酱鎯?chǔ)的單鏈表節(jié)點(diǎn)類Node.java，data為數(shù)據(jù)域，用于保存棧的數(shù)據(jù)，next為地址域，引用后繼節(jié)點(diǎn)。鏈?zhǔn)焦?jié)點(diǎn)可以用于鏈?zhǔn)綏：玩準(zhǔn)疥?duì)列，所以這里可以使用該Node類。在ch3StackQueue包中創(chuàng)建LinkQueue.java鏈?zhǔn)疥?duì)類，front和rear分別指向隊(duì)頭和隊(duì)尾節(jié)點(diǎn)，空隊(duì)則front和rear都為null，構(gòu)造空隊(duì)列就是front和rear都賦值為null。定義LinkQueue.java鏈?zhǔn)疥?duì)類的代碼如下：

packagech3StackQueue;

publicclassLinkQueue<E>implementsQueue<E> //鏈?zhǔn)疥?duì)列類

{

privateNode<E>front,rear; //front和rear分別指向隊(duì)頭和隊(duì)尾節(jié)點(diǎn)

publicLinkQueue() //構(gòu)造空隊(duì)列

{

this.front=this.rear=null; }

}

3．鏈?zhǔn)疥?duì)列基本算法

(1)判斷隊(duì)是否為空。中文描述算法： 如果隊(duì)空(front和rear均為null)

返回真 否則 返回假

(2)進(jìn)隊(duì)。中文描述算法(如圖3-11所示)：創(chuàng)建新節(jié)點(diǎn)如果隊(duì)空則隊(duì)頭和隊(duì)尾均指向新節(jié)點(diǎn) 否則 隊(duì)尾引用指向新節(jié)點(diǎn)圖3-11鏈?zhǔn)酱鎯?chǔ)隊(duì)列的進(jìn)隊(duì)操作

(3)出隊(duì)。中文描述算法(如圖3-12所示)：如果隊(duì)空則返回空 取出隊(duì)頭數(shù)據(jù)隊(duì)頭的引用指向其下一個(gè)節(jié)點(diǎn)

(4)取出隊(duì)頭數(shù)據(jù)值。取出隊(duì)頭數(shù)據(jù)值，隊(duì)中的數(shù)據(jù)不變，此時(shí)隊(duì)頭的引用不改變即可。圖3-12鏈?zhǔn)酱鎯?chǔ)隊(duì)列的出隊(duì)操作

(5)顯示隊(duì)中各數(shù)據(jù)的內(nèi)容。這不是隊(duì)的基本操作，將隊(duì)頭front引用賦給一個(gè)臨時(shí)引用p，從p開始到隊(duì)尾rear讀出隊(duì)中所有數(shù)據(jù)值。中文描述算法： 如果隊(duì)非空

front引用賦給一個(gè)臨時(shí)引用p

從p到rear將隊(duì)的數(shù)據(jù)值加到字符串str

返回串str

4．程序?qū)崿F(xiàn)鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列類LinkQueue.java操作的完整代碼如下：

packagech3StackQueue;

publicclassLinkQueue<E>implementsQueue<E> //鏈?zhǔn)疥?duì)列類

{

privateNode<E>front,rear; //front和rear分別指向隊(duì)頭和隊(duì)尾節(jié)點(diǎn)

publicLinkQueue() //構(gòu)造空隊(duì)列

{

this.front=this.rear=null;

}

publicbooleanisEmpty() //判斷隊(duì)列是否空，若空則返回true{returnthis.front==null&&this.rear==null;}publicbooleanenQueue(Edata) //數(shù)據(jù)data入隊(duì)，若操作成功則返回true{if(data==null){returnfalse; //空對(duì)象(null)不能入隊(duì)

}Node<E>newnode=newNode(data);if(!isEmpty()) //隊(duì)列不空時(shí){this.rear.setNext(newnode);

//q節(jié)點(diǎn)作為新的隊(duì)尾節(jié)點(diǎn)

}else{this.front=newnode;}this.rear=newnode;returntrue;}

publicEdeQueue() //出隊(duì)，返回當(dāng)前隊(duì)頭數(shù)據(jù)，若隊(duì)列空則返回null{if(!isEmpty()){Etemp=this.front.getData(); //取得隊(duì)頭數(shù)據(jù)

this.front=this.front.getNext(); //刪除隊(duì)頭節(jié)點(diǎn)

if(this.front==null){this.rear=null;}returntemp;}else{returnnull;}}

publicEgetFront(){if(!isEmpty()){Etemp=this.front.getData(); //取得隊(duì)頭數(shù)據(jù)

returntemp;}else{returnnull;}}@OverridepublicStringtoString() //返回棧中各數(shù)據(jù)的字符串描述

{Stringstr="[";Node<E>p=this.front;while(p!=null){str+=p.getData().toString();p=p.getNext();if(p!=null){str+=",";}}returnstr+"]";}}3.3任務(wù)三整合棧和隊(duì)列的操作本學(xué)習(xí)情境介紹了棧和隊(duì)列的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的操作，共有四類基本操作：棧的順序存儲(chǔ)操作、棧的鏈?zhǔn)酱鎯?chǔ)的操作、隊(duì)列的順序存儲(chǔ)操作、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)的操作，四類操作又有五種基本具體操作，比較整齊劃一，可以把這四類操作整合在一起。這需要構(gòu)造兩級(jí)操作菜單系統(tǒng)，第一級(jí)操作菜單如下：選擇其中一項(xiàng)目菜單后，進(jìn)入各自的二級(jí)菜單操作，在前面的各任務(wù)中都已經(jīng)介紹菜單項(xiàng)和操作實(shí)現(xiàn)，所以本任務(wù)只要做出主程序菜單即可。3.3.1子任務(wù)1構(gòu)造主程序

1．構(gòu)造棧和隊(duì)列實(shí)現(xiàn)的主程序由于棧和隊(duì)列在一級(jí)操作菜單下具有四個(gè)二級(jí)菜單，所以可以把菜單抽取出來作為一個(gè)Menu類，而構(gòu)造主程序只需調(diào)用菜單類即可，先構(gòu)造主程序如下：

packagech3StackQueue;

publicclassMain{

publicstaticvoidmain(String[]args){

}

}等“3.3.2子任務(wù)2構(gòu)造菜單程序”完成后再轉(zhuǎn)回下面的“2.主程序Main.java完整代碼”，調(diào)用菜單類的主菜單即可實(shí)現(xiàn)完整系統(tǒng)。

2．主程序Main.java完整代碼

packagech3StackQueue;

publicclassMain{

publicstaticvoidmain(String[]args){

Menumenu=newMenu(); //創(chuàng)建主菜單對(duì)象

menu.mainMenu(); //調(diào)用主菜單方法

}

}3.3.2子任務(wù)2構(gòu)造菜單程序

1．構(gòu)造一級(jí)菜單與學(xué)習(xí)情境2中的線性表菜單構(gòu)造類似，先構(gòu)造一級(jí)菜單。詳細(xì)代碼見Menu.java。

2．構(gòu)造二級(jí)菜單構(gòu)造四個(gè)二級(jí)菜單的方法包括：棧的順序存儲(chǔ)結(jié)構(gòu)操作seqstackMenu()、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)操作linkStackMenu()、隊(duì)的順序存儲(chǔ)結(jié)構(gòu)操作seqqueueMenu()、隊(duì)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)操作linkqueueMenu()。詳細(xì)代碼見Menu.java。3．棧和隊(duì)操作菜單Menu.java完整代碼

packagech3StackQueue;

importjava.util.Scanner;

publicclassMenu{

Scannerinput=newScanner(System.in);

Stringdata;publicvoidmainMenu()//主菜單

{intselect;do{System.out.print("\n\n");System.out.print("\t\t☆★☆棧和隊(duì)操作主菜單☆★☆\n");System.out.print("\n");System.out.print("\t【1-棧的順序存儲(chǔ)結(jié)構(gòu)】");System.out.print("\t【2-棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)】\n");System.out.print("\t【3-隊(duì)的順序存儲(chǔ)結(jié)構(gòu)】");System.out.print("\t【4-隊(duì)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)】\n");System.out.print("\t\t\t【5-退出】\n");System.out.print("\n");System.out.print("\t請(qǐng)選擇：");

select=input.nextInt();switch(select){case1:seqstackMenu();break;case2:linkStackMenu();break;case3:seqqueueMenu();break;case4:linkqueueMenu();break;case5:System.out.println("\t^_^感謝您的使用^_^\n");System.out.print("\t歡迎下次使用\n");System.out.print("\t再★見\n");System.exit(0);break;default:continue;}}while(true);}publicvoidseqstackMenu() //棧的順序存儲(chǔ)結(jié)構(gòu)操作菜單

{SeqStack<String>seqstack=newSeqStack<String>();intselect=0;do{System.out.print("\n");System.out.print("\t\t☆★☆棧的順序存儲(chǔ)結(jié)構(gòu)的操作菜單☆★☆\n");System.out.print("\n");System.out.print("\t【1-判斷?！俊?-進(jìn)棧】");System.out.print("\t【3-出?！俊?-取棧頂數(shù)據(jù)】");System.out.print("\t【5-顯示棧所有數(shù)據(jù)】\n");System.out.print("\t【6-返回上一級(jí)菜單】\n");System.out.print("\n請(qǐng)選擇:");

select=input.nextInt();switch(select){case1:if(seqstack.isEmpty()==true){System.out.println("\t棧為空！");}else{System.out.println("\t棧中有數(shù)據(jù)!");}break;case2:System.out.print("\t輸入要進(jìn)棧的數(shù)據(jù)：");data=input.next();seqstack.push(data);System.out.print("\t進(jìn)棧數(shù)據(jù)為："+data+"\n");break;

case3:System.out.println("\t出棧數(shù)據(jù)為："+seqstack.pop());break;case4:System.out.println("\t棧頂數(shù)據(jù)為："+seqstack.getTop());break;case5:System.out.println("\t棧頂"+seqstack.toString()+"棧底");

break;case6:mainMenu();break;default:continue;}}while(true);}//棧的順序存儲(chǔ)操作菜單結(jié)束

publicvoidlinkStackMenu()//棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)操作菜單

{LinkStack<String>linkstack=newLinkStack<String>();intselect;

do{System.out.print("\n");System.out.print("\n");System.out.print("\t\t☆★☆棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的操作菜單☆★☆\n");System.out.print("\n");System.out.print("\t【1-判斷?！俊?-進(jìn)?！?);System.out.print("\t【3-出棧】【4-取棧頂數(shù)據(jù)】");System.out.print("\t【5-顯示棧所有數(shù)據(jù)】\n");

System.out.print("\t【6-返回上一級(jí)菜單】\n");System.out.print("\n\n\t請(qǐng)選擇:");select=input.nextInt();switch(select){case1:if(linkstack.isEmpty()==true){System.out.println("\t棧為空！");}else{System.out.println("\t棧中有數(shù)據(jù)!");}break;

case2:System.out.print("\t輸入要進(jìn)棧的數(shù)據(jù)：");data=input.next();linkstack.push(data);System.out.print("\t進(jìn)棧數(shù)據(jù)為："+data+"\n");break;case3:System.out.println("\t出棧數(shù)據(jù)為："+linkstack.pop());break;case4:System.out.println("\t棧頂數(shù)據(jù)為："+linkstack.getTop());break;

case5:System.out.println("\t棧頂"+linkstack.toString()+"棧底");break;case6:mainMenu();break;default:continue;}}while(true);

}//棧的鏈?zhǔn)酱鎯?chǔ)操作菜單結(jié)束publicvoidseqqueueMenu()//隊(duì)的順序存儲(chǔ)結(jié)構(gòu)操作菜單

{SeqQueue<String>seqqueue=newSeqQueue<String>(5);intselect;do{System.out.print("\n");System.out.print("\n");System.out.print("\t\t☆★☆隊(duì)的順序存儲(chǔ)結(jié)構(gòu)的操作菜單☆★☆\n");System.out.print("\n");System.out.print("\t【1-判斷隊(duì)空】【2-進(jìn)隊(duì)】");System.out.print("\t【3-出隊(duì)】【4-顯示隊(duì)頭數(shù)據(jù)】");System.out.print("\t【5-顯示隊(duì)所有數(shù)據(jù)】\n");System.out.print("\t【6-返回上一級(jí)菜單】\n");System.out.print("\n請(qǐng)選擇:");select=input.nextInt();switch(select){case1:if(seqqueue.isEmpty()){System.out.println("\t隊(duì)為空！");}else{System.out.println("\t隊(duì)中有數(shù)據(jù)！");}break;case2:System.out.print("\t輸入要進(jìn)隊(duì)的數(shù)據(jù)：");data=input.next();seqqueue.enQueue(data);System.out.print("\t進(jìn)隊(duì)數(shù)據(jù)為："+data+"\n");break