第04章 棧和隊列(Java版)

第4章棧和隊列4.1棧4.2隊列4.3遞歸目的：使用?；蜿犃星蠼鈶?yīng)用問題。要求：棧和隊列的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)。重點：棧和隊列的設(shè)計和應(yīng)用。難點：棧或隊列的使用場合，以及如何使用 棧和隊列求解應(yīng)用問題。4.1棧4.1.1棧抽象數(shù)據(jù)類型

棧（stack）是一種線性表，插入和刪除操作只允許在線性表的一端進行。先進后出。圖4.1棧（順序棧）及其狀態(tài)變化{A,B,C,D}{入棧,入棧,出棧,入棧,入棧,出棧,出棧,出棧}【思考題4-1】入棧{A,B,C,D}，出棧{A,B,C,D}、{D,C,B,A}？還有哪些？有哪些不可能的出棧序列？為什么？棧抽象數(shù)據(jù)類型ADT，棧接口publicinterfaceStack<T>{publicabstractbooleanisEmpty();//判空

publicabstractvoidpush(Tx);//x入棧

publicabstractTpeek();//返回棧頂，未出棧

publicabstractTpop();//出棧，返回棧頂}習(xí)題4-3習(xí)4-3

能否使用一個線性表對象作為棧，或?qū)Ｂ暶鳛槔^承線性表？入棧調(diào)用insert(0,x)函數(shù)，出棧調(diào)用remove(0)函數(shù)？為什么？【習(xí)題解答】都不能。4.1.2順序棧//順序棧類，最終類，實現(xiàn)棧接口，T表示元素類型publicfinalclassSeqStack<T>implementsStack<T>{privateSeqList<T>list;//順序表publicSeqStack(intcapacity)//構(gòu)造空棧publicSeqStack()//構(gòu)造空棧publicbooleanisEmpty()//判空publicvoidpush(Tx)//x入棧publicTpeek()//返回棧頂（未出棧）publicTpop()//出棧，返回棧頂元素}習(xí)題解答4-4使用順序表對象作為棧成員變量的操作效率分析4.1.3鏈?zhǔn)綏D4.3鏈?zhǔn)綏５娜霔：统鰲２僮鳌稊?shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章8鏈?zhǔn)綏ｎ怢inkedStack<T>//鏈?zhǔn)綏ｎ?，最終類，實現(xiàn)棧接口，T表示元素類型publicfinalclassLinkedStack<T>

implementsStack<T>{privateSinglyList<T>list;//單鏈表

publicLinkedStack()//構(gòu)造空棧publicbooleanisEmpty()//判空publicvoidpush(Tx)//x入棧publicTpeek()//返回棧頂（未出棧）publicTpop()//出棧，返回棧頂元素}《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章9習(xí)題解答4-4使用單鏈表對象作為棧成員變量的操作效率分析《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章104.1.4棧的應(yīng)用棧是嵌套調(diào)用機制的實現(xiàn)基礎(chǔ)使用棧以非遞歸方式實現(xiàn)遞歸算法《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章11【例4.1】括號匹配的語法檢查。圖4.5表達(dá)式中圓括號匹配的語法檢查《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章12【例4.2】使用棧計算算術(shù)表達(dá)式值中綴表達(dá)式：1+2*(3-4)+5《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章13習(xí)題4-5【習(xí)題解答】ABCDEF+*G/-H+*+IJ+K*-習(xí)4-5

中綴表達(dá)式如下，寫出后綴表達(dá)式。

A+B*(C-D*(E+F)/G+H)-(I+J)*K《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章14（1）將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章15（2）后綴表達(dá)式求值《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章16ExpressionpublicclassExpression{StringBuffertoPostfix(Stringinfix)//返回將infix中綴表達(dá)式轉(zhuǎn)換成的后綴表達(dá)式inttoValue(StringBufferpostfix) //計算后綴表達(dá)式的值}【思考題4-2】《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章174.2隊列4.2.1隊列抽象數(shù)據(jù)類型隊列（queue）是一種特殊的線性表，其插入和刪除操作分別在線性表的兩端進行。先進先出。《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章184.2.1隊列抽象數(shù)據(jù)類型//隊列接口，描述隊列抽象數(shù)據(jù)類型，T表示元素類型publicinterfaceQueue<T>{

publicabstractbooleanisEmpty();//判空

publicabstractbooleanadd(Tx);//x入隊

publicabstractTpeek();//返回隊頭，沒有刪除publicabstractTpoll();//出隊，返回隊頭}《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章19習(xí)題4-8習(xí)4-8

能否使用一個線性表對象作為隊列，或?qū)㈥犃新暶鳛槔^承線性表，入棧調(diào)用insert(x)函數(shù)，出棧調(diào)用remove(0)函數(shù)？為什么？【習(xí)題解答】都不能?！稊?shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章204.2.2順序隊列順序隊列（1）使用順序表，出隊效率低《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章21（2）使用數(shù)組，存在假溢出不移動數(shù)據(jù)元素《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章222.順序循環(huán)隊列front=(front+1)%length;rear=(rear+1)%length;《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章233.順序循環(huán)隊列類//順序循環(huán)隊列類，最終類，實現(xiàn)隊列接口，T元素類型publicfinalclassSeqQueue<T>implementsQueue<T>{

privateObjectelement[];//數(shù)組

privateintfront,rear;//隊列頭尾下標(biāo)

publicSeqQueue(intcapacity)//構(gòu)造空隊列publicSeqQueue()//構(gòu)造空隊列publicbooleanisEmpty();//判空publicbooleanadd(Tx);//x入隊publicTpeek();//返回隊頭，沒有刪除publicTpoll();//出隊，返回隊頭}

《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章244.2.3鏈?zhǔn)疥犃校?）使用單鏈表，入隊效率低《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章25（2）單鏈表設(shè)計，增加尾指針《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章26鏈?zhǔn)疥犃蓄怢inkedQueue<T>//鏈?zhǔn)疥犃蓄?，最終類，實現(xiàn)隊列接口，T元素類型publicfinalclassLinkedQueue<T>implementsQueue<T>{privateNode<T>front,rear;//隊頭和隊尾結(jié)點

publicLinkedQueue()//構(gòu)造空隊列

publicbooleanisEmpty();//判空publicbooleanadd(Tx);//x入隊publicTpeek();//返回隊頭，沒有刪除publicTpoll();//出隊，返回隊頭}《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章274.2.4隊列的應(yīng)用【例4.3】求解素數(shù)環(huán)問題?！稊?shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章28【例4.3】求解素數(shù)環(huán)問題。publicclassPrimeRing

{publicPrimeRing(intmax)publicSortedSeqList<Integer>

createPrime(intmax)}【思考題4-3】①使用循環(huán)雙鏈表存儲素數(shù)集合和素數(shù)環(huán)。②使用棧？《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章29實驗4-13走迷宮(a)棧存儲經(jīng)過的點，出棧返回上一個點，再尋找其他路徑《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章30實驗4-13走迷宮《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章31實驗4-14騎士游歷《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章32實驗4-14

騎士游歷8×8棋盤，從(0,0)開始的一次游歷路徑5×5棋盤，一次不成功游歷路徑《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章334.2.5優(yōu)先隊列優(yōu)先隊列（PriorityQueue），隊列中的每個元素都有一個優(yōu)先級，每次出隊的是具有最高優(yōu)先級的元素。優(yōu)先隊列的存儲結(jié)構(gòu)。分別使用一個順序表、排序順序表、單鏈表、排序單鏈表、循環(huán)雙鏈表、排序循環(huán)雙鏈表作為優(yōu)先隊列的成員變量，分析優(yōu)先隊列的入隊和出隊操作的效率。《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章34習(xí)題4-13優(yōu)先隊列優(yōu)先隊列，分別使用各種線性表。{(E,4),(D,3),(A,1),(F,3),(B,2),(C,1)}習(xí)題解答《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章35習(xí)題4-13《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章36優(yōu)先隊列類PriorityQueue<TextendsComparable<T>>//優(yōu)先隊列類（升或降），最終類，實現(xiàn)隊列接口，T是元素類型publicfinalclassPriorityQueue<TextendsComparable<?superT>>implementsQueue<T>{privateSortedCirDoublyList<T>list;//排序循環(huán)雙鏈表

privatebooleanasc;

//asc指定升序（true）或降序

publicPriorityQueue(booleanasc)//構(gòu)造空隊列publicPriorityQueue()//構(gòu)造空隊列，默認(rèn)升序

publicbooleanisEmpty();//判空publicbooleanadd(Tx);//x入隊publicTpeek();//返回隊頭，沒有刪除publicTpoll();//出隊，返回隊頭}《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章37【例4.4】進程按優(yōu)先級調(diào)度管理//進程類publicclassProcessimplementsComparable<Process>{privateStringname;//進程名

privateintpriority; //優(yōu)先級

publicProcess(Stringname,intpriority)publicProcess(Stringname)

publicStringtoString()publicintcompareTo(Processp)}《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章38遞歸定義遞歸算法f(n)=n×f(n-1)【思考題4-4】publicstaticintfactorial(intn) //求階乘n!，遞歸方法4.3遞歸《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章39【思考題4-4】求階乘n!publicstaticintfactorial(intn)//遞歸方法{if(n<0)//拋出無效參數(shù)異常

thrownewIllegalArgumentException("n="+n);

if(n==0||n==1)//邊界條件，遞歸結(jié)束條件

return1;returnn*factorial(n-1);//遞歸調(diào)用，遞推通式}《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章40【例4.5】求Fibonacci序列?！稊?shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章41打印數(shù)字塔publicstaticvoidline(inti){if(i<10)line(i+1);System.out.print(String.format("%3d",i));}執(zhí)行l(wèi)ine(1)結(jié)果？輸出10987654321《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章42習(xí)題解答例4.1打印數(shù)字塔

112112321123432112345432112345654321123456765432112345678765432112345678987654321《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章43【例4.6】計算算術(shù)表達(dá)式的值，遞歸算法?！此阈g(shù)表達(dá)式〉∷＝〈項〉｜〈項〉＋〈項〉｜〈項〉－〈項〉〈項〉∷＝〈因子〉｜〈因子〉×〈因子〉｜〈因子〉／〈因子〉｜ 〈因子〉%〈因子〉〈因子〉∷＝〈常數(shù)〉｜（〈算術(shù)表達(dá)式〉）〈整數(shù)〉∷＝〈數(shù)字〉｜＋〈數(shù)字〉｜－〈數(shù)字〉｜〈整數(shù)〉〈數(shù)字〉〈數(shù)字〉∷＝0｜1｜2｜3｜4｜5｜6｜7｜8｜9《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章44算術(shù)表達(dá)式語法圖《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章45算術(shù)表達(dá)式類ArithmeticExpression//算術(shù)表達(dá)式（整數(shù)、不包括位運算）publicclassArithmeticExpression{privateStringinfix;//中綴算術(shù)表達(dá)式

privateintindex;//當(dāng)前字符序號

publicArithmeticExpression(Stringinfix)publicintintValue()//計算表達(dá)式，返回整數(shù)

privateintterm()//計算〈項〉privateintfactor()//計算〈因子〉

privateintconstant()//計算〈常數(shù)〉}《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章463.單鏈表的遞歸算法（1）遍歷單鏈表的遞歸算法publicStringtoString(){return"("+this.toString(this.head.next)+")";}privateStringtoString(Node<T>p)//遞歸算法{if(p==null)return"";//遞歸結(jié)束條件Stringstr=p.data.toString();if(p.next!=null)str+=",";returnstr+toString(p.next);//遞歸調(diào)用}《數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）》第4章47（2）構(gòu)造單鏈表的遞歸算法publicSinglyList(T[]values){this();//創(chuàng)建空單鏈表

this.head.next=create(values,0);}privateNode<T>create(T[]values,inti)//遞歸算法{Node<T>p=null;if(i<values.length)