數(shù)據(jù)結構（Java語言實現(xiàn)） 課件 陳銳 第3、4章 棧和隊列；串、數(shù)組和廣義表

第3章棧和隊列結構Java實據(jù)現(xiàn)數(shù)目錄CONTENTS3.1

棧的表示與實現(xiàn)3.2棧的應用3.3棧與遞歸3.6小結3.4隊列的表示與實現(xiàn)3.5隊列的應用案例3.1：數(shù)制轉換案例3.2：括號匹配的檢驗案例3.3：表達式求值案例3.4：舞伴問題為什么要學習棧和隊列？案例3.5：回文判斷案例3.6：楊輝三角3.1棧的表示與實現(xiàn)3.1.1棧的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作。棧（Stack），也稱為堆棧，它是一種特殊的線性表，只允許在表的一端進行插入和刪除操作。允許在表操作的一端稱為棧頂（Top），另一端稱為棧底（Bottom）。棧頂是動態(tài)變化的，它由一個稱為棧頂指針（top）的變量指示。當表中沒有元素時，稱為空棧。棧的插入操作稱為入?；蜻M棧，刪除操作稱為出棧或退棧。3.1棧的表示與實現(xiàn)例1.圖3.2演示了元素A、B、C、D和E依次進棧和出棧的過程。如果一個進棧的序列由A、B、C組成，它的出棧序列有ABC、ACB、BAC、BCA和CBA五種可能，只有CAB是不可能的輸出序列。因為A、B、C進棧后，C出棧，接著就是B要出棧，C不可能A在B之前出棧，所以CAB是不可能出現(xiàn)的序列。Ａ．i

Ｂ．n-iＣ．n-i+1Ｄ．不確定例2.若一個棧的入棧序列是1，2，3，…，n，其輸出序列為a1，a2，a3，…，an，若a1=n，則ai為Ｃ3.1棧的表示與實現(xiàn)例3.3若一個棧的輸入序列為P1、P2、P3、…、Pn，輸出序列為1、2、3、…、n，如果P3=1，則P1的值（）?？赡苁? B.一定是2 C.不可能是2 D.不可能是33.1棧的表示與實現(xiàn)3.1棧的表示與實現(xiàn)學習基礎學習認知能力ADTStack{

數(shù)據(jù)對象：D={ai|ai∈ElemSet，i=1，2，…，n，n≥0}

數(shù)據(jù)關系：R={<ai-1,ai>|ai-1，ai∈D，i=2，3，…，n}

約定a1端為棧底，an端為棧頂。基本操作：（1）InitStack(&S)

初始條件：棧S不存在。操作結果：建立一個空棧S。（2）StackEmpty(S)

初始條件：棧S已存在。操作結果：若棧S為空，返回1，否則返回0。3.1.2棧的抽象數(shù)據(jù)類型3.1棧的表示與實現(xiàn)學習基礎學習認知能力（3）GetTop(S,&e)

初始條件：棧S存在且非空。操作結果：返回棧S的棧頂元素給e。（4）PushStack(&S,x)

初始條件：棧S已存在。操作結果：將元素x插入到棧S中，使其成為新的棧頂元素。（5）PopStack(&S,&e)

初始條件：棧S存在且非空。操作結果：刪除棧S的棧頂元素，并用e返回其值。（6）StackLength(S)

初始條件：棧S已存在。操作結果：返回棧S的元素個數(shù)。（7）ClearStack(S)

初始條件：棧S已存在。操作結果：將棧S清為空棧。}ADTStack3.1棧的表示與實現(xiàn)學習基礎學習認知能力3.1.3順序棧1.棧的順序存儲結構采用順序存儲結構的棧稱為順序棧。順序棧利用一組連續(xù)的存儲單元存放棧中的元素，存放順序依次從棧底到棧頂。publicclassSeqStack{inttop;finalintMAXSIZE=50;charstack[];}其中，stack[]用于存儲棧中的數(shù)據(jù)元素，top為棧頂指針，MAXSIZE為棧的最大容量。3.1棧的表示與實現(xiàn)學習基礎學習認知能力將元素a、b、c、d、e、f、g、h依次進棧，棧底元素為a，棧頂元素為h。約定棧頂指針top指向棧頂元素的下一個位置（而不是棧頂元素）。（1）初始時，棧為空，棧頂指針為0，即S.top=0。（2）?？諚l件為S.top==0，棧滿條件為S.top==MAXSIZE-1。（3）進棧操作時，先將元素壓入棧中，即S.stack[S.top]=e，然后使棧頂指針加1，即S.top+=1。出棧操作時，先使棧頂指針減1，即S.top-=1，然后元素出棧，即e=S.stack[S.top]。（4）棧的長度即棧中元素的個數(shù)為S.top。3.1棧的表示與實現(xiàn)學習基礎學習認知能力2.順序棧的基本運算（1）初始化棧。SeqStack(){top=0;stack=newchar[MAXSIZE];}（2）判斷棧是否為空。publicbooleanStackEmpty(){if(top==0)returntrue;elsereturnfalse;}3.1棧的表示與實現(xiàn)學習基礎學習認知能力（3）取棧頂元素。在取棧頂元素前，先判斷棧是否為空，如果棧為空，則拋出異常表示取棧頂元素失?。环駝t，將棧頂元素返回。publiccharGetTop()throwsException{if(StackEmpty()){System.out.println("棧為空，取棧頂元素失敗!");thrownewException("棧為空！");}elsereturnstack[top-1];}3.1棧的表示與實現(xiàn)學習基礎學習認知能力（4）將元素e入棧。publicbooleanPushStack(chare){if(top>=MAXSIZE){System.out.println("棧已滿！");returnfalse;}else{stack[top]=e;top++;returntrue;}}3.1棧的表示與實現(xiàn)學習基礎學習認知能力（5）將棧頂元素出棧。在將元素出棧前，需要先判斷棧是否為空。若棧為空，則拋出異常；若棧不為空，則先使棧頂指針減1，然后將棧頂元素返回。publiccharPopStack()throwsException{if(StackEmpty()){System.out.println("棧為空，不能進行出棧操作!");thrownewException("棧為空!");}else{top--;charx=stack[top];returnx;}}3.1棧的表示與實現(xiàn)學習基礎學習認知能力（6）求棧的長度。publicintStackLength(){returntop;}（7）清空棧。publicvoidClearStack(){top=0;}【例3-3】任意給定一個數(shù)學表達式如{5*(9-2)-[15-(8-3)/2]}+3*(6-4)，試設計一個算法判斷表達式的括號是否匹配?！痉治觥繖z驗括號是否匹配可以設置一個棧，每讀入一個括號，如果是左括號，則直接進棧。（1）如果讀入的是右括號：且與當前棧頂?shù)淖罄ㄌ柺峭愋偷?，說明這一對括號是匹配的，則將棧頂?shù)淖罄ㄌ柍鰲?，否則是不匹配。且棧已經為空，說明缺少左括號，該括號序列不匹配。（2）如果輸入序列已經讀完，而棧中仍然有等待匹配的左括號，說明缺少右括號，該括號序列不匹配。（3）如果讀入是數(shù)字字符，則不進行處理，直接讀入下一個字符。publicstaticbooleanMatch(chare,charch){//判斷左右兩個括號是否為同類型，同類型則返回True，否則返回Falseif(e=='('&&ch==')')returntrue;elseif(e=='['&&ch==']')returntrue;elseif(e=='{'&&ch=='}')returntrue;elsereturnfalse;}3.1棧的表示與實現(xiàn)學習基礎學習認知能力3.共享棧使用順序棧會因為?？臻g的大小難以準確估計，從而造成有的棧溢出，有的棧還有空閑。為了解決這個問題，可以讓多個棧共享一個足夠大的連續(xù)存儲空間，利用棧的動態(tài)特性使?？臻g能夠互相補充，存儲空間得到有效利用，這就是棧的共享，這些棧被稱為共享棧。3.1棧的表示與實現(xiàn)學習基礎學習認知能力3.1.4鏈棧1.棧的鏈式存儲結構采用鏈式存儲方式的棧稱為鏈棧或鏈式棧。鏈棧采用帶頭結點的單鏈表實現(xiàn)。

鏈棧結點的類描述如下：classLinkStackNode{intdata;LinkStackNodenext;LinkStackNode(intdata){this.data=data;this.next=next;}}3.1棧的表示與實現(xiàn)學習基礎學習認知能力對于帶頭結點的鏈棧，初始化鏈棧時，有top.next=null，判斷?？盏臈l件為top.next==null。對于不帶頭結點的鏈棧，初始化鏈棧時，有top=null，判斷?？盏臈l件為top==null。3.1棧的表示與實現(xiàn)學習認知能力（1）初始化鏈棧。初始化鏈棧由構造方法LinkStack()實現(xiàn)，即初始化棧頂指針top。publicclassLinkStack{LinkStackNodetop;LinkStack(){top=newLinkStackNode(0);}}（2）判斷鏈棧是否為空。如果頭結點指針域為空，說明鏈棧為空，返回true；否則，返回false。publicbooleanStackEmpty(){if(top.next==null)returntrue;elsereturnfalse;}3.1棧的表示與實現(xiàn)學習基礎學習認知能力（3）進棧操作。先動態(tài)生成一個結點，用pnode指向該結點，再將元素e值賦給pnode結點的數(shù)據(jù)域，然后將新結點插入到鏈表的第一個結點之前。把新結點插入到鏈表中分為兩個步驟：①pnode.next=top.next；②top.next=pnode。publicvoidPushStack(inte)

{

LinkStackNodepnode=newLinkStackNode(e);

pnode.next=top.next;

top.next=pnode;

}3.1棧的表示與實現(xiàn)學習基礎學習認知能力（4）將棧頂元素出棧。先判斷棧是否為空，若棧為空，拋出異常表示出棧操作失??；否則，將棧頂元素值賦給x，釋放該結點空間，最后將棧頂元素返回。publicintPopStack()throwsException{

if(StackEmpty()){

System.out.println("棧為空，不能進行出棧操作!");

thrownewException("棧為空，不能進行出棧操作！");

}

else{

LinkStackNodepnode=top.next;

top.next=pnode.next;

intx=pnode.data;

returnx;

}

}3.1棧的表示與實現(xiàn)學習基礎學習認知能力（5）取棧頂元素。在取棧頂元素前要判斷鏈棧是否為空，如果為空，則拋出異常；否則，將棧頂元素返回。取棧頂元素的算法實現(xiàn)如下。publicintGetTop()throwsException{if(StackEmpty()){System.out.println("棧為空，取棧頂元素失敗!");thrownewException("棧為空!");}elsereturntop.next.data;}3.1棧的表示與實現(xiàn)學習基礎學習認知能力（6）求棧的長度。棧的長度就是鏈棧的元素個數(shù)。從棧頂元素開始，通過next域找到下一個結點，并使用變量len計數(shù)，直到棧底為止。publicintStackLength(){LinkStackNodep=top.next;intlen=0;while(p!=null){p=p.next;len=len+1;}returnlen;}3.1棧的表示與實現(xiàn)學習基礎學習認知能力（7）創(chuàng)建鏈棧。publicvoidCreateStack(){System.out.print("請輸入要入棧的整數(shù)：");Scannerinput=newScanner(System.in);Strings=input.nextLine();String[]arr=s.split("");for(inti=0;i<arr.length;i++){LinkStackNodepnode=newLinkStackNode(Integer.parseInt(arr[i]));pnode.next=top.next;top.next=pnode;}}3.2棧的應用學習基礎學習認知能力將十進制數(shù)N轉換為x進制數(shù)，可用輾轉相除法。（1）將N除以x，取其余數(shù)。（2）判斷商是否為零，如果為零，則結束程序；否則，將商送N，轉（1）繼續(xù)執(zhí)行。所得到的余數(shù)序列正好與x進制數(shù)的數(shù)字序列相反，因此利用棧的后進先出特性，先把得到的余數(shù)序列放入棧保存，最后依次出棧得到x進制數(shù)字序列。01數(shù)制轉換例如，(5678)10=(13056)8，其運算過程如下：3.1棧的表示與實現(xiàn)學習基礎學習認知能力

publicstaticintcovert10to8(intx,intnum[]){LinkStackNodetop=null,p;while(x!=0){p=newLinkStackNode(x%8);p.next=top;top=p;x=x/8;}intk=0;while(top!=null){p=top;num[k++]=p.data;top=top.next;}returnk;}01數(shù)制轉換3.1棧的表示與實現(xiàn)學習基礎學習認知能力設立一個輸入緩沖區(qū)，用來接受用戶輸入的一行字符，然后逐行存入數(shù)據(jù)區(qū)。如果用戶輸入出現(xiàn)錯誤，發(fā)現(xiàn)輸入有誤時及時更正。例如，當用戶發(fā)現(xiàn)剛剛鍵入的一個字符是錯誤的時候，可以輸入一個退格符“#”，以表示前一個字符無效；如果發(fā)現(xiàn)當前輸入的行內差錯較多時，則可以輸入一個退行符“@”，以表示當前行中的字符均無效。02行編輯程序例如，假設從終端接受了兩行字符：whl#ike##le(s#*s)opintf@putchar(*s==##++)則實際有效的是下面的兩行：while(*s)putchar(*s++)3.1棧的表示與實現(xiàn)學習基礎學習認知能力一個表達式由操作數(shù)（operand）、運算符（operator）和分界符（delimiter）組成。操作數(shù)可以是常數(shù)，也可以是變量；運算符可以是算術運算符、關系運算符和邏輯運算符；分界符包括左右括號和表達式的結束符等。03算術表達式求值3.1棧的表示與實現(xiàn)學習基礎學習認知能力將一個算術表達式的中綴形式轉化為相應的后綴形式前，需要先了解算術四則運算的規(guī)則。算術四則運算的規(guī)則是：（1）先計算乘除，后計算加減。（2）先計算括號內的表達式，后計算括號外的表達式。（3）同級別的運算從左到右進行計算。03算術表達式求值3.1棧的表示與實現(xiàn)在計算算術表達式的值時，需要先將中綴表達式轉換為后綴表達式，然后求解表達式的值。1.將中綴表達式轉換為后綴表達式例如，一個算術表達式為：a-(b+c*d)/e對應的后綴表達式為：abcd*+e/-后綴表達式具有以下兩個特點：（1）后綴表達式與中綴表達式的操作數(shù)出現(xiàn)順序相同，只是運算符先后順序改變了。（2）后綴表達式不出現(xiàn)括號。3.1棧的表示與實現(xiàn)運算符優(yōu)先關系表如表3.1所示。3.1棧的表示與實現(xiàn)中綴表達式轉換為后綴表達式的算法如下：（1）初始化棧，將“#”入棧。（2）如果當前讀入的字符是操作數(shù)，則將該操作數(shù)輸出，并讀入下一字符。（3）如果當前字符是運算符，記作?2，則將?2與棧頂?shù)倪\算符?1比較。如果棧頂?shù)倪\算符?1優(yōu)先級小于當前運算符?2，則將當前運算符?2進棧；如果棧頂?shù)倪\算符?1優(yōu)先級大于當前運算符?2，則將棧頂運算符?1出棧并將其作為后綴表達式輸出。然后繼續(xù)比較新的棧頂運算符?1與當前運算符?2的優(yōu)先級，如果棧頂運算符?1的優(yōu)先級與當前運算符?2相等，且?1為“(”、?2為“)”，則將?1出棧，繼續(xù)讀入下一個字符。（4）如果當前運算符?2的優(yōu)先級與棧頂運算符?1相等，且?1和?2都為“#”，將?1出棧，棧為空。則中綴表達式轉換為后綴表達式，算法結束。3.1棧的表示與實現(xiàn)中綴表達式(8*(15-9)+6)/3轉換為后綴表達式的輸出過程如表3.-2所示。3.1棧的表示與實現(xiàn)后綴表達式的求值算法如下（假設棧頂運算符為?1，當前掃描的運算符為?2）：（1）初始化S棧。（2）如果當前讀入的字符是操作數(shù)，則將該操作數(shù)進入S棧。（3）如果當前字符是運算符?，則將S棧退棧兩次，分別得到操作數(shù)x和y，對x和y進行?運算，即y?x，得到中間結果z，將z進S棧。（4）重復執(zhí)行步驟（2）和（3），直到S為空。3.1棧的表示與實現(xiàn)6+(7-1)*3+9/2，中綴表達式轉換為后綴表達式3.1棧的表示與實現(xiàn)根據(jù)得到的后綴表達式6+(7-1)*3+9/2#，利用棧求解表達式的值3.2棧與遞歸3.2.1遞歸遞歸是指在函數(shù)的定義中，在定義自己的同時又出現(xiàn)了對自身的調用。1.遞歸函數(shù)例如，n的階乘遞歸定義如下：deffact(n):#n的階乘

ifn==1:

return1

else:

returnn*fact(n-1)3.3棧與遞歸Ackermann函數(shù)定義如下：defAck(m,n):#Ackerman遞歸算法實現(xiàn)

ifm==0:returnn+1

elifn==0:returnAck(m-1,1)

else:returnAck(m-1,Ack(m,n-1))【例3-6】如果兔子在出生兩個月后就有繁殖能力，以后一對兔子每個月能生出一對兔子，假設所有兔子都不死，那么一年以后可以繁殖多少對兔子呢？經過的月數(shù)123456789101112兔子對數(shù)1123581321345589144表3-3每月兔子的對數(shù)publicstaticintfib2(intn){if(n==0)//若是第0項

return0;//則返回0elseif(n==1)//若是第1項

return1;//則返回1else//其他情況

returnfib2(n-1)+fib2(n-2);//第三項為前兩項之和}當n=4時，遞歸函數(shù)執(zhí)行過程3.3棧與遞歸2.遞歸調用過程n階漢諾塔問題。假設有三個塔座X、Y、Z，在塔座X上放置有n個直徑大小各不相同、從小到大編號為1、2、…、n的圓盤。要求圓盤移動時必須遵循以下規(guī)則：（1）每次只能移動一個圓盤。（2）圓盤可以放置在X、Y和Z中的任何一個塔座。（3）任何時候都不能將一個較大的圓盤放在較小的圓盤上。3.3棧與遞歸2.遞歸調用過程n階漢諾塔問題。3.3棧與遞歸publicstaticvoidHanoi(intn,StringA,StringB,StringC)//將塔座A上按照從小到大自上而下編號為1到n的圓盤按照規(guī)則搬到塔座C上，B作為輔助塔座{

if(n==1)

move(1,A,C);//將編號為1的圓盤從A移動到C

else{

Hanoi(n-1,A,C,B);//將編號為1到n-1的圓盤從A移動到B，C作為輔助塔座

move(n,A,C);//將編號為n的圓盤從A移動到C

Hanoi(n-1,B,A,C);//將編號為1到n-1的圓盤從B移動到C，A作為輔助塔座

}

}

publicstaticvoidmove(intn,StringtempA,StringtempB){System.out.println("moveplate"+n+"fromcolumn"+tempA+"tocolumn"+tempB);}3.3棧與遞歸在遞歸調用過程中，運行被調用函數(shù)前系統(tǒng)要完成3件事情：（1）將所有參數(shù)和返回地址傳遞給被調用函數(shù)保存。（2）為被調用函數(shù)的局部變量分配存儲空間。（3）將控制轉到被調用函數(shù)的入口。當被調用函數(shù)執(zhí)行完畢，返回到調用函數(shù)之前，系統(tǒng)同樣需要完成3個任務：（1）保存被調用函數(shù)的執(zhí)行結果。（2）釋放被調用函數(shù)的數(shù)據(jù)存儲區(qū)。（3）將控制轉到調用函數(shù)的返回地址處。3.3棧與遞歸3.3.2消除遞歸遞歸的算法也完全可以轉換為非遞歸實現(xiàn)，這就是遞歸的消除。消除遞歸方法有兩種：一種是對于簡單的遞歸可以直接用迭代，通過循環(huán)結構就可以消除；另一種方法是利用棧的方式實現(xiàn)。publicstaticlongfact(intn)//n的階乘的非遞歸算法實現(xiàn){

longf=1;

inti;

for(i=1;i<n+1;i++)//直接利用迭代消除遞歸

f=f*i;

returnf;

}3.3棧與遞歸利用棧消除遞歸

do{if(s[top][0]==1)//遞歸出口

{s[top][1]=1;System.out.println("n="+s[top][0]+",fact="+s[top][1]);}if(s[top][0]>1&&s[top][1]==0)//通過棧模擬遞歸的遞推過程，將問題依次入棧

{top=top+1;s[top][0]=s[top-1][0]-1;s[top][1]=0;//將結果置為0，還沒有返回結果

System.out.println("n="+s[top][0]+",fact="+s[top][1]);}if(s[top][1]!=0)//模擬遞歸的返回過程，將每一層調用的結果返回

{s[top-1][1]=s[top][1]*s[top-1][0];System.out.println("n="+s[top-1][0]+",fact="+s[top-1][1]);top=top-1;}}while(top>0);3.3棧與遞歸利用棧消除遞歸請輸入一個正整數(shù)(n<15)：5遞歸實現(xiàn)n的階乘:n!=120利用棧非遞歸實現(xiàn)n的階乘:n=4,fact=0n=3,fact=0n=2,fact=0n=1,fact=0n=1,fact=1n=2,fact=2n=3,fact=6n=4,fact=24n=5,fact=120n!=1203.3隊列3.3.1隊列的定義隊列（Queue）是一種先進先出（FirstInFirstOut，縮寫為FIFO）的線性表，它只允許在表的一端插入元素，而在另一端刪除元素。其中，允許插入的一端叫作隊尾（rear），允許刪除的一端稱為隊頭（front）。假設隊列為q=（a1，a2，…，ai，…，an），那么a1就是隊頭元素，an則是隊尾元素。3.3隊列3.3.2隊列的抽象數(shù)據(jù)類型ADTQueue{

數(shù)據(jù)對象：D={ai|ai∈ElemSet，i=1，2，…，n，n≥0}

數(shù)據(jù)關系：R={<ai-1,ai>|ai-1，ai∈D，i=2，3，…，n}

約定a1端為隊列頭，an端為隊列尾?；静僮鳎海?）InitQueue(&Q)

初始條件：隊列Q不存在。操作結果：建立一個空隊列Q。（2）QueueEmpty(Q)

初始條件：隊列Q已存在。操作結果：若Q為空隊列，返回1，否則返回0。3.3隊列（3）EnQueue(&Q,e)

初始條件：隊列Q已存在。操作結果：插入元素e到隊列Q的隊尾。（4）DeQueue(&Q,&e)

初始條件：隊列Q已存在且為非空。操作結果：刪除Q的隊頭元素，并用e返回其值。（5）Gethead(Q,&e)

初始條件：隊列Q已存在且為非空。操作結果：用e返回Q的隊頭元素。（6）ClearQueue(&Q)

初始條件：隊列Q已存在。操作結果：將隊列Q清為空隊列。}ADTQueue3.3隊列3.3.3順序隊列隊列有兩種存儲表示：順序存儲和鏈式存儲。采用順序存儲結構的隊列稱為順序隊列，采用鏈式存儲結構的隊列稱為鏈式隊列。1.順序隊列的表示順序隊列通常采用列表作為存儲結構。3.3隊列為了方便描述，我們約定：初始化時，隊列為空，有front=rear=0，隊頭指針front和隊尾指針rear都指向隊列的第一個位置，如圖3.23所示。3.3隊列順序隊列的類型描述如下：publicclassSeQueue<T>{finalintQUEUESIZE=20;Ts[];intfront,rear;}3.3隊列2.順序隊列的“假溢出”3.3隊列3.4.4順序循環(huán)隊列1.順序循環(huán)隊列的構造為了充分利用存儲空間，消除這種“假溢出”，當隊尾指針rear（或隊頭指針front）到達存儲空間的最大值QUEUESIZE的時候，讓隊尾指針rear（或隊頭指針front）自動轉化為存儲空間的最小值0。這樣，順序隊列的存儲空間就構成一個邏輯上首尾相連的循環(huán)隊列。2.順序循環(huán)隊列的隊空和隊滿（1）增加一個標志位。（2）少用一個存儲空間。3.3隊列初始化隊列。publicclassSeQueue<T>{finalintQUEUESIZE=20;Ts[];intfront,rear;SeQueue(){//順序循環(huán)隊列的初始化

s=(T[])newObject[QUEUESIZE];front=0;//把隊頭指針置為0rear=0;//把隊尾指針置為0}3.3隊列②判斷隊列是否為空。若隊頭指針與隊尾指針相等，則隊列為空；否則隊列不為空。publicbooleanIsEmpty()//判斷順序循環(huán)隊列是否為空{if(front==rear)//當順序循環(huán)隊列為空時

returntrue;//返回trueelse//否則

returnfalse;//返回false}3.3隊列③將元素x入隊。在將元素入隊（即把元素插入到隊尾）之前，先判斷隊列是否已滿。如果隊列未滿，則執(zhí)行插入運算，然后隊尾指針加1把隊尾指針向后移動。publicbooleanEnQueue(Tx)//元素e插入到順序循環(huán)隊列中，插入成功返回true，否則返回false{if((rear+1)%QUEUESIZE!=front)//在插入新元素前，判斷隊尾指針是否上溢

{s[rear]=x;//在隊尾插入元素erear=(rear+1)%QUEUESIZE;//將隊尾指針向后移動一個位置

returntrue;}else{System.out.println("當前隊列已滿!");returnfalse;}}3.3隊列④將隊頭元素出隊。在隊頭元素出隊（即刪除隊頭元素）之前，先判斷隊列是否為空。若隊列不空，則刪除隊頭元素，然后將隊頭指針向后移動，使其指向下一個元素。publicTDeQueue()throwsException{//將隊頭元素出隊，并將該元素賦值給eif(front==rear)//若隊列是否為空

{System.out.println("隊列為空，出隊操作失?。?);thrownewException("隊列為空，不能進行出隊操作");}else{Te=s[front];//將待出隊的元素賦值給efront=(front+1)%QUEUESIZE;//將隊頭指針向后移動一個位置，指向新的隊頭

returne;//返回出隊的元素

}}

3.3隊列⑤取隊頭元素。先判斷順序循環(huán)隊列是否為空，如果隊列為空，則拋出異常表示取隊頭元素失?。环駝t，取出隊頭元素返回，表示取隊頭元素成功。publicTGetHead()throwsException{//取隊頭元素，并將該元素返回

if(!IsEmpty())//若順序循環(huán)隊列不為空

return(T)s[front];//返回隊頭元素

else//否則

{System.out.println("隊列為空");thrownewException("隊列為空");}}

3.3隊列⑥獲取隊列的長度。publicintSeqLength(){return(rear-front+QUEUESIZE)%QUEUESIZE;}⑦隊列的創(chuàng)建。publicvoidCreateSeqQueue(){inti=0;System.out.println("請輸入元素（#作為輸入結束）:");Scannersc=newScanner(System.in);Integerdata=sc.nextInt();while(data!=-1){EnQueue(data);i++;data=sc.nextInt();}}

3.3隊列1.鏈式隊列的表示鏈式隊列通常用鏈表實現(xiàn)。一個鏈隊列顯然需要兩個分別指示隊頭和隊尾的指針（分別稱為隊頭指針和隊尾指針）才能唯一確定。這里，與單鏈表一樣，為了操作方便，給鏈隊列添加一個頭結點，并令隊頭指針front指向頭結點，用隊尾指針rear指向最后一個結點。一個不帶頭結點的鏈式隊列和帶頭結點的鏈隊列分別如圖3-34、圖3-35所示。

3.3隊列鏈式隊列的結點類型描述如下：classQueueNode{chardata;QueueNodenext;QueueNode(chardata){this.data=data;this.next=null;}}

3.3隊列（2）鏈式循環(huán)隊列將鏈式隊列的首尾相連就構成了鏈式循環(huán)隊列。在鏈式循環(huán)隊列中，可以只設置隊尾指針，如圖3-40所示。當隊列為空時，如圖3-41所示，隊列LQ為空的判斷條件為LQ.rear.next==LQ.rear。

3.3隊列（1）初始化隊列。先生成一個QueueNode類型的結點，然后讓front和rear分別指向該結點。publicclassLinkQueue{QueueNodefront,rear;LinkQueue()//初始化隊列

{QueueNodeQNode=newQueueNode('0');front=QNode;rear=QNode;}}。

3.3隊列（2）判斷隊列是否為空。publicbooleanQueueEmpty()//判斷鏈式隊列是否為空，隊列為空返回true，否則返回false{if(front==rear)//若鏈式隊列為空時

returntrue;//則返回trueelse//否則

returnfalse;//返回false}。

3.3隊列（3）將元素e入隊。先生成一個新結點pNode，再將e賦給該結點的數(shù)據(jù)域，使原隊尾元素結點的指針域指向新結點，最后讓隊尾指針指向新結點，從而將結點加入隊列中。

publicvoidEnQueue(chare)//將元素e入隊{QueueNodepNode=newQueueNode(e);//生成一個新結點,將元素值賦給結點的數(shù)據(jù)域

rear.next=pNode;//將原隊列的隊尾結點的指針指向新結點

rear=pNode;//將隊尾指針指向新結點

}3.3隊列（4）將隊頭元素出隊。刪除隊頭元素時，應首先通過隊頭指針和隊尾指針是否相等判斷隊列是否已空。若隊列非空，則刪除隊頭元素，然后將指向隊頭元素的指針向后移動，使其指向下一個元素。

publiccharDeQueue()throwsException//將鏈式隊列中的隊頭元素出隊返回該元素，若隊列為空，則拋出異常{if(QueueEmpty())//在出隊前，判斷鏈式隊列是否為空

{System.out.println("隊列為空,不能進行出隊操作!");thrownewException("隊列為空，不能出隊操作");}else

{QueueNodepNode=front.next;//使pNode指向隊頭元素

front.next=pNode.next;//使頭結點的next指向pNode的下一個結點

if(pNode==rear)//如果要刪除的結點是隊尾，則使隊尾指針指向隊頭

rear=front;returnpNode.data;//返回出隊元素

}}3.3隊列（5）取隊頭元素。在取隊頭元素之前，先判斷鏈式隊列是否為空。

publicintgetHead()//取鏈式隊列中的隊頭元素{if(!QueueEmpty())//若鏈式隊列不為空

returnfront.next.data;//返回隊頭元素}3.3隊列【例3-11】編寫一個算法，判斷任意給定的字符序列是否為回文。所謂回文是指一個字符序列以中間字符為基準兩邊字符完全相同，即順著看和倒著看是相同的字符序列。例如，字符序列“XYZMTATMZYX”為回文，而字符序列“回文，而字符序列不是回文。

Stringstr1=newString("XYZMTATMZYX");Stringstr2=newString("ABCBCAB");for(inti=0;i<str1.length();i++){LQ1.EnQueue(str1.charAt(i));LS1.PushStack(str1.charAt(i));}for(inti=0;i<str2.length();i++){LQ2.EnQueue(str2.charAt(i));LS2.PushStack(str2.charAt(i));

}System.out.println("字符序列1:"+str1);System.out.println("出隊序列出棧序列");while(!LS1.StackEmpty())//判斷堆棧1是否為空

{charq1=LQ1.DeQueue();//字符序列依次出隊，并把出隊元素賦值給qchars1=LS1.PopStack();//字符序列出棧，并把出棧元素賦值給sSystem.out.println(q1+":"+s1);if(q1!=s1){System.out.println("字符序列1不是回文！");return;}}3.4雙端隊列雙端隊列是一種特殊的隊列，它是在線性表的兩端對插入和刪除操作限制的線性表。雙端隊列可以在隊列的任何一端進行插入和刪除操作，而一般的隊列要求在一端插入元素，在另一端刪除元素。如圖3.30所示。

元素a、b、c依次進入右端的隊列，元素e、f依次進入左端的隊列，如圖3-45所示。3.5隊列的應用3.5.1隊列在楊輝三角中的應用1.楊輝三角楊輝三角是一個由數(shù)字排列成的三角形數(shù)表，一個8階的楊輝三角圖形如圖3.41所示。

3.5隊列的應用（1）在第8行中，第一個元素先入隊。假設隊列為Q，Q.queue[rear]=1、Q.rear=(Q.rear+1)%QUEUESIZE。（2）第8行中的中間6個元素需要通過第7行（已經入隊）得到并入隊。Q.queue[rear]=Q.queue[front]+Q.queue[front+1]、Q.rear=(Q.rear+1)%QUEUESIZ、Q.front=(Q.front+1)%QUEUESIZE。（3）第7行最后一個元素出隊，Q.front=(Q.front+1)%QUEUESIZE。（4）第8行最后一個元素入隊，Q.queue[rear]=1、Q.rear=(Q.rear+1)%QUEUESIZE。

3.5隊列的應用（1）在第8行中，第一個元素先入隊。假設隊列為Q，Q.queue[rear]=1、Q.rear=(Q.rear+1)%QUEUESIZE。（2）第8行中的中間6個元素需要通過第7行（已經入隊）得到并入隊。Q.queue[rear]=Q.queue[front]+Q.queue[front+1]、Q.rear=(Q.rear+1)%QUEUESIZ、Q.front=(Q.front+1)%QUEUESIZE。（3）第7行最后一個元素出隊，Q.front=(Q.front+1)%QUEUESIZE。（4）第8行最后一個元素入隊，Q.queue[rear]=1、Q.rear=(Q.rear+1)%QUEUESIZE。

3.6小結棧是一種只允許在線性表的一端進行插入和刪除操作的線性表。其中，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。棧的特點是后進先出，使棧在程序設計、編譯處理得到有效的利用。數(shù)制轉換、括號匹配、表達式求值等問題都是利用棧的后進先出特性解決的。隊列只允許在線性表的一端進行插入操作，在線性表的另一端進行刪除操作。隊列也有兩種存儲方式：順序存儲和鏈式存儲。采用順序存儲結構的棧稱為順序隊列，采用鏈式存儲結構的棧稱為鏈式隊列。順序隊列存在“假溢出”的問題，順序隊列的“假溢出”不是因為存儲空間不足而產生的，而是因為經過多次的出隊和入隊操作之后，存儲單元不能有效利用造成的。感謝聆聽主講：結構Java實據(jù)現(xiàn)數(shù)第4章串、數(shù)組和廣義表結構Java實據(jù)現(xiàn)數(shù)目錄CONTENTS4.1

串的定義和抽象數(shù)據(jù)類型4.2串的存儲表示4.3串的模式匹配4.6小結4.4數(shù)組的定義和抽象數(shù)據(jù)類型4.5廣義表4.1串的定義和抽象數(shù)據(jù)類型4.1.1什么是串串（String），也稱為字符串，是由零個或多個字符組成的有限序列。串是一種特殊的線性表，僅由字符組成。一般記作：S=”a1a2…an”。其中，S是串名，n是串的長度。用雙引號括起來的字符序列是串的值。ai(1≤i≤n)可以是字母、數(shù)字和其他字符。n=0時，串稱為空串。例如，有四個串a="tinghuauniversity"、b="tinghua"、c="university"、d="tinghuauniversity"。它們的長度分別為18、7、10、17，b和c是a和d的子串，b在a和d的位置都為1，c在a的位置是9，c在d的位置是8。4.1串的定義和抽象數(shù)據(jù)類型4.1.2串的抽象數(shù)據(jù)類型串的抽象數(shù)據(jù)類型定義了棧中的數(shù)據(jù)對象、數(shù)據(jù)關系及基本操作。棧的抽象數(shù)據(jù)類型定義如下：ADTString{數(shù)據(jù)對象：D={ai|ai∈CharacterSet，i=1，2，…，n，n≥0}數(shù)據(jù)關系：R={<ai-1,ai>|ai-1，ai∈D，i=2，3，…，n}基本操作：（1）StrAssign(&S,cstr)初始條件：cstr是字符串常量。操作結果：生成一個其值等于cstr的串S。（2）StrEmpty(S)初始條件：串S已存在。操作結果：如果是空串，則返回1，否則返回0。4.1串的定義和抽象數(shù)據(jù)類型（4）StrCopy(&T,S)初始條件：串S已存在。操作結果：由串S復制產生一個與S完全相同的另一個字符串T。（5）StrCompare(S,T)初始條件：串S和T已存在。操作結果：比較串S和T的每個字符的ASCII值的大小，如果S的值大于T，則返回1；如果S的值等于T，則返回0；如果S的值小于T，則返回-1。例如，StrCompare(S,T)=-1，因為串S和串T比較到第13個字符時，字符B的ASCII值小于字符S的ASCII值，所以返回-1。（6）StrInsert(&S,pos,T)初始條件：串S和T已存在，且1≤pos≤StrLength(S)+1。操作結果：在串S的pos個位置插入串T，如果插入成功，則返回1，否則返回0。例如，如果在串S中的第3個位置插入字符串"don’t"后，即StrInsert(S,3,"don’t")，串S="Idon’tcomefromBeijing"。4.1串的定義和抽象數(shù)據(jù)類型（7）StrDelete(&S,pos,len)初始條件：串S已存在，且1≤pos≤StrLength(S)-len+1。操作結果：如果在串S中刪除第pos個字符開始，長度為len的字符串。如果找到并刪除成功，則返回1，否則返回0。例如，如果在串S中的第13個位置刪除長度為7的字符串后，即StrDelete(S,13,7)，則S="Icomefrom"。（8）StrConcat(&T,S)初始條件：串S和T已存在。操作結果：將串S連接在串T的后面。如果連接成功，則返回1，否則返回0。例如，如果將串S連接在串T的后面，即StrCat(T,S)，則T="IcomefromShanghaiIcomefromBeijing"。（9）SubString(&Sub,S,pos,len)初始條件：串S已存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-len+1。操作結果：從串S中截取從第pos個字符開始，長度為len的連續(xù)字符，并賦值給Sub。如果截取成功，則返回1，否則返回0。例如，如果將串S中的第8個字符開始，長度為4的字符串賦值給Sub，即SubString(Sub,S,8,4)，則Sub="from"。4.1串的定義和抽象數(shù)據(jù)類型（10）StrReplace(&S,T,V)初始條件：串S、T和V已存在，且T為非空串。操作結果：如果在串S中存在子串T，則用V替換串S中的所有子串T。如果替換操作成功，則返回1，否則返回0。例如，如果將串S中的子串R替換為串V，即StrReplace(S,R,V)，則S="IcomefromChongqing"。（11）StrIndex(S,pos,T)初始條件：串S和T存在，T是非空串，且1≤len≤StrLength(S)。操作結果：如果主串S中存在與串T的值相等的子串，則返回子串T在主串S中，第pos個字符之后的第一次出現(xiàn)的位置，否則返回0。例如，在串S中的第4個字符開始查找，如果串S中存在與子串R相等的子串，則返回R在S中第一次出現(xiàn)的位置，即StrIndex(S,4,R)=13。4.2串的存儲表示4.2.1串的順序存儲結構用Java中的字符串類型表示串，可通過一對雙引號括起來的字符表示字符串。例如：Stringstr=“HelloWorld!”;確定串的長度有兩種方法（1）使用String類中的length()方法獲得串的長度，（2）引入一個變量length來記錄串的長度。例如，串”HelloWorld!”在內存中，用設置串的長度的方法的表示如圖4-2所示。publicclassSeqString//定義字符串結構類型{finalintMAXSIZE=100;charstr[];intlength;SeqString(chars[]){str=newchar[MAXSIZE];for(inti=0;i<s.length;i++)str[i]=s[i];length=s.length;}}4.2串的存儲表示4.2.2串的鏈式存儲結構在順序串中，對于串的插入操作、串的連接及串的替換操作，如果串的長度超過了MaxLen，串會被截斷處理。為了克服這些缺點，可以使用鏈式存儲結構表示的串進行處理。4.2串的存儲表示塊鏈串類型定義如下：classChunk//串的結點類型定義{finalintChunkSize=4;charch[];Chunknext;

}classLinkString//鏈串的類型定義{Chunkhead,tail;intlength;}其中，head表示頭指針，指向鏈串的第一個結點。tail表示尾指針，指向鏈串的最后一個結點。length表示鏈串中字符的個數(shù)。4.3串的模式匹配4.3.1樸素模式匹配算法——模式匹配算法Brute-Force子串的定位操作串通常稱為模式匹配，是各種串處理系統(tǒng)中最重要的操作之一。設有主串S和子串T，如果在主串S中找到一個與子串T相等的串，則返回串T的第一個字符在串S中的位置。其中，主串S又稱為目標串，子串T又稱為模式串。4.3串的模式匹配例如，主串S="abaababaddecab"，子串T="abad"，S的長度為n=13，T的長度為m=4。用變量i表示主串S中當前正在比較字符的下標，變量j表示子串T中當前正在比較字符的下標。模式匹配的過程如圖4-8所示。4.3串的模式匹配publicintB_FIndex(SeqStringS,SeqStringT,intpos){//在主串S中的第pos個位置開始查找模式串T，如果找到返回子串在主串的位置；否則，返回-1

inti=pos-1;intj=0;

count=0;

while(i<S.length&&j<T.length){

if(S.str[i]==T.str[j])//若串S和T字符相等，則繼續(xù)比較下一個字符

{

i+=1;j+=1;}

else//若對應字符不相等，則從串S的下一個字符、T的第0個字符開始比較

{i=i-j+1;j=0;}

count++;

}

if(j>=T.length)//如果在S中找到串T，則返回子串T在主串S的位置

returni-j+1;

else

return-1;

}4.3串的模式匹配例如設主串S="aaaaaaaaaaaaab"，模式串T="aaab"。其中，n=14，m=4。因為模式串的前3個字符是"aaa"，主串的前13個字符也是"aaa"，每趟比較模式串的最后一個字符與主串中的字符不相等，所以均需要將主串的指針回退，從主串的下一個字符開始與模式串的第一個字符重新比較。在整個匹配過程中，主串的指針需要回退9次，匹配不成功的比較次數(shù)是10*4，成功匹配的比較次數(shù)是4次，因此總的比較次數(shù)是10*4+4=11*4即(n-m+1)*m。Brute-Force匹配算法在最好的情況下，即主串的前m個字符剛好與模式串相等，時間復雜度為O(m)。在最壞的情況下，Brute-Force匹配算法的時間復雜度是O(n*m)。4.3串的模式匹配4.3.2KMP算法KMP算法是由D.E.Knuth、J.H.Morris、V.R.Pratt共同提出的，因此稱為KMP算法（Knuth-Morris-Pratt算法）。KMP算法在Brute-Force算法的基礎上有較大改進4.3串的模式匹配從圖4-9中可以看出，KMP算法的匹配次數(shù)由原來的6次減少為4次。在第一次匹配的過程中，當i=3、j=3，主串中的字符與子串中的字符不相等，Brute-Force算法從i=1、j=0開始比較。將主串的指針回退的比較是沒有必要的，在第一次比較遇到主串與子串中的字符不相等時，有S0=T0="a"，S1=T1="b"，S2=T2="a"，S3≠T3。因為S1=T1且T0≠T1，所以S1≠T0，S1與T0不必比較。又因為S2=T2且T0=T2，有S2=T0，所以從S3與T1開始比較。4.3串的模式匹配假設主串S="s0s1…sn-1"，T="t0t1…tm-1"。在模式匹配過程中，如果出現(xiàn)字符不匹配的情況，即當Si≠Tj(0≤i<n,0≤j<m)時，有："si-jsi-j+1…si-1"="t0t1…tj-1"假設子串即模式串存在可重疊的真子串，即："t0t1…tk-1"="tj-ktj-k+1…tj-1"4.3串的模式匹配如果令next[j]=k，則next[j]表示：當子串中的第j個字符與主串中的對應的字符不相等時，下一次子串需要與主串中該字符進行比較的字符的位置。子串即模式串中的next函數(shù)，定義如下：4.3串的模式匹配KMP算法的模式匹配過程：如果模式串T中存在真子串"t0t1…tk-1"="tj-ktj-k+1…tj-1"，當模式串T與主串S的si不相等，則按照next[j]=k將模式串向右滑動，從主串中的si與模式串的tk開始比較。如果si=tk，則主串與子串的指針各自增1，繼續(xù)比較下一個字符。如果si≠tk，則按照next[next[j]]將模式串繼續(xù)向右滑動，將主串中的si與模式串中的next[next[j]]字符進行比較。4.3串的模式匹配publicintKMP_Index(SeqStringS,SeqStringT,intpos,intnext[])//KMP模式匹配算法。利用模式串T的next函數(shù)在主串S中的第pos個位置開始查找模式串T，如果找到返回模式串在主串的位置；否則，返回-1{

inti=pos-1;

intj=0;count=0;

while(i<S.length&&j<T.length)

{

if(j==-1||S.str[i]==T.str[j])//如果j=-1或當前字符相等，則繼續(xù)比較后面的字符

{

i+=1;j+=1;}

else//如果當前字符不相等，則將模式串向右移動

{j=next[j];//next保存next函數(shù)值

}

count++;

}

if(j>=T.length)//匹配成功，返回子串在主串中的位置