棧與隊(duì)列(java版)

1、第三章第三章 棧與隊(duì)列棧與隊(duì)列第三章第三章 棧棧 與與 隊(duì)隊(duì) 列列3.2 隊(duì)列隊(duì)列3.1 棧棧3.4 棧與隊(duì)列的綜合應(yīng)用舉例棧與隊(duì)列的綜合應(yīng)用舉例3.3 棧與隊(duì)列的比較棧與隊(duì)列的比較第三章第三章 棧棧 與與 隊(duì)隊(duì) 列列重點(diǎn)：重點(diǎn)：u棧、隊(duì)列的特點(diǎn)；棧、隊(duì)列的特點(diǎn)；u棧、隊(duì)列基本操作的實(shí)現(xiàn)算法棧、隊(duì)列基本操作的實(shí)現(xiàn)算法難點(diǎn)：難點(diǎn)：u棧、隊(duì)列的應(yīng)用棧、隊(duì)列的應(yīng)用第三章第三章 棧棧 與與 隊(duì)隊(duì) 列列 通常稱，棧和隊(duì)列是限定插入插入和刪除只能刪除只能在表的“端點(diǎn)端點(diǎn)”進(jìn)行的線性表。 線性表線性表 棧棧 隊(duì)列隊(duì)列 Insert(i, x) Insert(n, x) Insert(n, x) 0in De

2、lete(i) Delete(n-1) Delete(0) 0in-1 棧和隊(duì)列是兩種棧和隊(duì)列是兩種操作受限操作受限的的線性線性表表，是兩種常用的數(shù)據(jù)類型。，是兩種常用的數(shù)據(jù)類型。3.1 棧棧a0 a1 a2 an-1進(jìn)進(jìn)出出(2) 棧棧是是“后進(jìn)先出后進(jìn)先出”的線性表（的線性表（LIFO）或）或 “先先 進(jìn)后出進(jìn)后出”的線性表（的線性表（FILO）3.1 棧棧 如下圖所示的是鐵路調(diào)度站形象地如下圖所示的是鐵路調(diào)度站形象地表示棧的表示棧的“后進(jìn)先出后進(jìn)先出”特點(diǎn)。特點(diǎn)。3.1 棧棧 設(shè)有編號(hào)為設(shè)有編號(hào)為1 1，2 2，3 3，4 4的四輛的四輛列車，順序進(jìn)一個(gè)棧式結(jié)構(gòu)的站臺(tái)列車，順序進(jìn)一個(gè)棧式

3、結(jié)構(gòu)的站臺(tái)，具體寫出這四輛列車開(kāi)出車站的，具體寫出這四輛列車開(kāi)出車站的所有可能的順序。所有可能的順序。3.1 棧棧四輛車出站的所有可能順序?yàn)椋核妮v車出站的所有可能順序?yàn)椋?）2、1、3、4；7）2、1、4、3； 8）2、3、4、1；9）2、3、1、4 ； 10）2、4、3、1；14）4、3、2、1。1）1、2、3、4； 2）1、2、4、3；3）1、3、2、4； 4）1、3、4、2；5）1、4、3、2； 11）3、2、1、4； 12）3、2、4、1；13）3、4、2、1； 3.1 棧棧 clear( )1 1）棧的置空操作：）棧的置空操作： isEmpty( )2 2）棧的判空操作：）棧的判空操

4、作： length( )3）求棧的長(zhǎng)度：）求棧的長(zhǎng)度：4）取棧頂元素操作：）取棧頂元素操作：5）入棧操作：）入棧操作：peek( )push( x )6）出棧操作：）出棧操作：pop( ) 1. 1.基本操作基本操作3.1 棧棧 2. 2.棧的抽象數(shù)據(jù)類型的棧的抽象數(shù)據(jù)類型的JavaJava接口描述接口描述public interface IStackpublic void clear();public boolean isEmpty();public int length();public Object peek();public void push(Object x) throws Exc

5、eption;public Object pop();實(shí)現(xiàn)此接口的方法有兩種實(shí)現(xiàn)此接口的方法有兩種: 順序棧順序棧鏈棧鏈棧3.1 棧棧1. 順序棧順序棧非空棧非空?？諚？諚0a1an-1 top=n stackElem maxSize-10 1 n-1 top=0stackElem maxSize-10 1 2 3.1 棧棧1. 順序棧順序棧思考思考?？諚l件?？諚l件?棧滿條件棧滿條件?棧的長(zhǎng)度棧的長(zhǎng)度?棧頂元素棧頂元素?如下問(wèn)題如何描述如下問(wèn)題如何描述?top=0top=stackElem.lengthtopstackElemtop-1a0a1an-1 top=n stackElem 0 1

6、 n-13.1 棧棧2.2.順序棧類的描述順序棧類的描述( (書書P71-P71-與與P33P33順序表類對(duì)照學(xué)習(xí)順序表類對(duì)照學(xué)習(xí)) )public class SqStack implements IStack private Object stackElem; private int top; /構(gòu)造一個(gè)容量為構(gòu)造一個(gè)容量為maxSize的空棧的空棧 public SqStack (int maxSize) / 棧置空棧置空 public void clear( ) stackElem = new ObjectmaxSize;top = 0;top= 0;3.1 棧棧2. 順序棧類的描述順

7、序棧類的描述( (見(jiàn)教材見(jiàn)教材P71)P71)public class SqStack implements IStack / / 棧棧判判空空public boolean isEmpty( ) / / 求棧數(shù)據(jù)元素個(gè)數(shù)函數(shù)求棧數(shù)據(jù)元素個(gè)數(shù)函數(shù) public int length( ) / / 取棧頂元素的函數(shù)取棧頂元素的函數(shù) public Object peek ( ) return top= 0;return top;if (!isEmpty() / / 棧非空棧非空return stackElemtop-1; / / 棧頂元素棧頂元素 elsereturn null;3.1 棧棧2. 順

8、序棧類的描述順序棧類的描述( (見(jiàn)教材見(jiàn)教材P71)P71)public class SqStack implements IStack / / 入棧操作的函數(shù)入棧操作的函數(shù)public void push( Object x) / / 出棧操作的函數(shù)出棧操作的函數(shù)public void pop ( ) / / 輸出函數(shù)輸出函數(shù)( (從棧頂?shù)綏５讖臈ｍ數(shù)綏５? )public void display () for (int i = top - 1; i = 0; i-)System.out.print(stackElemi.toString() + );3.1 棧棧3. 順序棧基本操作的實(shí)現(xiàn)

9、順序棧基本操作的實(shí)現(xiàn)1)順序棧的入棧操作順序棧的入棧操作 push (x)的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.1)插入元素插入元素x使其成為順序棧中新的棧使其成為順序棧中新的棧頂元素。頂元素。 x a0a1an-1 toptop3.1 棧棧 a.判斷順序棧是否為滿，若滿則拋出異常判斷順序棧是否為滿，若滿則拋出異常 b.若棧不滿，則若棧不滿，則將新元素將新元素x 壓入棧頂，并修壓入棧頂，并修正棧頂指針正棧頂指針 if (top = stackElem.length) throw new Exception(棧已滿棧已滿) 1)順序棧的入棧操作順序棧的入棧操作 push (x)的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法

10、3.1)statckElemtop+=xstatckElemtop=x;top=top+1;3.1 棧棧public void push (Object x) throws Exception /算法3.1結(jié)束if (top = stackElem.length) throw new Exception(棧已滿棧已滿);else stackElemtop+ = x; 1)順序棧的入棧操作順序棧的入棧操作 push (x)的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.1)時(shí)間復(fù)雜度為：時(shí)間復(fù)雜度為：O(1)3.1 棧棧3. 順序?；静僮鞯膶?shí)現(xiàn)順序?；静僮鞯膶?shí)現(xiàn)2)順序棧的出棧操作順序棧的出棧操作 pop (

11、 )的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.2) 將棧頂元素從棧中移去，并返回被移將棧頂元素從棧中移去，并返回被移去的棧頂元素值。去的棧頂元素值。 a0a1an-1 an-2top3.1 棧棧2)順序棧的出棧操作順序棧的出棧操作 pop() 的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.2) a）若?？?，則返回空值）若?？?，則返回空值 b)若棧不空，則移去棧頂元素并返回其值若棧不空，則移去棧頂元素并返回其值if (top=0) return null; a1a2an an-1top或或 if (isEmpty() return null;return stackElemtop;return stackElem-top;

12、top=top-1;3.1 棧棧public Object pop () throws Exception /算法3.2結(jié)束if (isEmpty() ) return null;elsereturn stackElem-top;2) 順序棧的出棧操作順序棧的出棧操作 pop ()的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.2)時(shí)間復(fù)雜度為：時(shí)間復(fù)雜度為：O(1)3.1 棧棧1. 鏈棧鏈棧 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧鏈棧，是運(yùn)算受限，是運(yùn)算受限的單鏈表，其插入和刪除操作僅限制在的單鏈表，其插入和刪除操作僅限制在鏈表的鏈表的表頭位置上表頭位置上進(jìn)行，故鏈棧沒(méi)有必要象單鏈表一進(jìn)行，故鏈棧沒(méi)有必

13、要象單鏈表一樣附加頭結(jié)點(diǎn)，樣附加頭結(jié)點(diǎn)，棧頂指針棧頂指針即為鏈表的即為鏈表的頭指針頭指針。 topa0an-1注意注意: : 鏈棧中鏈棧中指針的方向指針的方向an-2棧底棧底3.1 棧棧1. 鏈棧鏈棧思考思考?？諚l件棧空條件?棧的長(zhǎng)度棧的長(zhǎng)度?棧頂元素棧頂元素?如下問(wèn)題如何描述如下問(wèn)題如何描述?top=null需從棧頂開(kāi)始沿著需從棧頂開(kāi)始沿著nextnext指針依次對(duì)結(jié)點(diǎn)逐個(gè)進(jìn)指針依次對(duì)結(jié)點(diǎn)逐個(gè)進(jìn)行點(diǎn)數(shù)才能確定。行點(diǎn)數(shù)才能確定。top.getData( ) topa0an-1an-23.1 棧棧2. 鏈棧類的描述鏈棧類的描述( (書中書中P73-74)P73-74)Import cho2.No

14、de;public class LinkStack implements IStack private Node top; / 棧置空函數(shù)棧置空函數(shù) public void clear( ) / / 判判空函數(shù)空函數(shù)public boolean isEmpty( ) top= null;return top= null;3.1 棧棧2. 鏈棧類的描述鏈棧類的描述(書中書中P73-74)public class LinkStack implements IStack / / 求棧數(shù)據(jù)元素個(gè)數(shù)函數(shù)求棧數(shù)據(jù)元素個(gè)數(shù)函數(shù) public int length( ) / / 取棧頂元素的函數(shù)取棧頂元素的函

15、數(shù) public Object peek ( ) if (!isEmpty() / 棧非空棧非空 return top.getData( ); / 棧頂元素棧頂元素else return null;3.1 棧棧2. 鏈棧類的描述鏈棧類的描述(書中書中P73-74)public class LinkStack implements IStack / / 入棧操作的函數(shù)入棧操作的函數(shù)public void push( Object x) / / 出棧操作的函數(shù)出棧操作的函數(shù)public void pop ( ) / / 輸出函數(shù)輸出函數(shù)( (從棧頂?shù)綏５讖臈ｍ數(shù)綏５? )public void d

16、isplay () Node p=top;System.out.print(p.getData( ).tostring( )+ )p=p.getNext();while(p!=null) 3.1 棧棧03. 鏈?；静僮鞯膶?shí)現(xiàn)鏈?；静僮鞯膶?shí)現(xiàn)1) 求鏈棧的長(zhǎng)度操作求鏈棧的長(zhǎng)度操作 length ()的實(shí)現(xiàn)的實(shí)現(xiàn) 計(jì)算出鏈棧中所包含的數(shù)據(jù)元素的個(gè)計(jì)算出鏈棧中所包含的數(shù)據(jù)元素的個(gè)數(shù)并返回其值。數(shù)并返回其值。 與求單鏈表長(zhǎng)度的方法相同。與求單鏈表長(zhǎng)度的方法相同。 ppplength1 2 3211830754256topp4p5p6p3.1 棧棧public int length ( ) /算法3

17、.3結(jié)束Node p = top; int length = 0;時(shí)間復(fù)雜度為：時(shí)間復(fù)雜度為：O(n)1) 求鏈棧的長(zhǎng)度操作求鏈棧的長(zhǎng)度操作 length ()的實(shí)現(xiàn)的實(shí)現(xiàn)(算法算法 3.3)while (p != null) p = p.getNext(); +length; 3.1 棧棧3. 鏈?；静僮鞯膶?shí)現(xiàn)鏈?；静僮鞯膶?shí)現(xiàn)2) 鏈棧的入棧操作鏈棧的入棧操作 push (x )的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.4) 將數(shù)據(jù)域值為將數(shù)據(jù)域值為x x的新結(jié)點(diǎn)插入到鏈棧的棧頂，的新結(jié)點(diǎn)插入到鏈棧的棧頂，使其成為新的棧頂元素。使其成為新的棧頂元素。 x1830754256toptopNode p

18、= new Node(x); p.setNext(top); top = p; p3.1 棧棧public void push (object x) /算法3.4結(jié)束Node p = new Node(x); 2) 鏈棧的入棧操作鏈棧的入棧操作 push (x )的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.4)時(shí)間復(fù)雜度為：時(shí)間復(fù)雜度為：O(1)p.setNext(top); top = p; 3.1 棧棧3. 鏈?；静僮鞯膶?shí)現(xiàn)鏈?；静僮鞯膶?shí)現(xiàn)3) 鏈棧的出棧操作鏈棧的出棧操作 pop ( )的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.5) 將首結(jié)點(diǎn)（或棧頂結(jié)點(diǎn)）從鏈棧中移去，將首結(jié)點(diǎn)（或棧頂結(jié)點(diǎn)）從鏈棧中移去，并返

19、回該結(jié)點(diǎn)的數(shù)據(jù)域的值。并返回該結(jié)點(diǎn)的數(shù)據(jù)域的值。Node p = top; top=top.getNext( ) return (p.getData( ); 211830754256topp3.1 棧棧public Object pop ( ) /算法3.5結(jié)束3) 鏈棧的出棧操作鏈棧的出棧操作 pop ( )的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.5)時(shí)間復(fù)雜度為：時(shí)間復(fù)雜度為：O(1)Node p = top; top=top.getNext( ) return (p.getData( ); if (isEmpty() return null;else3.1 棧棧3.1.5 3.1.5 棧的應(yīng)用棧的

20、應(yīng)用例例1. 分隔符匹配問(wèn)題分隔符匹配問(wèn)題例例2. 大數(shù)加法問(wèn)題大數(shù)加法問(wèn)題例例3. 表達(dá)式求值問(wèn)題表達(dá)式求值問(wèn)題例例4. 棧與遞歸問(wèn)題棧與遞歸問(wèn)題3.1 棧?！纠? 1】分隔符匹配問(wèn)題分隔符匹配問(wèn)題- -問(wèn)題分析問(wèn)題分析 假設(shè)在表達(dá)式中（）或（ /* */）等為正確正確的格式，（ ）或（）)或（ ）均為不正確不正確的格式。則則 檢驗(yàn)分隔符是否匹配檢驗(yàn)分隔符是否匹配的方法可用的方法可用“期待的急迫程度期待的急迫程度”這個(gè)概念來(lái)描述。這個(gè)概念來(lái)描述。 Java Java程序中分隔符有圓、方、花括程序中分隔符有圓、方、花括號(hào)和注釋符號(hào)和注釋符“/ /* *”和和“* */ /”。3.1 棧棧分析

21、可能出現(xiàn)的分析可能出現(xiàn)的不匹配不匹配的情況的情況:l到來(lái)的右分隔符到來(lái)的右分隔符并非是所并非是所“期待期待”的；的；例如：考慮下列括號(hào)序列：例如：考慮下列括號(hào)序列：（ ）或或（ ）)或或（ ）1 2 3 4 1 2 3 4 5 6 1 2 3 4 5l到來(lái)的是到來(lái)的是“不速之客不速之客”；l直到結(jié)束，也沒(méi)有到來(lái)直到結(jié)束，也沒(méi)有到來(lái)所所“期待期待”的括的括弧?；?。【例例1 1】分隔符匹配問(wèn)題分隔符匹配問(wèn)題- -問(wèn)題分析問(wèn)題分析3.1 棧?！纠? 1】分隔符匹配問(wèn)題分隔符匹配問(wèn)題- -問(wèn)題分析問(wèn)題分析這這三種情況三種情況對(duì)應(yīng)到棧的操作即為：對(duì)應(yīng)到棧的操作即為： 1 1和棧頂?shù)淖蠓指舴幌嗥ヅ洌缓?/p>

22、棧頂?shù)淖蠓指舴幌嗥ヅ洌?2 2棧中并沒(méi)有左分隔符等在那里；棧中并沒(méi)有左分隔符等在那里； 3 3棧中還有左分隔符沒(méi)有等到和它棧中還有左分隔符沒(méi)有等到和它相匹配的右括弧。相匹配的右括弧。3.1 棧棧1）凡出現(xiàn)）凡出現(xiàn)左括弧左括弧，則，則進(jìn)棧進(jìn)棧；2）凡出現(xiàn)）凡出現(xiàn)右括弧右括弧，首先檢查棧是否空，首先檢查棧是否空 若若?？諚？?，則表明該，則表明該“右括弧右括弧”多余多余， 否則和棧頂元素比較，否則和棧頂元素比較， 若若相匹配相匹配，則，則“左括弧出棧左括弧出?！?， 否則否則表明表明不匹配不匹配。3）表達(dá)式檢驗(yàn)）表達(dá)式檢驗(yàn)結(jié)束結(jié)束時(shí)，時(shí)， 若若棧空?？眨瑒t表明表達(dá)式中，則表明表達(dá)式中匹配正確匹配正

23、確， 否則否則表明表明“左括弧左括弧”有余有余。【例例1 1】分隔符匹配問(wèn)題分隔符匹配問(wèn)題- -問(wèn)題分析問(wèn)題分析3.1 棧?！纠? 1】分隔符匹配問(wèn)題分隔符匹配問(wèn)題- -程序代碼（程序代碼（P77-78P77-78）public class Example3_1 private final int LEFT = 0;/ 記錄記錄左左分隔符分隔符private final int RIGHT = 1;/ 記錄記錄右右分隔符分隔符private final int OTHER = 2;/ 記錄其他字符記錄其他字符Import java.util.Scanner;public int verify

24、Flag(String str) if (.equals(str) | .equals(str) | .equals(str)| /*.equals(str) / 左分隔符左分隔符 return LEFT; else if ().equals(str) | .equals(str) | .equals(str)| */.equals(str) / 右分隔符右分隔符 return RIGHT; else / 其它的字符其它的字符 return OTHER;3.1 棧棧public class Example3_1 / 檢驗(yàn)左分隔符檢驗(yàn)左分隔符str1和右分隔符和右分隔符str2是否匹配是否匹配p

25、ublic boolean matches(String str1, String str2) if (.equals(str1) & ).equals(str2)| (.equals(str1) & .equals(str2)| (.equals(str1) & .equals(str2)| (/*.equals(str1) & */.equals(str2)return true; else return false; 【例例1 1】分隔符匹配問(wèn)題分隔符匹配問(wèn)題- -程序代碼（程序代碼（P77-78P77-78）3.1 棧棧public class Exam

26、ple3_1 / 檢驗(yàn)串中分隔符是否匹配檢驗(yàn)串中分隔符是否匹配private boolean isLegal(String str) throws Exception if (!.equals(str) & str != null) SqStack S = new SqStack(100); int length = str.length(); for (int i = 0; i # 3 * (7-2) 4 *( 7-2) 5 37 *( -2) -( 6 37 *(- 2) 7 372 *(- ) 遇） 8 372- *( )遇( 9 372- * 10 372-* 結(jié)束 動(dòng)畫動(dòng)畫3

27、-3-73.1 棧棧【例例3 3】表達(dá)式求值表達(dá)式求值問(wèn)題分析問(wèn)題分析先找運(yùn)算符，先找運(yùn)算符， 再找操作數(shù)再找操作數(shù) 例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) f動(dòng)畫動(dòng)畫3-3-6a b+(c-d/e) f3.1 棧?！纠? 3】表達(dá)式求值表達(dá)式求值問(wèn)題分析問(wèn)題分析1) 設(shè)立一個(gè)設(shè)立一個(gè)操作數(shù)棧；操作數(shù)棧；2) 從左到右依次讀入后綴表達(dá)式中的字符從左到右依次讀入后綴表達(dá)式中的字符:若若當(dāng)前字符當(dāng)前字符是操作數(shù)是操作數(shù)，則壓入操作數(shù)棧。，則壓入操作數(shù)棧。后綴式求值的操作步驟為：后綴式求值的操作步驟為：若若當(dāng)前字符當(dāng)前字符是運(yùn)算符是運(yùn)算符，則從棧頂彈出兩，

28、則從棧頂彈出兩個(gè)操作數(shù)參與運(yùn)算，并將運(yùn)算結(jié)果壓入操個(gè)操作數(shù)參與運(yùn)算，并將運(yùn)算結(jié)果壓入操作數(shù)棧內(nèi)。作數(shù)棧內(nèi)。動(dòng)畫動(dòng)畫3-3-63.1 棧?！纠? 3】表達(dá)式求值表達(dá)式求值程序代碼程序代碼Example3_3.javaExample3_3.java( (書書P84-85)P84-85)3.1 棧?！纠? 4】棧與遞歸問(wèn)題棧與遞歸問(wèn)題 在程序設(shè)計(jì)中，經(jīng)常會(huì)碰到多個(gè)函在程序設(shè)計(jì)中，經(jīng)常會(huì)碰到多個(gè)函數(shù)的嵌套調(diào)用。和匯編程序設(shè)計(jì)中主程數(shù)的嵌套調(diào)用。和匯編程序設(shè)計(jì)中主程序和子程序之間的鏈接和信息交換相類序和子程序之間的鏈接和信息交換相類似，在高級(jí)語(yǔ)言編制的程序中，調(diào)用函似，在高級(jí)語(yǔ)言編制的程序中，調(diào)用函

29、數(shù)和被調(diào)用函數(shù)之間的鏈接和信息交換數(shù)和被調(diào)用函數(shù)之間的鏈接和信息交換也是由編譯程序通過(guò)也是由編譯程序通過(guò)棧棧來(lái)實(shí)施的。來(lái)實(shí)施的。3.1 棧?！纠? 4】棧與遞歸問(wèn)題棧與遞歸問(wèn)題 當(dāng)在一個(gè)函數(shù)的運(yùn)行期間當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一調(diào)用另一個(gè)函數(shù)個(gè)函數(shù)時(shí)，在時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前運(yùn)行該被調(diào)用函數(shù)之前，需先完成三項(xiàng)任務(wù)：需先完成三項(xiàng)任務(wù)：3.1 棧棧【例例4 4】棧與遞歸問(wèn)題棧與遞歸問(wèn)題3.1 棧?！纠? 4】棧與遞歸問(wèn)題棧與遞歸問(wèn)題多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是：多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是：此時(shí)的內(nèi)存管理實(shí)行此時(shí)的內(nèi)存管理實(shí)行“棧式管理?xiàng)Ｊ焦芾怼焙笳{(diào)用先返回后調(diào)用先返回 ！例如：例如：void

30、main( ) void a( ) void b( ) a( ); b( ); /main / a / b函數(shù)函數(shù)a的數(shù)據(jù)區(qū)的數(shù)據(jù)區(qū)函數(shù)函數(shù)b的數(shù)據(jù)區(qū)的數(shù)據(jù)區(qū)Main的數(shù)據(jù)區(qū)的數(shù)據(jù)區(qū)3.1 棧?！纠? 4】棧與遞歸問(wèn)題棧與遞歸問(wèn)題遞歸工作棧：遞歸工作棧：遞歸過(guò)程執(zhí)行過(guò)程中占用的遞歸過(guò)程執(zhí)行過(guò)程中占用的 數(shù)據(jù)區(qū)。數(shù)據(jù)區(qū)。遞歸工作記錄：遞歸工作記錄：每一層的遞歸參數(shù)合成每一層的遞歸參數(shù)合成 一個(gè)記錄。一個(gè)記錄。當(dāng)前活動(dòng)記錄：當(dāng)前活動(dòng)記錄：棧頂記錄指示當(dāng)前層的棧頂記錄指示當(dāng)前層的 執(zhí)行情況。執(zhí)行情況。當(dāng)前環(huán)境指針：當(dāng)前環(huán)境指針：遞歸工作棧的棧頂指針。遞歸工作棧的棧頂指針。 遞歸函數(shù)執(zhí)行的過(guò)程可視為

31、遞歸函數(shù)執(zhí)行的過(guò)程可視為同一函數(shù)同一函數(shù)進(jìn)進(jìn)行嵌套調(diào)用，例如：行嵌套調(diào)用，例如：3.1 棧?！纠? 4】棧與遞歸問(wèn)題棧與遞歸問(wèn)題漢諾塔問(wèn)題描述漢諾塔問(wèn)題描述 n n階漢諾塔問(wèn)題：階漢諾塔問(wèn)題：假設(shè)有三個(gè)分別命名為假設(shè)有三個(gè)分別命名為X X，Y Y和和Z Z的塔座，在塔座的塔座，在塔座X X上插有上插有n n個(gè)直徑大小各個(gè)直徑大小各不相同，且從小到大編號(hào)為不相同，且從小到大編號(hào)為1 1、2 2、n n的圓的圓盤?，F(xiàn)要求將塔座盤?，F(xiàn)要求將塔座X X上的上的n n個(gè)圓盤借助塔座個(gè)圓盤借助塔座Y Y移至移至塔座塔座Z Z上，并仍按同樣順序疊排。圓盤移動(dòng)時(shí)必上，并仍按同樣順序疊排。圓盤移動(dòng)時(shí)必須遵循下

32、列規(guī)則：須遵循下列規(guī)則： 每次只能移動(dòng)一個(gè)圓盤；每次只能移動(dòng)一個(gè)圓盤； 圓盤可以插在圓盤可以插在X X，Y Y和和Z Z中的任何一個(gè)塔中的任何一個(gè)塔座上；座上； 任何時(shí)刻都不能將一個(gè)較大的圓盤壓在任何時(shí)刻都不能將一個(gè)較大的圓盤壓在較小的圓盤之上。較小的圓盤之上。3.1 棧棧【例例4 4】棧與遞歸問(wèn)題棧與遞歸問(wèn)題漢諾塔問(wèn)題漢諾塔問(wèn)題public void hanoi (int n, char x, char y, char z)/ 將塔座x上按直徑由小到大且至上而下編號(hào)為1至n的n個(gè)圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。1 2 if (n=1)3 move(x, 1, z); / 將編號(hào)為的

33、圓盤從x移到z4 else 5 hanoi(n-1, x, z, y); / 將x上編號(hào)為至n-1的 /圓盤移到y(tǒng), z作輔助塔6 move(x, n, z); / 將編號(hào)為n的圓盤從x移到z7 hanoi(n-1, y, x, z); / 將y上編號(hào)為至n-1的 /圓盤移到z, x作輔助塔8 9 3.1 棧棧【例例4 4】棧與遞歸問(wèn)題棧與遞歸問(wèn)題漢諾塔問(wèn)題漢諾塔問(wèn)題public void hanoi (int n, char x, char y, char z) 1 2 if (n=1)3 move(x, 1, z); 4 else 5 hanoi(n-1, x, z, y); 6 move

34、(x, n, z); 7 hanoi(n-1, y, x, z); 8 9 3.1 棧?！纠?】漢諾塔問(wèn)題漢諾塔問(wèn)題程序代碼程序代碼Example3_4.javaExample3_4.java( (書書P86-87)P86-87)3.2 隊(duì)列隊(duì)列隊(duì)列隊(duì)列是只允許在表的一端進(jìn)行插入，而在表是只允許在表的一端進(jìn)行插入，而在表 的另一端進(jìn)行刪除操作的一種的另一端進(jìn)行刪除操作的一種特殊線性表特殊線性表。 允許插入的一端稱為允許插入的一端稱為“隊(duì)尾隊(duì)尾”，允許刪除的，允許刪除的一一 端稱為端稱為“隊(duì)首隊(duì)首”。(2) 棧棧是是“先進(jìn)先出先進(jìn)先出”的線性表（的線性表（FIFO）或）或 “后進(jìn)后出后進(jìn)后出”

35、的線性表（的線性表（LILO）a0 a1 a2 an-1隊(duì)首隊(duì)首隊(duì)尾隊(duì)尾入隊(duì)入隊(duì)出隊(duì)出隊(duì)3.2 隊(duì)列隊(duì)列3.2.2 3.2.2 隊(duì)列的抽象數(shù)據(jù)類型描述隊(duì)列的抽象數(shù)據(jù)類型描述 clear( )1 1）隊(duì)列的置空操作：）隊(duì)列的置空操作： isEmpty( )2 2）隊(duì)列的判空操作：）隊(duì)列的判空操作： length( )3）求隊(duì)列的長(zhǎng)度：）求隊(duì)列的長(zhǎng)度：4）取隊(duì)首元素操作：）取隊(duì)首元素操作：5）入隊(duì)操作：）入隊(duì)操作：peek( )offer( x )6）出隊(duì)操作：）出隊(duì)操作：poll ( ) 1. 1.基本操作基本操作3.2 隊(duì)列隊(duì)列 2. 2.隊(duì)列的抽象數(shù)據(jù)類型的隊(duì)列的抽象數(shù)據(jù)類型的JavaJav

36、a接口描述接口描述public interface IQueuepublic void clear();public boolean isEmpty();public int length();public Object peek();public void offer(Object x) throws Exception;public Object popll();實(shí)現(xiàn)此接口的方法有兩種實(shí)現(xiàn)此接口的方法有兩種: 順序隊(duì)列順序隊(duì)列鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列3.2 隊(duì)列隊(duì)列1. 順序隊(duì)列順序隊(duì)列非空隊(duì)列非空隊(duì)列空隊(duì)列空隊(duì)列a0a1an-1 rear(隊(duì)尾指針) maxSize-1queueElemfron

37、t(隊(duì)首指針)0 1 n-1frontstackElemrear maxSize-10 1 2 3.2 隊(duì)列隊(duì)列1. 順序隊(duì)列順序隊(duì)列思考思考隊(duì)空條件隊(duì)空條件?隊(duì)列滿條件隊(duì)列滿條件?如下問(wèn)題如何描述如下問(wèn)題如何描述?front=rearrear=queueElem.length入隊(duì)入隊(duì)offer(x): queueElemrear+=x;出隊(duì)出隊(duì)poll ( ): return queueElem front+;隊(duì)首元素隊(duì)首元素?queueElemfront隊(duì)尾元素隊(duì)尾元素?queueElemrear-13.2 隊(duì)列隊(duì)列3.2.3 3.2.3 順序棧及其基本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)1

38、. 順序隊(duì)列順序隊(duì)列 序號(hào)值：序號(hào)值：0 1 2 3 4 5a0a1a3a3a4假溢出假溢出現(xiàn)象現(xiàn)象maxSize=6a5front front front front frontrearrear3.2 隊(duì)列隊(duì)列3.2.3 3.2.3 順序棧及其基本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)2. 循環(huán)順序隊(duì)列循環(huán)順序隊(duì)列 將順序隊(duì)列看成是首尾相聯(lián)的隊(duì)列。將順序隊(duì)列看成是首尾相聯(lián)的隊(duì)列。動(dòng)畫動(dòng)畫3-3-133.2 隊(duì)列隊(duì)列3.2.3 3.2.3 順序棧及其基本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)2. 循環(huán)順序隊(duì)列循環(huán)順序隊(duì)列假設(shè)：假設(shè)：maxSize=6循環(huán)隊(duì)空條件：循環(huán)隊(duì)空條件：循環(huán)隊(duì)滿條件：循環(huán)隊(duì)滿條

39、件：front=rearfront=rear隊(duì)空與隊(duì)滿的條件相同隊(duì)空與隊(duì)滿的條件相同, ,無(wú)法判斷無(wú)法判斷, ,怎么辦？怎么辦？054321 frontreara0a1a2a3a4a53.2 隊(duì)列隊(duì)列3.2.3 3.2.3 順序棧及其基本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)2. 循環(huán)順序隊(duì)列循環(huán)順序隊(duì)列 1. 1.設(shè)一個(gè)標(biāo)志變量設(shè)一個(gè)標(biāo)志變量flagflag并置初值為并置初值為0,0, 每當(dāng)入隊(duì)操作成功后就置每當(dāng)入隊(duì)操作成功后就置flag=1flag=1；每當(dāng)；每當(dāng)出隊(duì)操作成功后就置出隊(duì)操作成功后就置flag=0 flag=0 。循環(huán)隊(duì)空條件：循環(huán)隊(duì)空條件：循環(huán)隊(duì)滿條件：循環(huán)隊(duì)滿條件：front

40、=rear&flag=0front=rear&flag=13.2 隊(duì)列隊(duì)列3.2.3 3.2.3 順序棧及其基本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)2. 循環(huán)順序隊(duì)列循環(huán)順序隊(duì)列 2. 2.設(shè)置一個(gè)計(jì)數(shù)變量設(shè)置一個(gè)計(jì)數(shù)變量numnum并置初值為并置初值為0,0,每當(dāng)入隊(duì)操作成功后每當(dāng)入隊(duì)操作成功后numnum加加1 1；每當(dāng)出；每當(dāng)出隊(duì)操作成功后隊(duì)操作成功后numnum減減1 1。循環(huán)隊(duì)空條件：循環(huán)隊(duì)空條件：循環(huán)隊(duì)滿條件：循環(huán)隊(duì)滿條件：num=0或或front=rear& num=0num=queueElem.length或或front=rear&num03.2

41、隊(duì)列隊(duì)列3.2.3 3.2.3 順序棧及其基本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)2. 循環(huán)順序隊(duì)列循環(huán)順序隊(duì)列3. 3. 少用一個(gè)元素空間：如下圖少用一個(gè)元素空間：如下圖循環(huán)隊(duì)空條件：循環(huán)隊(duì)空條件：循環(huán)隊(duì)滿條件：循環(huán)隊(duì)滿條件：front=rear（rear+1）% queueElem.length = =front054321 frontreara1a2a3a4a5空空3.2 隊(duì)列隊(duì)列3. 循環(huán)順序隊(duì)列類的描述循環(huán)順序隊(duì)列類的描述( (書中書中P91)P91)public class CircleSqQueue implements IQueue private Object queueEle

42、m; private int front; private int rear; /構(gòu)造一個(gè)容量為構(gòu)造一個(gè)容量為maxSize的空循環(huán)隊(duì)列函數(shù)的空循環(huán)隊(duì)列函數(shù) public CircleSqQueue (int maxSize) / 隊(duì)列置空函數(shù)隊(duì)列置空函數(shù) public void clear( ) queueElem = new ObjectmaxSize;front=rear = 0; front=rear= 0; 3.2 隊(duì)列隊(duì)列3. 循環(huán)順序隊(duì)列類的描述循環(huán)順序隊(duì)列類的描述( (見(jiàn)書見(jiàn)書P91)P91)public class CircleSqQueue implements IQueu

43、e public boolean isEmpty( ) / 判判空函數(shù)空函數(shù)public int length( ) / / 求隊(duì)列當(dāng)前長(zhǎng)度函數(shù)求隊(duì)列當(dāng)前長(zhǎng)度函數(shù) public Object peek ( ) / 讀取隊(duì)首元素的函數(shù)讀取隊(duì)首元素的函數(shù) return front=rear;return (rear-front+queueElem.length)%queueElem.length);if (front=rear) / 隊(duì)列為隊(duì)列為空空elsereturn null ; return queueElemfront; / 返回隊(duì)首返回隊(duì)首元素元素3.2 隊(duì)列隊(duì)列public class

44、 CircleSqQueue implements IQueue /循環(huán)順序隊(duì)列類的描述結(jié)束循環(huán)順序隊(duì)列類的描述結(jié)束/ / 入隊(duì)操作的函數(shù)入隊(duì)操作的函數(shù)public void offer( Object x) / 出隊(duì)操作的函數(shù)出隊(duì)操作的函數(shù)public void poll ( ) / / 輸出函數(shù)輸出函數(shù)( (從隊(duì)首到隊(duì)尾從隊(duì)首到隊(duì)尾) )public void display () 3. 循環(huán)順序隊(duì)列類的描述循環(huán)順序隊(duì)列類的描述( (見(jiàn)書見(jiàn)書P91)P91)if (!isEmpty() else for (int i = front; i != rear; i = (i + 1) % qu

45、eueElem.length) System.out.print(queueElemi.toString() + );System.out.println(此隊(duì)列為空此隊(duì)列為空);3.2 隊(duì)列隊(duì)列4. 循環(huán)順序隊(duì)列基本操作的實(shí)現(xiàn)循環(huán)順序隊(duì)列基本操作的實(shí)現(xiàn)1)循環(huán)順序隊(duì)列的入隊(duì)操作循環(huán)順序隊(duì)列的入隊(duì)操作 offer (x)的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.6) 將新元素將新元素x插入到一個(gè)循環(huán)隊(duì)插入到一個(gè)循環(huán)隊(duì)列的隊(duì)尾。列的隊(duì)尾。rear054321fronta3a4a5x3.2 隊(duì)列隊(duì)列 1）若）若，則拋出異常后結(jié)束操作；，則拋出異常后結(jié)束操作； 2）若隊(duì)非滿，則將）若隊(duì)非滿，則將x進(jìn)隊(duì)，尾指針加

46、進(jìn)隊(duì)，尾指針加1queueElemrear = x; /x入隊(duì)入隊(duì)if (rear+1)%queueElem.length=front) throw new Exception(隊(duì)列已滿隊(duì)列已滿);4. 循環(huán)順序隊(duì)列基本操作的實(shí)現(xiàn)循環(huán)順序隊(duì)列基本操作的實(shí)現(xiàn)1)循環(huán)順序隊(duì)列的入隊(duì)操作循環(huán)順序隊(duì)列的入隊(duì)操作 offer (x)的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.6)rear=(rear+1)% queueElem.length;3.2 隊(duì)列隊(duì)列public void offer (Object x) throws Exception /算法3.6結(jié)束if (rear+1)%queueElem.lengt

47、h=front) throw new Exception(“隊(duì)列已滿隊(duì)列已滿);else queueElemrear = x; rear=(rear+1)% queueElem.length; 時(shí)間復(fù)雜度為：時(shí)間復(fù)雜度為：O(1)4. 循環(huán)順序隊(duì)列基本操作的實(shí)現(xiàn)循環(huán)順序隊(duì)列基本操作的實(shí)現(xiàn)1)循環(huán)順序隊(duì)列的入隊(duì)操作循環(huán)順序隊(duì)列的入隊(duì)操作 offer (x)的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.6)3.2 隊(duì)列隊(duì)列2)循環(huán)順序隊(duì)列的出隊(duì)操作循環(huán)順序隊(duì)列的出隊(duì)操作poll( )的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.7)4. 循環(huán)順序隊(duì)列基本操作的實(shí)現(xiàn)循環(huán)順序隊(duì)列基本操作的實(shí)現(xiàn)將隊(duì)首元素刪除，并返回其值。將隊(duì)首元素刪

48、除，并返回其值。a5front021054reara6a73.2 隊(duì)列隊(duì)列 1）若）若，則返回空值；，則返回空值； 2）若隊(duì)非空，則返回隊(duì)首元素且首指針加）若隊(duì)非空，則返回隊(duì)首元素且首指針加1Object t=queueElemfront /讀取隊(duì)首元素讀取隊(duì)首元素if (front=rear) return null;4. 循環(huán)順序隊(duì)列基本操作的實(shí)現(xiàn)循環(huán)順序隊(duì)列基本操作的實(shí)現(xiàn)front=(front+1)% queueElem.length;2)循環(huán)順序隊(duì)列的出隊(duì)操作循環(huán)順序隊(duì)列的出隊(duì)操作poll( )的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.7)return t;3.2 隊(duì)列隊(duì)列public Obje

49、ct poll ( ) /算法3.7結(jié)束if (front = rear) return null;else Object t = queueElemfront; front = (front + 1) % queueElem.length; return t; 時(shí)間復(fù)雜度為：時(shí)間復(fù)雜度為：O(1)4. 循環(huán)順序隊(duì)列基本操作的實(shí)現(xiàn)循環(huán)順序隊(duì)列基本操作的實(shí)現(xiàn)2)循環(huán)順序隊(duì)列的出隊(duì)操作循環(huán)順序隊(duì)列的出隊(duì)操作poll( )的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.7)3.2 隊(duì)列隊(duì)列1. 鏈隊(duì)列鏈隊(duì)列 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列鏈隊(duì)列，其鏈?zhǔn)酱?，其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在此用儲(chǔ)結(jié)構(gòu)在此用不帶頭結(jié)點(diǎn)

50、不帶頭結(jié)點(diǎn)的單鏈表來(lái)實(shí)現(xiàn)的單鏈表來(lái)實(shí)現(xiàn). . frontan-1a0a1 rear隊(duì)首指針隊(duì)首指針隊(duì)尾指針隊(duì)尾指針3.2 隊(duì)列隊(duì)列1. 鏈隊(duì)列鏈隊(duì)列思考思考隊(duì)列空的條件隊(duì)列空的條件?隊(duì)列的長(zhǎng)度隊(duì)列的長(zhǎng)度?隊(duì)首元素隊(duì)首元素?如下問(wèn)題如何描述如下問(wèn)題如何描述?front=null需從隊(duì)首開(kāi)始沿著需從隊(duì)首開(kāi)始沿著nextnext指針依次對(duì)結(jié)點(diǎn)逐個(gè)進(jìn)指針依次對(duì)結(jié)點(diǎn)逐個(gè)進(jìn)行點(diǎn)數(shù)才能確定。行點(diǎn)數(shù)才能確定。front.getData( )隊(duì)尾元素隊(duì)尾元素?rear.getData( )3.2 隊(duì)列隊(duì)列2. 鏈隊(duì)列類的描述鏈隊(duì)列類的描述( (書中書中P93-94)P93-94)import cho2.Node

51、;public class LinkQueue implements IQueue private Node front; private Node rear; / 隊(duì)列置空函數(shù)隊(duì)列置空函數(shù) public void clear( ) / / 判判空函數(shù)空函數(shù)public boolean isEmpty( ) front=rear= null; return front= null;3.2 隊(duì)列隊(duì)列public class LinkQueue implements IQueue / / 求隊(duì)列長(zhǎng)度函數(shù)求隊(duì)列長(zhǎng)度函數(shù)public int length( ) 2. 鏈隊(duì)列類的描述鏈隊(duì)列類的描述( (

52、書中書中P93-94)P93-94)Node p = front;int length = 0;while (p !=null) p = p.getNext(); /指針下移指針下移 +length; /計(jì)數(shù)器加計(jì)數(shù)器加1 return length;3.2 隊(duì)列隊(duì)列public class LinkQueue implements IQueue / / 取隊(duì)首元素的函數(shù)取隊(duì)首元素的函數(shù) public Object peek ( ) 2. 鏈隊(duì)列類的描述鏈隊(duì)列類的描述( (書中書中P93-94)P93-94)if (!isEmpty() / 隊(duì)列隊(duì)列非空非空 elsereturn front.

53、getData( ); / 返回隊(duì)首返回隊(duì)首元素元素return null;3.2 隊(duì)列隊(duì)列public class LinkQueue implements IQueue / / 入隊(duì)操作的函數(shù)入隊(duì)操作的函數(shù)public void push( Object x) / / 出隊(duì)操作的函數(shù)出隊(duì)操作的函數(shù)public void pop ( ) / / 輸出函數(shù)輸出函數(shù)( (從隊(duì)首到隊(duì)尾從隊(duì)首到隊(duì)尾) )public void display () 2. 鏈隊(duì)列類的描述鏈隊(duì)列類的描述( (書中書中P93-94)P93-94)Node p=front;while( p!=null ) System.o

54、ut.print(p.getData( ).tostring( )+ )p=p.getNext();3.2 隊(duì)列隊(duì)列3. 鏈隊(duì)列基本操作的實(shí)現(xiàn)鏈隊(duì)列基本操作的實(shí)現(xiàn)1) 鏈隊(duì)列的入隊(duì)操作鏈隊(duì)列的入隊(duì)操作 offer(x )的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.8) 插入新元素插入新元素x x使其成為新的隊(duì)尾元素。使其成為新的隊(duì)尾元素。 1830754256frontrearNode p = new Node(x); rear.setNext(p); rear = p; rearxp a）產(chǎn)生新的結(jié)點(diǎn)）產(chǎn)生新的結(jié)點(diǎn)pb）將新結(jié)點(diǎn)插入鏈隊(duì)的尾部（修改鏈）將新結(jié)點(diǎn)插入鏈隊(duì)的尾部（修改鏈）隊(duì)非空時(shí)隊(duì)非空時(shí): :

55、隊(duì)空時(shí)隊(duì)空時(shí): :front=rear = p; 3.2 隊(duì)列隊(duì)列public void offer (object x) /算法3.8結(jié)束 Node p = new Node(x); if (front != null) / 隊(duì)列非空隊(duì)列非空 rear.setNext(p); rear = p; else front = rear = p; 時(shí)間復(fù)雜度為：時(shí)間復(fù)雜度為：O(1)3. 鏈隊(duì)列基本操作的實(shí)現(xiàn)鏈隊(duì)列基本操作的實(shí)現(xiàn)1) 鏈隊(duì)列的入隊(duì)操作鏈隊(duì)列的入隊(duì)操作 offer(x )的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.8)3.2 隊(duì)列隊(duì)列3. 鏈隊(duì)列基本操作的實(shí)現(xiàn)鏈隊(duì)列基本操作的實(shí)現(xiàn)2) 鏈隊(duì)列的出隊(duì)

56、操作鏈隊(duì)列的出隊(duì)操作 poll()的實(shí)現(xiàn)的實(shí)現(xiàn) 移去隊(duì)首元素并返回其值移去隊(duì)首元素并返回其值1830754256frontrearif (front=null) return null; Node p=front; front = front.getNext(); a）若隊(duì)列為空）若隊(duì)列為空,則返回空值則返回空值b）若隊(duì)列非空）若隊(duì)列非空,則移去隊(duì)首元素則移去隊(duì)首元素p3.2 隊(duì)列隊(duì)列3. 鏈隊(duì)列基本操作的實(shí)現(xiàn)鏈隊(duì)列基本操作的實(shí)現(xiàn)2) 鏈隊(duì)列的出隊(duì)操作鏈隊(duì)列的出隊(duì)操作 poll()的實(shí)現(xiàn)的實(shí)現(xiàn) 移去隊(duì)首元素并返回其值移去隊(duì)首元素并返回其值1830754256frontrearpc) 若刪除的是

57、隊(duì)尾元素，則修改隊(duì)尾指針若刪除的是隊(duì)尾元素，則修改隊(duì)尾指針if ( rear=p) rear=null;d) 返回隊(duì)尾元素值返回隊(duì)尾元素值return p.getData();3.2 隊(duì)列隊(duì)列public Objext poll( ) Node p = new Node(x); if (front != null) / 隊(duì)列非空隊(duì)列非空 Node p=front; front=front.getNext(); if (rear=p) rear=null; return p.getData(); else return null;時(shí)間復(fù)雜度為：時(shí)間復(fù)雜度為：O(1)3. 鏈隊(duì)列基本操作的實(shí)現(xiàn)鏈隊(duì)

58、列基本操作的實(shí)現(xiàn)2) 鏈隊(duì)列的出隊(duì)操作鏈隊(duì)列的出隊(duì)操作 poll()的實(shí)現(xiàn)的實(shí)現(xiàn)3.2 隊(duì)列隊(duì)列【例例 】編程實(shí)現(xiàn)求解的素?cái)?shù)環(huán)問(wèn)題編程實(shí)現(xiàn)求解的素?cái)?shù)環(huán)問(wèn)題3.2.5 3.2.5 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用【問(wèn)題描述】【問(wèn)題描述】將將1 1n n的的 n n個(gè)自然數(shù)排列成個(gè)自然數(shù)排列成環(huán)形，使得每相鄰兩數(shù)之和為素?cái)?shù)，從而構(gòu)成環(huán)形，使得每相鄰兩數(shù)之和為素?cái)?shù)，從而構(gòu)成一個(gè)素?cái)?shù)環(huán)。一個(gè)素?cái)?shù)環(huán)。【方法方法】 先引入順序表類先引入順序表類SqlistSqlist和鏈隊(duì)列類和鏈隊(duì)列類LinkQueueLinkQueue，再創(chuàng)建，再創(chuàng)建SqlistSqlist類的一個(gè)對(duì)象類的一個(gè)對(duì)象L L作作為順序表，用于存放素?cái)?shù)

59、環(huán)的數(shù)據(jù)元素；創(chuàng)建為順序表，用于存放素?cái)?shù)環(huán)的數(shù)據(jù)元素；創(chuàng)建LinkQueueLinkQueue類的一個(gè)對(duì)象類的一個(gè)對(duì)象Q Q，作為隊(duì)列用于存放，作為隊(duì)列用于存放還未加入到素?cái)?shù)環(huán)中的自然數(shù)。還未加入到素?cái)?shù)環(huán)中的自然數(shù)。3.2 隊(duì)列隊(duì)列【例例 】編程實(shí)現(xiàn)求解的素?cái)?shù)環(huán)問(wèn)題編程實(shí)現(xiàn)求解的素?cái)?shù)環(huán)問(wèn)題3.2.5 3.2.5 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用【問(wèn)題描述】【問(wèn)題描述】將將1 1n n的的 n n個(gè)自然數(shù)排列成個(gè)自然數(shù)排列成環(huán)形，使得每相鄰兩數(shù)之和為素?cái)?shù)，從而構(gòu)成環(huán)形，使得每相鄰兩數(shù)之和為素?cái)?shù)，從而構(gòu)成一個(gè)素?cái)?shù)環(huán)。一個(gè)素?cái)?shù)環(huán)?！痉椒ǚ椒ā?(2) (2) 初始化順序表初始化順序表L L和隊(duì)列和隊(duì)列Q: Q:

60、 將將1 1加入到加入到順序表順序表L L中，將中，將2 2n n的自然數(shù)全部加入到的自然數(shù)全部加入到Q Q隊(duì)列隊(duì)列中。中。3.2 隊(duì)列隊(duì)列【例例 】編程實(shí)現(xiàn)求解的素?cái)?shù)環(huán)問(wèn)題編程實(shí)現(xiàn)求解的素?cái)?shù)環(huán)問(wèn)題3.2.5 3.2.5 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用【問(wèn)題描述】【問(wèn)題描述】將將1 1n n的的 n n個(gè)自然數(shù)排列成個(gè)自然數(shù)排列成環(huán)形，使得每相鄰兩數(shù)之和為素?cái)?shù)，從而構(gòu)成環(huán)形，使得每相鄰兩數(shù)之和為素?cái)?shù)，從而構(gòu)成一個(gè)素?cái)?shù)環(huán)。一個(gè)素?cái)?shù)環(huán)?！痉椒ǚ椒ā?(3) (3) 將出隊(duì)的隊(duì)首元素將出隊(duì)的隊(duì)首元素p p與素?cái)?shù)環(huán)最后一與素?cái)?shù)環(huán)最后一個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素q q相加相加。 (a) (a)若兩數(shù)之和是素?cái)?shù)并且若兩數(shù)之和是素?cái)?shù)并且p p 不是隊(duì)列中不是隊(duì)列中的最后一個(gè)數(shù)據(jù)元素（或隊(duì)尾元素