數(shù)據(jù)結(jié)構(gòu)單元3引例括號(hào)匹配的檢查括號(hào)匹配是指一個(gè)算術(shù)表達(dá)式中括號(hào)要成對(duì)并以正確的順序出現(xiàn)，才是合法的。假設(shè)表達(dá)式中包含兩種括號(hào)：[]和()，嵌套順序任意，則正確的嵌套模式為：([]())、[([])()]，錯(cuò)誤的嵌套模式為：([](])、(()[]。引例描述：括號(hào)匹配的檢查編譯系統(tǒng)對(duì)算術(shù)表達(dá)式進(jìn)行語(yǔ)法檢查時(shí)，若括號(hào)不匹配，系統(tǒng)則會(huì)給出語(yǔ)法錯(cuò)誤，不能通過(guò)編譯。思政小課堂：樹(shù)立正確的技能觀“遵守規(guī)則，樹(shù)立正確的技能觀”遵守規(guī)則，敬畏規(guī)則，堅(jiān)定自我，堅(jiān)守正確之路，是我們每個(gè)人都應(yīng)該做到的。同時(shí)我們要自強(qiáng)自信，學(xué)好專業(yè)技能，造福社會(huì)。引例分析與實(shí)現(xiàn)引例分析：編譯系統(tǒng)對(duì)算術(shù)表達(dá)式進(jìn)行語(yǔ)法檢查時(shí)，表達(dá)式中的左右括號(hào)不僅要個(gè)數(shù)相等，而且先左后右的順序要正確。括號(hào)可以嵌套使用，嵌套使用時(shí)，右括號(hào)與其前最近的一個(gè)左括號(hào)匹配。若括號(hào)不匹配，系統(tǒng)則會(huì)給出語(yǔ)法錯(cuò)誤，不能通過(guò)編譯。算法思路：讀取表達(dá)式字符串，依次對(duì)其中的字符ch進(jìn)行判斷若ch是右括號(hào)，則先判斷棧是否為空若棧為空，則表示此右括號(hào)是多余的若ch是左括號(hào)，則入棧若棧不空，則與棧頂左括號(hào)比較，判斷是否是同類括號(hào)若是同類括號(hào)，則表示這一對(duì)括號(hào)匹配成功，棧頂元素出棧若不是同類括號(hào)，則表示括號(hào)嵌套錯(cuò)誤表達(dá)式讀取結(jié)束時(shí)：棧為空，則表達(dá)式括號(hào)匹配成功棧不空，說(shuō)明左括號(hào)有多余的引例分析與實(shí)現(xiàn)1*2+3/5-3[(檢測(cè)到左中括號(hào)[，入棧檢測(cè)到右小括號(hào))，判斷棧不空，且括號(hào)匹配，則棧頂左小括號(hào)(出棧；檢測(cè)到右中括號(hào)]，判斷棧不空，且括號(hào)匹配，則棧頂左中括號(hào)[出棧檢測(cè)到左小括號(hào)(，入棧檢測(cè)到左小括號(hào)(，入棧；檢測(cè)到右小括號(hào))，判斷棧不空，且括號(hào)匹配，則棧頂左小括號(hào)(出棧。[(])()(表達(dá)式讀取結(jié)束，最后棧為空，表達(dá)式括號(hào)匹配數(shù)據(jù)結(jié)構(gòu)主講人：閭楓常州信息職業(yè)技術(shù)學(xué)院3.1棧棧（Stack）是一種操作受限的線性表，其插入和刪除操作只允許在線性表的一端進(jìn)行。引言IntroductionPart01棧的抽象數(shù)據(jù)類型棧的插入和刪除操作只允許在線性表的一端進(jìn)行。允許進(jìn)行操作的一端稱為棧頂（top），不允許操作的一端則稱為棧底（bottom）。棧的插入操作通常稱為入棧（push），棧的刪除操作則稱為出棧（pop）。如果棧中無(wú)數(shù)據(jù)元素，則稱為空棧。棧頂元素是最后入棧，最先出棧，棧底元素是最先入棧，最后出棧，棧具有后進(jìn)先出（LIFO，LastInFirstOut）的特征。棧（Stack）說(shuō)明棧的定義棧的定義棧操作限定的是元素插入和刪除的位置，元素插入和刪除操作進(jìn)行的時(shí)間并未限定。即出?？梢噪S時(shí)進(jìn)行，只要出棧的是棧頂元素即可。a有三個(gè)元素a，b，c依次進(jìn)棧并且每個(gè)元素只進(jìn)一次棧，則出棧的次序可以有：abc、acb、bac、bca、cba五種。示例若進(jìn)出棧操作為：a進(jìn)棧然后出棧，b、c進(jìn)棧，然后c出棧，b出棧，則最終的出棧次序?yàn)椋篴cbbcbb初始a進(jìn)棧a出棧c進(jìn)棧c出棧b出棧b進(jìn)棧雖然棧的操作受限降低了棧操作的靈活性，但也使棧的操作更有效和更容易實(shí)現(xiàn)。棧的基本操作主要有創(chuàng)建棧、入棧、出棧、取棧頂元素、判斷棧是否為空等。棧的抽象數(shù)據(jù)類型描述及定義Part02順序棧順序棧的存儲(chǔ)結(jié)構(gòu)棧作為一種特殊的線性表，可以采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。采用順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序棧（SequentialStack）。順序棧的存儲(chǔ)結(jié)構(gòu)棧滿設(shè)數(shù)組的長(zhǎng)度為length，當(dāng)top=length-1時(shí)，表示棧滿?？諚Ｖ杏幸粋€(gè)元素時(shí)，top值為0，因此一般用top=-1，表示?？諚５讛?shù)組下標(biāo)為0的一端表示棧底棧頂用變量top表示棧頂元素在數(shù)組中的位置，也把top稱為棧頂指針一維數(shù)組順序棧一維數(shù)組順序棧的基本操作定義順序棧類SeqStack實(shí)現(xiàn)順序棧接口Stack，類中實(shí)現(xiàn)接口中相應(yīng)操作方法，定義泛型數(shù)組stack用于存儲(chǔ)數(shù)據(jù)元素，定義變量length表示棧的初始容量，定義整型變量top表示棧頂指針，指向棧頂元素位置。構(gòu)造方法用來(lái)對(duì)棧進(jìn)行初始化，創(chuàng)建一維的泛型數(shù)組，并指定棧的容量大小，設(shè)置棧頂指針為-1，代表是一個(gè)空棧。//順序棧類public

classSeqStack<T>implementsStack<T>{

privateT[]stack=null;//聲明一維數(shù)組，表示順序棧

private

int

length;//表示順序棧的容量

private

int

top;//棧頂指針

//棧初始化

publicSeqStack(){

stack=(T[])newObject[16];//構(gòu)造一維的泛型數(shù)組，默認(rèn)大小為16

length=16;

top=-1;//棧初始化，棧中沒(méi)有元素 }

publicSeqStack(int

size){

stack=(T[])newObject[size];//構(gòu)造一維的泛型數(shù)組，大小由參數(shù)決定

length=size;

top=-1;//棧初始化，棧中沒(méi)有元素 }……}順序棧的基本操作出棧時(shí)，先取出棧頂元素，然后top減1。出棧操作入棧時(shí)，top加1，指向新的棧頂位置，新元素放置到棧頂入棧操作atop03120312初始?？?top=-1

元素a,b,c入棧0312元素c,b出棧abctoptopcb順序棧的基本操作元素入棧先判斷棧是否滿，若棧已滿，則拋出異常；若棧未滿，則先將棧頂指針加1，再將元素放入棧頂位置。元素出棧需要判斷棧是否空，若?？眨瑒t拋出異常；若棧不空，則先獲取頂元素，再將棧頂指針減1。//元素入棧@Overridepublic

voidpush(Tt){//判斷棧是否已滿，如果已滿，則拋出異常，如果未滿，則元素入棧

if(top==length-1){

throw

newRuntimeException("棧已經(jīng)滿，元素不能再進(jìn)棧");}else{

stack[++top]=t;//棧頂指針先加1，再將元素放入棧頂位置}}

//元素出棧@OverridepublicTpop(){//判斷棧是否為空，若為空，則拋出異常，若不空，則元素出棧

if(this.isEmpty()){

throw

newRuntimeException("棧為空，沒(méi)有元素出棧");}else{

//先將棧頂元素值獲取返回，并將棧頂指針減1

return

stack[top--];}}時(shí)間復(fù)雜度為O(1)順序棧的基本操作判棧空?？諛?biāo)志是棧頂指針top值為-1，判斷top值是否為-1即可。取棧頂元素判斷棧不空，則直接返回棧頂元素值，棧頂指針不移動(dòng)。//獲取棧頂元素@OverridepublicTpeek(){//判斷棧是否為空，若為空，則拋出異常，若不空，則返回棧頂元素 if(this.isEmpty()){

throw

newRuntimeException("棧為空"); }else{

return

stack[top];//直接將棧頂元素值返回 }}//判斷棧是否為空@Overridepublic

booleanisEmpty(){

//top為-1,代表?xiàng)Ｖ袥](méi)有元素，為空棧

return

top==-1;}棧中的元素是Integer類型,從棧頂?shù)綏５滓来问牵?、2、3、4，定義逆置方法，修改棧中元素的次序從棧頂?shù)綏５鬃優(yōu)?4、3、2、1。注意：只使用順序棧的基本操作方法。課堂實(shí)踐Part03鏈?zhǔn)綏ｆ準(zhǔn)綏５拇鎯?chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧稱為鏈?zhǔn)綏?，?jiǎn)稱為鏈棧（LinkedStack）鏈棧一般用不帶頭結(jié)點(diǎn)單鏈表實(shí)現(xiàn)，單鏈表頭部作為棧頂，頭指針即為棧頂指針topantopa2a1^……棧底棧頂鏈?zhǔn)綏５幕静僮鱬ublic

classLinkedNode<T>{

privateTdata;

private

LinkedNodenext;

//構(gòu)造方法

publicLinkedNode(){ }

publicLinkedNode(Tdata){

this.data=data;

this.next=null; } publicLinkedNode(Tdata,LinkedNode<T>next){

this.data=data;

this.next=next; }

//省略相應(yīng)屬性的setter和getter方法 …...}鏈棧的結(jié)點(diǎn)結(jié)構(gòu)鏈棧的結(jié)點(diǎn)同樣包含數(shù)據(jù)域和指向下一個(gè)結(jié)點(diǎn)的指針域next變量用于指向下一個(gè)結(jié)點(diǎn)data變量用于存放數(shù)據(jù)鏈?zhǔn)綏５幕静僮?/鏈棧類public

classLinkedStack<T>implementsStack<T>{

privateLinkedNode<T>top;//代表?xiàng)ｍ斨羔?/p>

//棧初始化

publicLinkedStack(){

top=null;//將棧頂指針top置空，構(gòu)造一個(gè)空鏈棧 }

//實(shí)現(xiàn)棧接口的相關(guān)方法

……鏈棧類結(jié)構(gòu)鏈棧類LinkedStack實(shí)現(xiàn)棧接口Stack，除了實(shí)現(xiàn)棧接口的相應(yīng)方法外，鏈棧中定義一個(gè)LinkedNode類型的棧頂指針top，指向棧頂元素。鏈?zhǔn)綏５幕静僮鞒跏兼湕Ｖ杏?個(gè)元素ctopba^新結(jié)點(diǎn)入棧(1)先創(chuàng)建新結(jié)點(diǎn)noded^node(2)將新結(jié)點(diǎn)node指向棧頂指針(3)再移動(dòng)棧頂指針指向新結(jié)點(diǎn)鏈?zhǔn)綏５幕静僮?/元素入棧@Overridepublic

voidpush(Tt){

//將新結(jié)點(diǎn)指向棧頂，再移動(dòng)棧頂指針指向新結(jié)點(diǎn)，新結(jié)點(diǎn)成為棧頂元素 LinkedNode<T>node=newLinkedNode<T>(t);//使用傳遞的進(jìn)棧數(shù)值，先構(gòu)造新結(jié)點(diǎn)

node.setNext(top);//設(shè)置新結(jié)點(diǎn)指向棧頂指針

top=node;//設(shè)置棧頂指針指向新結(jié)點(diǎn)}入棧操作實(shí)現(xiàn)鏈?zhǔn)綏５幕静僮鞒跏兼湕Ｖ杏?個(gè)元素ctopba^出棧(1)棧頂元素值先保存到變量topData(2)移動(dòng)棧頂指針指向其下一個(gè)結(jié)點(diǎn)先保存棧頂元素值(3)返回變量topData的值鏈?zhǔn)綏５幕静僮?/元素出棧@OverridepublicTpop(){

//判斷鏈棧是否為空，若為空，拋出異常，若不為空，則取棧頂元素的值并返回，修改棧頂指針指向下一個(gè)結(jié)點(diǎn)

if(this.isEmpty()){

throw

newRuntimeException("棧為空，沒(méi)有元素可出棧"); } TtopData=top.getData();//獲取棧頂元素值

top=top.getNext();//修改棧頂指針，指向下一個(gè)結(jié)點(diǎn)

return

topData;}出棧操作實(shí)現(xiàn)鏈?zhǔn)綏５幕静僮髋袛鄺？杖ｍ斣?/獲取棧頂元素@OverridepublicTpeek(){

//判斷鏈棧是否為空，若為空，拋出異常，若不為空，則取棧頂元素的值并返回

if(this.isEmpty()){

throw

newRuntimeException("棧為空，沒(méi)有元素可出棧"); }

return

top.getData();//返回棧頂元素的值}//判斷棧是否為空@Overridepublic

booleanisEmpty(){

if(top==null)return

true;

else

return

false;}時(shí)間復(fù)雜度為O(1)順序棧和鏈?zhǔn)綏５膶?duì)比順序棧鏈?zhǔn)綏２僮鞯臅r(shí)間復(fù)雜度為O(1)操作的時(shí)間復(fù)雜度為O(1)存在空間浪費(fèi)和棧滿問(wèn)題沒(méi)有棧滿問(wèn)題，但每個(gè)結(jié)點(diǎn)有數(shù)據(jù)域和引用域，增加內(nèi)存開(kāi)銷元素個(gè)數(shù)變化不大，可使用順序棧若個(gè)數(shù)變化較大，不可預(yù)料，可使用鏈棧編寫(xiě)代碼實(shí)現(xiàn)，將十進(jìn)制整數(shù)轉(zhuǎn)換為二進(jìn)制整數(shù)（使用除2倒取余法）課堂實(shí)踐Part04棧的應(yīng)用棧在計(jì)算機(jī)領(lǐng)域的應(yīng)用非常廣泛，如CPU的中斷處理、函數(shù)的嵌套調(diào)用或遞歸調(diào)用、圖的深度優(yōu)先遍歷、網(wǎng)頁(yè)瀏覽的后退操作、算術(shù)表達(dá)式的轉(zhuǎn)換和求值等實(shí)現(xiàn)中，都有棧的身影。棧的應(yīng)用棧的應(yīng)用函數(shù)嵌套調(diào)用函數(shù)的嵌套調(diào)用是在一個(gè)函數(shù)中調(diào)用另一個(gè)函數(shù)f1(){……f2();……}f2(){……f3();……}f3(){………………}main(){……f1();……}main調(diào)用f1f1調(diào)用f2f2調(diào)用f3f3函數(shù)此時(shí)4個(gè)函數(shù)都在執(zhí)行中，均占用系統(tǒng)資源。函數(shù)調(diào)用的系統(tǒng)棧mainf1f2f3后調(diào)用先返回設(shè)立函數(shù)調(diào)用的系統(tǒng)棧用于記錄函數(shù)調(diào)用位置及執(zhí)行環(huán)境等相關(guān)信息。函數(shù)被調(diào)用時(shí)，將被調(diào)用函數(shù)的相關(guān)信息入棧；函數(shù)執(zhí)行結(jié)束返回時(shí)，棧頂元素出棧，獲得調(diào)用函數(shù)的相關(guān)信息，返回到主調(diào)用函數(shù)繼續(xù)執(zhí)行。棧是系統(tǒng)實(shí)現(xiàn)函數(shù)嵌套調(diào)用的基礎(chǔ)。棧的應(yīng)用算術(shù)表達(dá)式求值

界限符（小括號(hào)等）運(yùn)算符（+，-，*……）操作數(shù)（1，2，3……）中綴表達(dá)式：(1+2*3)-4算術(shù)表達(dá)式四則運(yùn)算的規(guī)則有：先乘除、后加減同級(jí)運(yùn)算時(shí)先左后右先括號(hào)內(nèi)，后括號(hào)外等后綴表達(dá)式：

123*+4-后綴表達(dá)式是將運(yùn)算符放在操作數(shù)后面的寫(xiě)法，如1+2的后綴表達(dá)式為：12+后綴表達(dá)式中已考慮了運(yùn)算符的優(yōu)先級(jí)，沒(méi)有括號(hào)，只有操作數(shù)和運(yùn)算符，運(yùn)算時(shí)能按從左到右的順序進(jìn)行，便于系統(tǒng)實(shí)現(xiàn)。棧的應(yīng)用算術(shù)表達(dá)式求值

說(shuō)明：為簡(jiǎn)化表達(dá)式求值過(guò)程，這里只討論操作數(shù)是個(gè)位整型，且運(yùn)算符僅有+、-、*、/，界限符為小括號(hào)。Step01Step02將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式對(duì)后綴表達(dá)式求值棧的應(yīng)用算術(shù)表達(dá)式求值

Step01中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式若字符ch是操作數(shù)，則直接將ch添加到postfix中；

從左至右讀取中綴表達(dá)式字符串中的字符ch，判斷字符類型進(jìn)行不同的處理，字符串postfix表示后綴表達(dá)式若字符ch是運(yùn)算符，若棧為空，則直接進(jìn)棧，若棧不空，則先與棧頂元素比較優(yōu)先級(jí)，若ch優(yōu)先級(jí)高于棧頂元素，ch入棧，否則棧頂元素出棧，添加到postfix中，一直到發(fā)現(xiàn)優(yōu)先級(jí)更低的元素為止；若字符ch是左括號(hào)(，則直接入棧；若字符ch是右括號(hào))，則棧中的運(yùn)算符出棧，直到彈出一個(gè)左括號(hào)為止反復(fù)讀取判斷，直到中綴表達(dá)式字符串讀取結(jié)束，將棧中的運(yùn)算符全部出棧，添加到postfix中。中綴表達(dá)式棧后綴表達(dá)式postfix(1+2*3)-4123*+4-棧的應(yīng)用算術(shù)表達(dá)式求值

//表達(dá)式處理public

classExpression{//中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式public

staticStringinfixToPostfix(Stringinfix){

//棧初始化，存放運(yùn)算符SeqStack<String>stack=newSeqStack<String>(infix.length());StringBufferpostfix=newStringBuffer();//存放后綴表達(dá)式//循環(huán)讀取前綴表達(dá)式的字符for(int

i=0;i<infix.length();i++){

char

ch=infix.charAt(i);

switch(ch){

case

'(‘:

stack.push(ch+""); break;//若是左括號(hào)，直接入棧

case

')'://棧元素出棧 Stringstr=null;

while(!(str=stack.pop()).equals("(")){//棧項(xiàng)元素不為左括號(hào),則元素一直出棧添加到串中，直到遇到左括號(hào)

postfix.append(str); } break;

case

'+’:

case

'-’:

//先與棧頂元素比較優(yōu)先級(jí)，運(yùn)算符是+或-時(shí)，只有棧頂元素是（，才會(huì)直接進(jìn)棧，其他情況都是出棧

while(!stack.isEmpty()&&!stack.peek().equals("(")){

postfix.append(stack.pop()); }

stack.push(ch+"");//當(dāng)前運(yùn)算符入棧

break;

case

'*’:

case

'/’:

//先與棧頂元素比較優(yōu)先級(jí)，運(yùn)算符是*或/時(shí)，棧頂元素是（或+或-，才會(huì)直接進(jìn)棧，若是*或/，因是同級(jí)，則是出棧

while(!stack.isEmpty()&&(stack.peek().equals("*")||stack.peek().equals("/"))){

postfix.append(stack.pop()); }

stack.push(ch+"");//當(dāng)前運(yùn)算符入棧

break;

default://表示讀取的不是運(yùn)算符，是數(shù)值

postfix.append(ch); } }

//前綴表達(dá)式讀取結(jié)束，若棧不空，元素直接出棧，接到串中

while(!stack.isEmpty()){

postfix.append(stack.pop()); }

return

postfix.toString();}}【注意】在中綴表達(dá)式中，運(yùn)算符的優(yōu)先級(jí)括號(hào)最高，其次為*、/，最后是+、-，而一旦進(jìn)入運(yùn)算符棧中后，“(”優(yōu)先級(jí)變成最低。棧的應(yīng)用算術(shù)表達(dá)式求值

//計(jì)算后綴表達(dá)式的值public

static

floatcalculate(Stringpostfix){

//初始化棧 LinkedStack<Float>stack=newLinkedStack<Float>();

float

res=0;

//用棧存儲(chǔ)操作數(shù)值，讀取的若是操作數(shù)，則數(shù)值入棧，

//若是運(yùn)算符，則棧頂兩個(gè)元素連續(xù)出棧，使用該運(yùn)算符進(jìn)行計(jì)算，并將計(jì)算結(jié)果再入棧。依次操作，直到表達(dá)式讀取結(jié)束，最后棧頂元素即計(jì)算結(jié)果。

for(int

i=0;i<postfix.length();i++){

char

ch=postfix.charAt(i);//讀取字符

if(Character.isDigit(ch)){//若是數(shù)字

stack.push(Float.parseFloat(ch+""));//數(shù)字入棧 }else{

//棧頂兩個(gè)元素連續(xù)出棧

float

num1=stack.pop();

float

num2=stack.pop();

switch(ch){

case

'+':res=num2+num1; break;

case

'-':res=num2-num1; break;

case

'*':res=num2*num1; break;

case

'/':res=num2/num1; break; }

stack.push(res); } }

return

stack.pop();}}Step02后綴表達(dá)式求值棧的應(yīng)用算術(shù)表達(dá)式求值

讀取后綴表達(dá)式，用棧存儲(chǔ)操作數(shù)值1后綴表達(dá)式23*+4-=6=7=3讀取的若是操作數(shù)，則數(shù)值入棧若是運(yùn)算符，則棧頂兩個(gè)元素連續(xù)出棧，使用該運(yùn)算符進(jìn)行計(jì)算，并將計(jì)算結(jié)果再入棧。依次操作，直到表達(dá)式讀取結(jié)束，最后棧頂元素即計(jì)算結(jié)果。數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：閭楓常州信息職業(yè)技術(shù)學(xué)院3.2隊(duì)列隊(duì)列和棧一樣，也是操作受限的線性表?，F(xiàn)實(shí)生活中隊(duì)列隨處可見(jiàn)，如超市購(gòu)物排隊(duì)結(jié)賬、銀行排隊(duì)等待辦理業(yè)務(wù)、計(jì)算機(jī)操作系統(tǒng)的作業(yè)調(diào)度、打印機(jī)緩沖區(qū)等都是隊(duì)列應(yīng)用的體現(xiàn)。引言IntroductionPart01隊(duì)列的抽象數(shù)據(jù)類型隊(duì)列(Queue)是插入和刪除操作在線性表的兩端進(jìn)行，一端允許插入操作，而另一端只允許刪除操作，允許插入的一端稱為隊(duì)尾(Rear)，允許刪除的另一端則稱為隊(duì)頭(Front)。隊(duì)列的插入操作通常稱為入隊(duì)或進(jìn)隊(duì)，刪除操作通常稱為出隊(duì)。如果隊(duì)列中沒(méi)有元素，則稱為空隊(duì)列。隊(duì)列的插入操作在隊(duì)尾，刪除操作在隊(duì)頭，因此最先入隊(duì)也會(huì)最先出隊(duì)，最后進(jìn)隊(duì)的最后出隊(duì)，隊(duì)列具有先進(jìn)先出(FIFO，F(xiàn)irstInFirstOut)的特征。隊(duì)列（Queue）說(shuō)明隊(duì)列的定義a1a2a3……

an隊(duì)頭隊(duì)尾出隊(duì)進(jìn)隊(duì)隊(duì)列的插入和刪除操作在兩端進(jìn)行，使用隊(duì)頭指針(front)和隊(duì)尾指針(rear)表示隊(duì)列的操作的兩端。隊(duì)列的基本操作主要有創(chuàng)建隊(duì)列、入隊(duì)、出隊(duì)、取隊(duì)頭元素、判斷隊(duì)列是否為空等。設(shè)計(jì)隊(duì)列的抽象數(shù)據(jù)類型接口Queue，其中的操作數(shù)據(jù)元素用泛型描述。隊(duì)列的抽象數(shù)據(jù)類型//隊(duì)列抽象數(shù)據(jù)類型，其中T表示隊(duì)列中數(shù)據(jù)的類型public

interfaceQueue<T>{

public

voidenqueue(Tt);//元素入隊(duì),在隊(duì)尾插入元素T

publicTdequeue();//元素出隊(duì)，隊(duì)頭元素出隊(duì)

publicTpeek();//取隊(duì)頭元素值,但隊(duì)頭元素不出隊(duì)

public

booleanisEmpty();//判斷隊(duì)列是否為空}Part02順序隊(duì)列順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)隊(duì)列的順序存儲(chǔ)稱為順序隊(duì)列（SequentialQueue）。順序隊(duì)列用一個(gè)一維數(shù)組存放元素?cái)?shù)據(jù)，用兩個(gè)變量front和rear，分別表示隊(duì)頭和隊(duì)尾的位置。public

classSeqQueue<T>implementsQueue<T>{

privateT[]queue=null;//聲明一維數(shù)組，存儲(chǔ)隊(duì)列元素

private

int

length;//數(shù)組的大小，表示隊(duì)列的最大容量

private

int

front;//表示隊(duì)頭位置

private

int

rear;//表示隊(duì)尾位置 //實(shí)現(xiàn)隊(duì)列接口的相關(guān)方法 ……}順序隊(duì)列的基本操作初始隊(duì)列中有3個(gè)元素01234frontrear一個(gè)隊(duì)列初始有3個(gè)元素a、b、c，元素存儲(chǔ)在數(shù)組的前3個(gè)單元中。下標(biāo)為0的一端為隊(duì)頭，元素d進(jìn)隊(duì)時(shí)，只要隊(duì)列未滿，直接在隊(duì)尾增加即可；元素a出隊(duì)操作時(shí)，若要保證隊(duì)頭位置不空，剩下元素仍然在數(shù)組的前列，則需要所有剩下元素向前移動(dòng)一個(gè)位置dabc元素d進(jìn)隊(duì)元素a出隊(duì)時(shí)間復(fù)雜度為O(n)順序隊(duì)列的基本操作初始空隊(duì)列，長(zhǎng)度為501234元素a、b、c入隊(duì)

frontrear若不限定隊(duì)列的所有元素存儲(chǔ)在數(shù)組的前n個(gè)單元中，即隊(duì)頭不需要固定在下標(biāo)為0的位置，元素出隊(duì)時(shí)，移動(dòng)隊(duì)頭的位置，元素進(jìn)隊(duì)時(shí)，移動(dòng)隊(duì)尾的位置初始空隊(duì)列，隊(duì)頭front和隊(duì)尾rear值均為-1，并且front定位在隊(duì)頭元素的前一個(gè)位置，rear定位在隊(duì)尾元素位置約定abc元素a、b出隊(duì)順序隊(duì)列的基本操作cde01234frontrear隊(duì)列中已有3個(gè)元素，這時(shí)如果再有一個(gè)元素f想入隊(duì)，此時(shí)rear值為4，再做加1，值已經(jīng)超出數(shù)組下標(biāo)范圍，出現(xiàn)越界溢出。而此時(shí)隊(duì)列頭部元素a、b已出隊(duì)，隊(duì)列是有空閑的，這種現(xiàn)象稱為“假溢出”。解決假溢出最好的辦法是將隊(duì)列設(shè)計(jì)成頭尾相接的循環(huán)結(jié)構(gòu)。順序循環(huán)隊(duì)列順序循環(huán)隊(duì)列是將順序隊(duì)列設(shè)計(jì)成邏輯上頭尾相接的循環(huán)結(jié)構(gòu)cde01234frontrearfrontrear01234cde順序隊(duì)列順序循環(huán)隊(duì)列frear順序循環(huán)隊(duì)列出隊(duì)操作時(shí)改變front值，計(jì)算表達(dá)式為：front=(front+1)%lengthfrontrear01234cdefrear循環(huán)隊(duì)列入隊(duì)或出隊(duì)操作時(shí)，隊(duì)頭和隊(duì)尾位置移動(dòng)時(shí)，不能簡(jiǎn)單的執(zhí)行加1操作，可能會(huì)存在越界情況入隊(duì)操作時(shí)改變r(jià)ear值，計(jì)算表達(dá)式為：rear=(rear+1)%lengthrear=(4+1)%5可用取模運(yùn)算使值在0--length-1順序循環(huán)隊(duì)列約定隊(duì)列中預(yù)留一個(gè)空位，在隊(duì)頭位置和隊(duì)尾位置相差為1時(shí)，即認(rèn)為隊(duì)列已滿，此時(shí)隊(duì)滿條件為：front=(rear+1)%length，隊(duì)列中最多放length-1個(gè)元素。隊(duì)列中有元素c、d、e、ffrontrear01234cdef隊(duì)空和隊(duì)滿判斷元素g入隊(duì)rearg隊(duì)空隊(duì)滿隊(duì)空條件為：front=rear隊(duì)滿條件為：front=(rear+1)%length隊(duì)列中有元素c、d、efrontrear012dce43frontfrontfront元素c、d、e出隊(duì)隊(duì)列為空，隊(duì)頭和隊(duì)尾相等隊(duì)空和隊(duì)滿時(shí)，front和rear值均相等，那該如何判定隊(duì)空和隊(duì)滿呢？順序循環(huán)隊(duì)列隊(duì)列初始化為空f(shuō)rontrear01243定義順序循環(huán)隊(duì)列SeqCirQueue類實(shí)現(xiàn)隊(duì)列接口Queue，定義泛型數(shù)組queue用于存儲(chǔ)數(shù)據(jù)元素，定義變量length表示隊(duì)列長(zhǎng)度，定義整型變量front和rear分別表示隊(duì)頭和隊(duì)尾位置。public

classSeqCirQueue<T>implements

Queue<T>{

privateT[]queue=null;//聲明一維數(shù)組，存儲(chǔ)隊(duì)列元素

private

int

length;//數(shù)組的大小，表示隊(duì)列的最大容量

private

int

front;//表示隊(duì)頭位置

private

int

rear;//表示隊(duì)尾位置

//隊(duì)列初始化

publicSeqCirQueue(){

queue=(T[])newObject[16];//構(gòu)造一維的泛型數(shù)組，默認(rèn)大小為16，存儲(chǔ)隊(duì)列元素

length=16;

front=rear=0;//初始隊(duì)列為空 }

publicSeqCirQueue(int

length){

queue=(T[])newObject[length];//構(gòu)造一維的泛型數(shù)組，存儲(chǔ)隊(duì)列元素

this.length=length;

front=rear=0;//初始隊(duì)列為空 }……}順序循環(huán)隊(duì)列入隊(duì)操作元素a、b、c入隊(duì)rear01243front元素d入隊(duì)，隊(duì)滿rearrearrearrearfront=(rear+1)%length//元素入隊(duì)@Overridepublic

void

enqueue(Tt){//判斷隊(duì)列是否滿，若已滿，則拋出異常，若未滿，隊(duì)尾位置向前移動(dòng)1，插入元素

if(front==(rear+1)%length){

throw

newRuntimeException("隊(duì)列已滿，元素不能入隊(duì)"); }else{

rear=(rear+1)%length;

queue[rear]=t; }}abcd順序循環(huán)隊(duì)列出隊(duì)操作front=rearrear01243cdeffront元素c、d、e、f出隊(duì)frontfrontfrontfront//元素出隊(duì)@OverridepublicTdequeue(){//判斷隊(duì)列是否空，若為空，拋出異常，若不為空，隊(duì)頭位置向前移動(dòng)1，取出元素

if(isEmpty()){

throw

newRuntimeException("隊(duì)列空，沒(méi)有元素出隊(duì)"); }else{

front=(front+1)%length; Tt=queue[front];

queue[front]=null;

return

t; }}時(shí)間復(fù)雜度為O(1)順序循環(huán)隊(duì)列//取隊(duì)頭元素@OverridepublicTpeek(){//判斷隊(duì)列是否空，若為空，拋出異常，若不為空，直接取出隊(duì)頭元素

if(isEmpty()){

throw

newRuntimeException("隊(duì)列空，沒(méi)有元素獲取"); }else{

return

queue[front+1];//直接將隊(duì)頭元素取出 }}判隊(duì)空取隊(duì)頭元素//判斷隊(duì)列是否為空

@Override

public

boolean

isEmpty(){

//隊(duì)頭和隊(duì)尾指向同一個(gè)位置，表示隊(duì)列為空

return

front==rear; }獲取隊(duì)頭元素和出隊(duì)操作的區(qū)別在于，隊(duì)頭位置不移動(dòng)。Part03鏈?zhǔn)疥?duì)列在循環(huán)隊(duì)列中，若隊(duì)列已滿，再有元素入隊(duì)，就會(huì)出現(xiàn)“真溢出”現(xiàn)象，這時(shí)隊(duì)列可用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)。隊(duì)列的鏈?zhǔn)酱鎯?chǔ)稱為鏈?zhǔn)疥?duì)列，簡(jiǎn)稱鏈隊(duì)。鏈?zhǔn)疥?duì)列的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)疥?duì)列其實(shí)就是單鏈表，只是操作限制了隊(duì)尾插入元素，隊(duì)頭刪除元素。鏈隊(duì)使用帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)，需要設(shè)置隊(duì)頭(front)和隊(duì)尾(rear)兩個(gè)指針，分別指向鏈隊(duì)的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)。當(dāng)隊(duì)頭和隊(duì)尾指針都指向頭結(jié)點(diǎn)時(shí)，表示是一個(gè)空隊(duì)列。a1a2an^front……rearfront^rear鏈?zhǔn)疥?duì)列的基本操作//鏈?zhǔn)疥?duì)列類public

classLinkedQueue<T>implementsQueue<T>{

privateLinkedNode<T>front,rear;//表示隊(duì)頭,隊(duì)尾指針

//隊(duì)列初始化

publicLinkedQueue(){

front=rear=newLinkedNode<T>();//初始空隊(duì)列，隊(duì)頭和隊(duì)尾指向一個(gè)空的頭結(jié)點(diǎn) }

//實(shí)現(xiàn)隊(duì)列接口的相關(guān)方法

……}鏈隊(duì)類結(jié)構(gòu)鏈?zhǔn)疥?duì)列的基本操作入隊(duì)操作nodefrontreararear（1）創(chuàng)建新結(jié)點(diǎn)node初始空隊(duì)列時(shí)，隊(duì)頭front和隊(duì)尾rear都指向頭結(jié)點(diǎn)。（2）結(jié)點(diǎn)node入隊(duì)nodeb^^^時(shí)間復(fù)雜度為O(1)（3）移動(dòng)隊(duì)尾指針鏈?zhǔn)疥?duì)列的基本操作入隊(duì)操作實(shí)現(xiàn)//元素入隊(duì)@Overridepublic

voidenqueue(Tt){

//先構(gòu)造新結(jié)點(diǎn)，在隊(duì)尾處插入新結(jié)點(diǎn)，再移動(dòng)隊(duì)尾指針指向新結(jié)點(diǎn) LinkedNode<T>node=newLinkedNode<T>(t,null);

rear.setNext(node);//新結(jié)點(diǎn)插入隊(duì)尾

rear=node;//移動(dòng)隊(duì)尾指針}鏈?zhǔn)疥?duì)列的基本操作出隊(duì)操作元素出隊(duì)，就是頭結(jié)點(diǎn)的后繼結(jié)點(diǎn)(如為結(jié)點(diǎn)node)出隊(duì)nodefrontarearb^（1）node指向出隊(duì)的元素結(jié)點(diǎn)（2）頭結(jié)點(diǎn)的后繼結(jié)點(diǎn)改為node的后繼結(jié)點(diǎn)只有一個(gè)元素時(shí)，該元素出隊(duì)只需要將隊(duì)尾指針rear指向頭結(jié)點(diǎn)^node時(shí)間復(fù)雜度為O(1)鏈?zhǔn)疥?duì)列的基本操作出隊(duì)操作實(shí)現(xiàn)//元素出隊(duì)@OverridepublicTdequeue(){

//先獲取隊(duì)頭元素，再移動(dòng)隊(duì)頭指針指向下一個(gè)結(jié)點(diǎn)，若隊(duì)列只有一個(gè)元素，出隊(duì)后隊(duì)列為空，則移動(dòng)隊(duì)尾指針指向頭結(jié)點(diǎn)

if(isEmpty())

throw

newRuntimeException("隊(duì)列為空，沒(méi)有元素可出隊(duì)"); LinkedNode<T>node=front.getNext();//保存要出隊(duì)的隊(duì)頭結(jié)點(diǎn)

front.setNext(node.getNext());//隊(duì)頭指針指向node的后繼結(jié)點(diǎn)

if(node.getNext()==null)//若隊(duì)列中只有一個(gè)元素

rear=front;//元素出隊(duì)后，隊(duì)列為空，隊(duì)尾和隊(duì)頭指針都指向頭結(jié)點(diǎn)

return

node.getData();}鏈?zhǔn)疥?duì)列的基本操作判斷隊(duì)空取隊(duì)頭元素//取隊(duì)頭元素@OverridepublicTpeek(){//判斷隊(duì)列是否為空，若為空，則拋出異常，若不為空，則獲取隊(duì)頭元素

if(isEmpty()){

throw

newRuntimeException("隊(duì)列為空"); }else{

return

front.getNext().getData();//取隊(duì)頭元素值返回 }}//判斷鏈隊(duì)是否為空@Overridepublic

booleanisEmpty(){

if(front==rear)

return

true; else

return

false;}順序循環(huán)隊(duì)列和鏈?zhǔn)疥?duì)列的對(duì)比順序循環(huán)隊(duì)列鏈?zhǔn)疥?duì)列操作的時(shí)間復(fù)雜度為O(1)操作的時(shí)間復(fù)雜度為O(1)存在空間浪費(fèi)和溢出問(wèn)題結(jié)點(diǎn)有數(shù)據(jù)域和引用域，增加引用域的存儲(chǔ)開(kāi)銷元素個(gè)數(shù)變化不大且不會(huì)溢出，使用循環(huán)隊(duì)列若個(gè)數(shù)變化較大，可使用鏈?zhǔn)疥?duì)列編寫(xiě)代碼實(shí)現(xiàn)，將十進(jìn)制小數(shù)轉(zhuǎn)換為二進(jìn)制小數(shù)（使用乘2取整法）課堂實(shí)踐Part04隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用隊(duì)列求解約瑟夫環(huán)問(wèn)題算法分析：用隊(duì)列存放n個(gè)人，從第一個(gè)人開(kāi)始報(bào)數(shù)，判斷若是m，則直接出隊(duì)，若不是m，則出隊(duì)后重新入隊(duì)，即排到隊(duì)尾，依次判斷，直到隊(duì)列為空。問(wèn)題描述：n個(gè)人圍成一圈，從第一個(gè)人開(kāi)始報(bào)數(shù)，報(bào)到m的人出列，再由下一個(gè)人重新從1開(kāi)始報(bào)數(shù)，報(bào)到m的人再出列，依次類推，直到剩下最后一個(gè)人，輸出每次出列的人的編號(hào)。frontrear01234bcda有4個(gè)人為a、b、c、d，進(jìn)入順序循環(huán)隊(duì)列從a開(kāi)始，報(bào)到3的人出隊(duì)，若報(bào)數(shù)不是3，則排到隊(duì)尾a報(bào)數(shù)1，出隊(duì)，不是3，則a再入隊(duì)rearb報(bào)數(shù)2，出隊(duì)，不是3，則b再入隊(duì)frontrearc報(bào)數(shù)3，直接出隊(duì)frontreard報(bào)數(shù)1，出隊(duì)，不是3，則d再入隊(duì)隊(duì)列的應(yīng)用隊(duì)列求解約瑟夫環(huán)問(wèn)題//約瑟夫環(huán)問(wèn)題public

classJosephusRing{//n表示人數(shù)，m是所報(bào)的數(shù)public

voidoutQueue(int

n,int

m){//創(chuàng)建隊(duì)列存放人LinkedQueue<Integer>rings=newLinkedQueue<Integer>();//n個(gè)人按順序入隊(duì)for(int

i=1;i<=n;i++){

rings.enqueue(i);}int

count=0;//統(tǒng)計(jì)報(bào)數(shù)while(!rings.isEmpty()){//只要隊(duì)列不空，一直報(bào)數(shù) Integerdeq=rings.dequeue();//元素出隊(duì)

count++;

if(count%m==0){//如果正好報(bào)數(shù)的是m，則輸出，否則再次入隊(duì) System.out.print(deq+"");//輸出

count=0; }else{

rings.enqueue(deq);//元素再次入隊(duì)，到隊(duì)尾 }}}}public

classTestJR{

public

static

voidmain(String[]args){

//10個(gè)人圍成一圈，報(bào)到3的人出隊(duì) System.out.println("出隊(duì)順序?yàn)椋?);

newJosephusRing().outQueue(10,3); }}隊(duì)列的應(yīng)用舞伴配對(duì)問(wèn)題問(wèn)題描述：在舞會(huì)上男女各自排成一隊(duì)，每曲開(kāi)始時(shí)，依次從男隊(duì)和女隊(duì)各出一人配成舞伴，本曲沒(méi)成功配對(duì)者，坐著等待下一曲找舞伴，舞曲結(jié)束，雙方可以再次進(jìn)隊(duì)，等待新的配對(duì)。兩隊(duì)初始人數(shù)可以不等，較長(zhǎng)的那一隊(duì)中未配對(duì)者等待下一輪舞曲。算法分析：根據(jù)性別分別創(chuàng)建兩個(gè)隊(duì)列Q1(女生)和Q2(男生)，舞會(huì)開(kāi)始時(shí)，Q1和Q2的隊(duì)頭元素同時(shí)出隊(duì)，進(jìn)行配對(duì)。配對(duì)結(jié)束，再次進(jìn)到隊(duì)尾，等待再次輪換。F1F2F3rearfrontfrontrear女生隊(duì)列初始化，設(shè)有三人男生隊(duì)列初始化，設(shè)有五人開(kāi)始配對(duì)配對(duì)結(jié)束，再次進(jìn)隊(duì)^M3M4M5M1M2^隊(duì)列的應(yīng)用舞伴配對(duì)問(wèn)題M1//舞會(huì)配對(duì)public

classDancingPartner{//同時(shí)讀取Q1和Q2的內(nèi)容，進(jìn)行配對(duì)，n表示配對(duì)的輪次，每次配對(duì)結(jié)束就回到隊(duì)尾，等待再次輪換

public

voidmatch(LinkedQueue<Dancer>Q1,LinkedQueue<Dancer>Q2,int

n){

int

count=0;

//同時(shí)讀取Q1和Q2的內(nèi)容，進(jìn)行配對(duì)

while(!Q1.isEmpty()&&!Q2.isEmpty()){

//元素分別出隊(duì) Dancerfemale=Q1.dequeue(); Dancermale=Q2.dequeue();

//輸出信息 System.out.println(female+"----"+male);

//元素再次入到隊(duì)尾

Q1.enqueue(female);

Q2.enqueue(male);

count++;

if(count==n)break; } }}//測(cè)試舞會(huì)配對(duì)public

classTestDancingPartner{

public

static

voidmain(String[]args){

//創(chuàng)建兩個(gè)隊(duì)列，用于保存女生和男生信息 LinkedQueue<Dancer>Q1=newLinkedQueue<Dancer>(); LinkedQueue<Dancer>Q2=newLinkedQueue<Dancer>();

//隊(duì)列進(jìn)行初始化

for(int

i=1;i<=3;i++){ Dancerdancer=newDancer("lady"+i,"female");

Q1.enqueue(dancer); }

for(int

i=1;i<=5;i++){ Dancerdancer=newDancer("gentlment"+i,"male");

Q2.enqueue(dancer); }

//5首舞曲

newDancingPartner().match(Q1,Q2,5); }}lady1----gentlment1lady2----gentlment2lady3----gentlment3lady1----gentlment4lady2----gentlment5Part05優(yōu)先隊(duì)列實(shí)際情況中，有些按“先來(lái)先服務(wù)”原則不能滿足需求，還需要將任務(wù)的重要或緊急程度作為排隊(duì)處理的依據(jù)。如一般醫(yī)院急診室，會(huì)以最嚴(yán)重的患者優(yōu)先診治，計(jì)算機(jī)CPU的進(jìn)程調(diào)度管理，優(yōu)先級(jí)高的進(jìn)程先執(zhí)行。優(yōu)先隊(duì)列優(yōu)先隊(duì)列(PriorityQueue)作為一種特殊的隊(duì)列，不必遵守隊(duì)列先進(jìn)先出的特性，而根據(jù)元素的優(yōu)先級(jí)決定元素出隊(duì)操作。優(yōu)先隊(duì)列需要保證：每次出隊(duì)總是隊(duì)列中優(yōu)先級(jí)最高的元素優(yōu)先級(jí)的含義：由具體應(yīng)用定義，存入隊(duì)列中的元素附有表示優(yōu)先級(jí)的數(shù)值，標(biāo)識(shí)這個(gè)元素的優(yōu)先程度任務(wù)名P1P2P3P4優(yōu)先級(jí)4628設(shè)定優(yōu)先級(jí)數(shù)值越小優(yōu)先級(jí)越高，數(shù)值越大優(yōu)先級(jí)越低出隊(duì)順序?yàn)椋篜3、P1、P2、P4優(yōu)先隊(duì)列此時(shí)入隊(duì)效率較高，而出隊(duì)效率較低，且出隊(duì)不一定在隊(duì)頭。入隊(duì)時(shí)，保證隊(duì)列中的數(shù)據(jù)按優(yōu)先級(jí)從大到小排列，則任何時(shí)候隊(duì)頭出隊(duì)的都是優(yōu)先級(jí)最高的元素。入隊(duì)時(shí)，采用直接在隊(duì)尾入隊(duì)，不考慮元素優(yōu)先級(jí)，而在出隊(duì)時(shí)進(jìn)行檢索，找到優(yōu)先級(jí)最高的元素出隊(duì)?；静僮髋袛嗍欠駷榭?、入隊(duì)、出隊(duì)、取隊(duì)頭元素等入隊(duì)操作為保證優(yōu)先級(jí)的有序，效率可能較低，但出隊(duì)比較方便。時(shí)間復(fù)雜度為O(n)優(yōu)先隊(duì)列入隊(duì)時(shí)保證元素始終按優(yōu)先級(jí)數(shù)據(jù)遞增排列，保證每次出隊(duì)的是優(yōu)先級(jí)最高的元素，采用有序單鏈表存儲(chǔ)數(shù)據(jù)。優(yōu)先隊(duì)列實(shí)現(xiàn)

//取隊(duì)頭元素

@Override

publicTpeek(){

//取隊(duì)列中的第一個(gè)元素，并不出隊(duì)

return

priorityQueue.get(0); }

@Override

public

booleanisEmpty(){

//判斷鏈表是否為空

return

priorityQueue.isEmpty(); }

publicStringtoString(){

Node

p=priorityQueue.head.next; StringBufferdatas=newStringBuffer();

while(p!=null){

datas.append(p.data+"");//輸出結(jié)點(diǎn)的數(shù)據(jù)域

p=p.next;//指針后移一個(gè)結(jié)點(diǎn) }

return

datas.toString(); }}//優(yōu)先隊(duì)列public

classMyPriorityQueue<TextendsComparable<T>>implementsQueue<T>{

privateSortedSinglyList<T>priorityQueue;//使用有序單鏈表表示優(yōu)先隊(duì)列，插入隊(duì)列的元素以遞增排列

//隊(duì)列初始化

publicMyPriorityQueue(){

priorityQueue=newSortedSinglyList(); }

//元素入隊(duì)

@Override

public

voidenqueue(Tt){

//根據(jù)參數(shù)值大小，將元素插入到指定位置，此時(shí)不是單純的在隊(duì)尾入隊(duì)

priorityQueue.insert(t); }

//元素出隊(duì)

@Override

publicTdequeue(){

//返回隊(duì)頭元素，并從隊(duì)列中移除

return

priorityQueue.remove(0); }優(yōu)先隊(duì)列優(yōu)先隊(duì)列實(shí)現(xiàn)public

classMyProcessimplementsComparable<MyProcess>{

privateStringpname;//進(jìn)程名字

private

int

priority;//進(jìn)程優(yōu)先級(jí)

publicMyProcess(Stringpname){

this(pname,5); }

//使用名字和優(yōu)先級(jí)構(gòu)造進(jìn)程，若優(yōu)先級(jí)不在1-10之間，則拋出異常

publicMyProcess(Stringpname,int

priority){

this.pname=pname;

if(priority<1||priority>10){

throw

newRuntimeException("優(yōu)先級(jí)超范圍了"); }else{

this.priority=priority; } }

@Override

public

intcompareTo(MyProcesso){

return

this.priority-o.priority;//根據(jù)優(yōu)先級(jí)比較大小 }

publicStringtoString(){

return

"("+this.pname+","+this.priority+")"; }}定義任務(wù)類MyProcess，表示系統(tǒng)進(jìn)程，MyProcess要實(shí)現(xiàn)Comparable接口，根據(jù)優(yōu)先級(jí)數(shù)值比較大小，以保證其順序。優(yōu)先隊(duì)列優(yōu)先隊(duì)列實(shí)現(xiàn)public

classMockProcess{

public

static

voidmain(String[]args){

//假設(shè)有4個(gè)任務(wù)P1、P2、P3、P4，優(yōu)先級(jí)值分別為4、6、2、8 MyProcessp1=newMyProcess("P1",4); MyProcessp2=newMyProcess("P2",6); MyProcessp3=newMyProcess("P3",2); MyProcessp4=newMyProcess("P4",8);

//元素進(jìn)隊(duì)，根據(jù)優(yōu)先級(jí)遞增進(jìn)隊(duì) MyPriorityQueue<MyProcess>pqueue=newMyPriorityQueue<MyProcess>();

pqueue.enqueue(p1);

pqueue.enqueue(p2);

pqueue.enqueue(p3);

pqueue.enqueue(p4);

//隊(duì)列中元素 System.out.println("隊(duì)列中元素為："+pqueue);

//元素出隊(duì)，隊(duì)頭元素為(p3,2)，優(yōu)先級(jí)最高，直接出隊(duì) System.out.println(pqueue.dequeue()); }}任務(wù)名P1P2P3P4優(yōu)先級(jí)4628優(yōu)先隊(duì)列和普通隊(duì)列的主要區(qū)別在于優(yōu)先隊(duì)列始終是優(yōu)先級(jí)最高的先出隊(duì)數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)3.3遞歸遞歸在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中是一種非常有效的問(wèn)題求解方法，遞歸(recursion)是指在定義自身的同時(shí)又出現(xiàn)了對(duì)自身的直接或間接引用。引言IntroductionPart01遞歸的概念遞歸的基本思想是把規(guī)模大的復(fù)雜問(wèn)題轉(zhuǎn)化為相似的規(guī)模小的子問(wèn)題來(lái)解決。斐波那契數(shù)列的對(duì)于原問(wèn)題F(n)的求解可以轉(zhuǎn)為對(duì)F(n-1)、F(n-2)兩個(gè)子問(wèn)題的求解，F(xiàn)(n-1)的求解又可分解為F(n-2)、F(n-3)兩個(gè)子問(wèn)題的求解，依次遞推下去，一直到F(2)、F(1)的求解，而F(2)、F(1)數(shù)值是確定的，因此F(n)值得解。遞歸思想說(shuō)明遞歸的概念

斐波那契(Fibonacci)數(shù)列{1、1、2、3、5、8、13、21、34、……}遞歸的求解遞歸的概念先將原問(wèn)題分解為規(guī)模較小的子問(wèn)題，分解后的子問(wèn)題與原問(wèn)題類型相同，求解方法一樣再將子問(wèn)題繼續(xù)分解，反復(fù)進(jìn)行到不能再劃分或已經(jīng)可以求解為止最小子問(wèn)題解決，則它的上一層子問(wèn)題得解，依次回溯最后獲得原問(wèn)題的解F(n)F(n-2)F(n-2)F(n-3)F(n-1)F(n-3)F(n-4)……F(n-3)F(n-4)……F(1)F(2)F(1)F(2)遞歸的求解遞歸的概念遞歸求解過(guò)程包括兩個(gè)必要條件：遞推和回歸。5!5*4!

4*3!

3*2!

2*1!

1*0!

遞推回歸=1=2=6=24=120

遞歸邊界：0!=1遞推過(guò)程分析得到的規(guī)律即遞推公式，回歸點(diǎn)即遞歸邊界，是遞歸終止條件，到達(dá)后則回歸。n！=n*(n-1)!(n>=1)=120

Part02遞歸算法遞歸函數(shù)必須有遞歸邊界，函數(shù)的無(wú)限遞歸會(huì)導(dǎo)致程序崩潰。遞歸算法和遞歸函數(shù)遞歸算法遞歸算法是遞歸思維在程序中的體現(xiàn)，遞歸函數(shù)是指在函數(shù)的定義中直接或間接調(diào)用自身的函數(shù)。遞歸函數(shù)執(zhí)行時(shí)會(huì)反復(fù)判斷邊界條件，條件不滿足時(shí)，遞歸前進(jìn)，當(dāng)邊界條件滿足時(shí)，遞歸返回。遞歸算法和遞歸函數(shù)遞歸算法（1）問(wèn)題能否分解成多個(gè)同類子問(wèn)題，并且解決方法相同；（2）問(wèn)題的分解是否有終止條件。寫(xiě)遞歸關(guān)鍵的兩點(diǎn)就是找出遞推公式和明確遞歸邊界sum(n)=1+2+3+……+(n-1)+nsum(n-1)sum(n-1)=1+2+3+……+(n-2)+(n-1)sum(n-2)推導(dǎo)得到遞推公式為：sum(n)=sum(n-1)+n遞歸邊界為：n=1時(shí)，sum(1)值為1//遞歸求和的方法public

static

intsum(int

n){

if(n==1)return1;//遞歸邊界

else

return

n+sum(n-1);//遞推公式}遞歸求解Fibonacci遞歸算法（1）斐波那契數(shù)列的遞推公式為：F(n)=F(n-1)+F(n-2)(n>2)（2）遞歸邊界為:F(1)=F(2)=1(n=1,2)//遞歸求解Fibonacci數(shù)列的第n項(xiàng)public

static

intfib(int

n){

if(n<=0)

throw

newRuntimeException("無(wú)效參數(shù)");

if(n==1||n==2)return1;//遞歸邊界，n為1或2,函數(shù)值為1，直接返回

return

fib(n-1)+fib(n-2);//遞推公式，n不是邊界值，遞歸調(diào)用}fib(6)fib(5)fib(4)fib(3)fib(3)fib(2)fib(2)fib(1)fib(2)fib(1)fib(4)fib(3)fib(2)fib(2)fib(1)111211111223538遞歸求解Fibonacci遞歸算法數(shù)列求解過(guò)程中，存在重復(fù)遞歸計(jì)算問(wèn)題，若計(jì)算第n項(xiàng)，n值越大，重復(fù)計(jì)算越多。重復(fù)計(jì)算會(huì)導(dǎo)致程序的時(shí)間復(fù)雜度提高，導(dǎo)致程序效率低下。將計(jì)算過(guò)的數(shù)值先保存到集合容器中，每次遞歸計(jì)算前檢查容器中是否有該數(shù)據(jù)，若有，則直接拿來(lái)使用，若沒(méi)有，則計(jì)算并保存到容器中。//改進(jìn)的Fibonacci數(shù)列的第n項(xiàng)，避免重復(fù)計(jì)算public

static

intfib(int

n){

if(n<=0)

throw

newRuntimeException("無(wú)效參數(shù)");

if(n==1||n==2)return1;//遞歸邊界，n為1或2,函數(shù)值為1，直接返回

//用一個(gè)map存放已經(jīng)計(jì)算出來(lái)的數(shù)值，判斷fib(n)是否已經(jīng)計(jì)算過(guò)，若是，則直接從map中取值返回

if(map.containsKey(n)){

return

map.get(n); }

//若fib(n)沒(méi)有計(jì)算過(guò)，map中沒(méi)有包含其值，則用遞推公式進(jìn)行計(jì)算

int

num=fib(n-1)+fib(n-2);

//計(jì)算得到的fib(n)數(shù)據(jù)存放到map中

map.put(n,num);

return

num;}遞歸算法函數(shù)調(diào)用執(zhí)行是不斷壓棧和出棧過(guò)程，遞歸函數(shù)調(diào)用時(shí)在函數(shù)里調(diào)用自身，且當(dāng)前函數(shù)并未結(jié)束，層層遞歸進(jìn)去，直到遞歸邊界。系統(tǒng)棧的大小是有限的，遞歸深度太深，不斷壓?？赡軙?huì)導(dǎo)致棧滿溢出，以致程序崩潰。階乘算法中，為避免棧溢出可以設(shè)置一個(gè)遞歸深度值，若超過(guò)預(yù)設(shè)的遞歸深度值，則結(jié)束程序，不再遞歸下去。假如有n個(gè)臺(tái)階，每次可以跨一個(gè)或者兩個(gè)臺(tái)階，若要找出走n個(gè)臺(tái)階有多少種走法，請(qǐng)用遞歸求解，分析找出遞推公式和遞歸邊界。思考CerebratePart03遞歸算法應(yīng)用遞歸算法的關(guān)鍵就是找到如何將大問(wèn)題分解為小問(wèn)題的規(guī)律，基于規(guī)律寫(xiě)出遞推公式，然后再推敲遞歸邊界，最后將遞推公式和遞歸邊界翻譯成代碼。遞歸算法應(yīng)用單鏈表的遞歸創(chuàng)建算法實(shí)現(xiàn)：函數(shù)的參數(shù)為結(jié)點(diǎn)個(gè)數(shù)，同時(shí)用于設(shè)置結(jié)點(diǎn)的數(shù)據(jù)域的值，返回值為頭結(jié)點(diǎn)。//遞歸創(chuàng)建鏈表，n表示結(jié)點(diǎn)個(gè)數(shù)publicLinkedNode<T>create(int

n){

if(n<=0){

return

null; }

//構(gòu)造一個(gè)新結(jié)點(diǎn) LinkedNode<T>node=newLinkedNode(n,null);

//node的next指向下一個(gè)結(jié)點(diǎn)，下一個(gè)結(jié)點(diǎn)用遞歸構(gòu)造

node.setNext(create(n-1));

return

node;}遞歸算法應(yīng)用單鏈表的遞歸創(chuàng)建以遞歸思想來(lái)看單鏈表，每個(gè)結(jié)點(diǎn)的next指向以其后繼結(jié)點(diǎn)開(kāi)始的一個(gè)子鏈表，最后一個(gè)結(jié)點(diǎn)的next指向NULL算法分析：?jiǎn)捂湵淼慕Y(jié)點(diǎn)數(shù)量由用戶指定，假設(shè)有n個(gè)結(jié)點(diǎn)的單鏈表。創(chuàng)建一個(gè)結(jié)點(diǎn)作為頭結(jié)點(diǎn)并設(shè)置數(shù)據(jù)，其后的n-1個(gè)結(jié)點(diǎn)是子鏈表，第一個(gè)結(jié)點(diǎn)的next指向子鏈表的頭結(jié)點(diǎn)，返回第一個(gè)結(jié)點(diǎn)的地址。nhead頭結(jié)點(diǎn)包含n-1個(gè)結(jié)點(diǎn)的子鏈表對(duì)子鏈表使用遞歸方式繼續(xù)創(chuàng)建。遞歸邊界為n=0，即空鏈表的情況，若n為非法值，也設(shè)為空鏈表。。nhead包含n-2個(gè)結(jié)點(diǎn)的子鏈表n-1nheadn-11……NULL遞歸算法應(yīng)用單鏈表的遍歷算法分析：先獲取頭結(jié)點(diǎn)的數(shù)據(jù)域，存放到字符串中，其后剩下的結(jié)點(diǎn)作為一個(gè)子鏈表，再遞歸遍歷即可。遞歸結(jié)束條件是遍歷完最后一個(gè)結(jié)點(diǎn)后，鏈表為空的情況。//遞歸輸出單鏈表的結(jié)點(diǎn)publicStringprintNode(LinkedNode<T>p){

//遞歸邊界，若是空鏈表，輸出空串

if(p==null)return

"";

//取結(jié)點(diǎn)的數(shù)據(jù)域 Stringstr=p.getData().toString();

//若不