棧與隊(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 棧棧3.1.1 3.1.1 棧的概念棧的概念a0 a1 a2 an-1進(jìn)進(jìn)出出(2) 棧棧是是“后進(jìn)先出后進(jìn)先出”的線性表（的線性表（LIFO）或）或 “先先 進(jìn)后出進(jìn)后出”的線性表（的線性表（FILO）3.1 棧棧3.1.1 3.1.1 棧的概念棧的概念 如下圖所示的是鐵路調(diào)度站形象地如下圖所示的是鐵路調(diào)度站形象地表示棧的表示棧的“后進(jìn)先出后進(jìn)先出”特點(diǎn)。特點(diǎn)。3.1 棧棧3.1.1 3.1.1 棧的概念棧

3、的概念 設(shè)有編號為設(shè)有編號為1 1，2 2，3 3，4 4的四輛的四輛列車，順序進(jìn)一個棧式結(jié)構(gòu)的站臺列車，順序進(jìn)一個棧式結(jié)構(gòu)的站臺，具體寫出這四輛列車開出車站的，具體寫出這四輛列車開出車站的所有可能的順序。所有可能的順序。3.1 棧棧3.1.1 3.1.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、

4、2、4、1；13）3、4、2、1； 3.1 棧棧3.1.2 3.1.2 棧的抽象數(shù)據(jù)類型描述棧的抽象數(shù)據(jù)類型描述 clear( )1 1）棧的置空操作：）棧的置空操作： isEmpty( )2 2）棧的判空操作：）棧的判空操作： length( )3）求棧的長度：）求棧的長度：4）取棧頂元素操作：）取棧頂元素操作：5）入棧操作：）入棧操作：peek( )push( x )6）出棧操作：）出棧操作：pop( ) 1. 1.基本操作基本操作3.1 棧棧3.1.2 3.1.2 棧的抽象數(shù)據(jù)類型描述棧的抽象數(shù)據(jù)類型描述 2. 2.棧的抽象數(shù)據(jù)類型的棧的抽象數(shù)據(jù)類型的JavaJava接口描述接口描述pu

5、blic interface IStackpublic void clear();public boolean isEmpty();public int length();public Object peek();public void push(Object x) throws Exception;public Object pop();實(shí)現(xiàn)此接口的方法有兩種實(shí)現(xiàn)此接口的方法有兩種: 順序棧順序棧鏈棧鏈棧3.1 棧棧3.1.3 3.1.3 順序棧及其基本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)1. 順序棧順序棧非空棧非空?？諚？諚0a1an-1 top=n stackElem maxSize-1

6、0 1 n-1 top=0stackElem maxSize-10 1 2 3.1 棧棧3.1.3 3.1.3 順序棧及其基本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)1. 順序棧順序棧思考思考?？諚l件棧空條件?棧滿條件棧滿條件?棧的長度棧的長度?棧頂元素棧頂元素?如下問題如何描述如下問題如何描述?top=0top=stackElem.lengthtopstackElemtop-1a0a1an-1 top=n stackElem 0 1 n-13.1 棧棧3.1.3 3.1.3 順序棧及其基本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)2.2.順序棧類的描述順序棧類的描述( (書書P71-P71-與與P33P3

7、3順序表類對照學(xué)習(xí)順序表類對照學(xué)習(xí)) )public class SqStack implements IStack private Object stackElem; private int top; /構(gòu)造一個容量為構(gòu)造一個容量為maxSize的空棧的空棧 public SqStack (int maxSize) / 棧置空棧置空 public void clear( ) stackElem = new ObjectmaxSize;top = 0;top= 0;3.1 棧棧2. 順序棧類的描述順序棧類的描述( (見教材見教材P71)P71)public class SqStack impl

8、ements IStack / / 棧棧判判空空public boolean isEmpty( ) / / 求棧數(shù)據(jù)元素個數(shù)函數(shù)求棧數(shù)據(jù)元素個數(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. 順序棧類的描述順序棧類的描述( (見教材見教材P71)P71)public class SqSta

9、ck 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)順序?；静僮鞯膶?shí)現(xiàn)1)順序棧的入棧操作順序棧的入棧操作 push (x)的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算

10、法 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)（算法 3.1)statckElemtop+=xstatckElemtop=x;top=top+1;3.

11、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)時間復(fù)雜度為：時間復(fù)雜度為：O(1)3.1 棧棧3. 順序?；静僮鞯膶?shí)現(xiàn)順序?；静僮鞯膶?shí)現(xiàn)2)順序棧的出棧操作順序棧的出棧操作 pop ( )的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.2) 將棧頂元素從棧中移去，并返回被移將棧頂元素從棧中移去，并

12、返回被移去的棧頂元素值。去的棧頂元素值。 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;top=top-1;3.1 棧棧public Object pop () throws Exce

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

14、附加頭結(jié)點(diǎn)，棧頂指針棧頂指針即為鏈表的即為鏈表的頭指針頭指針。 topa0an-1注意注意: : 鏈棧中鏈棧中指針的方向指針的方向an-2棧底棧底3.1 棧棧3.1.4 3.1.4 鏈棧及其基本操作的實(shí)現(xiàn)鏈棧及其基本操作的實(shí)現(xiàn)1. 鏈棧鏈棧思考思考?？諚l件棧空條件?棧的長度棧的長度?棧頂元素棧頂元素?如下問題如何描述如下問題如何描述?top=null需從棧頂開始沿著需從棧頂開始沿著nextnext指針依次對結(jié)點(diǎn)逐個進(jìn)指針依次對結(jié)點(diǎn)逐個進(jìn)行點(diǎn)數(shù)才能確定。行點(diǎn)數(shù)才能確定。top.getData( ) topa0an-1an-23.1 棧棧3.1.4 3.1.4 鏈棧及其基本操作的實(shí)現(xiàn)鏈棧及其基本操

15、作的實(shí)現(xiàn)2. 鏈棧類的描述鏈棧類的描述( (書中書中P73-74)P73-74)Import cho2.Node;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ù)元素個

16、數(shù)函數(shù)求棧數(shù)據(jù)元素個數(shù)函數(shù) public int length( ) / / 取棧頂元素的函數(shù)取棧頂元素的函數(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 vo

17、id pop ( ) / / 輸出函數(shù)輸出函數(shù)( (從棧頂?shù)綏５讖臈ｍ數(shù)綏５? )public void display () 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) 求鏈棧的長度操作求鏈棧的長度操作 length ()的實(shí)現(xiàn)的實(shí)現(xiàn) 計算出鏈棧中所包含的數(shù)據(jù)元素的個計算出鏈棧中所包含的數(shù)據(jù)元素的個數(shù)并返回其值。數(shù)并返回其值。 與求單鏈表長度的方法相同。與求單鏈表長度的方法相同。 ppplength1 2 3

18、211830754256topp4p5p6p3.1 棧棧public int length ( ) /算法3.3結(jié)束Node p = top; int length = 0;時間復(fù)雜度為：時間復(fù)雜度為：O(n)1) 求鏈棧的長度操作求鏈棧的長度操作 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)插入

19、到鏈棧的棧頂，使其成為新的棧頂元素。使其成為新的棧頂元素。 x1830754256toptopNode p = 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)時間復(fù)雜度為：時間復(fù)雜度為：O(1)p.setNext(top); top = p; 3.1 棧棧3. 鏈棧基本操作的實(shí)現(xiàn)鏈?；静僮鞯膶?shí)現(xiàn)3) 鏈棧的出棧操作鏈棧的出棧操作 pop ( )的實(shí)

20、現(xiàn)（算法的實(shí)現(xiàn)（算法 3.5) 將首結(jié)點(diǎn)（或棧頂結(jié)點(diǎn)）從鏈棧中移去，將首結(jié)點(diǎn)（或棧頂結(jié)點(diǎn)）從鏈棧中移去，并返回該結(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)時間復(fù)雜度為：時間復(fù)雜度為：O(1)Node p = top; top=top.getNext( ) return (p.getData( );

21、if (isEmpty() return null;else3.1 棧棧3.1.5 3.1.5 棧的應(yīng)用棧的應(yīng)用例例1. 分隔符匹配問題分隔符匹配問題例例2. 大數(shù)加法問題大數(shù)加法問題例例3. 表達(dá)式求值問題表達(dá)式求值問題例例4. 棧與遞歸問題棧與遞歸問題3.1 棧棧【例例1 1】分隔符匹配問題分隔符匹配問題- -問題分析問題分析 假設(shè)在表達(dá)式中（）或（ /* */）等為正確正確的格式，（ ）或（）)或（ ）均為不正確不正確的格式。則則 檢驗(yàn)分隔符是否匹配檢驗(yàn)分隔符是否匹配的方法可用的方法可用“期待的急迫程度期待的急迫程度”這個概念來描述。這個概念來描述。 Java Java程序中分隔符有圓、

22、方、花括程序中分隔符有圓、方、花括號和注釋符號和注釋符“/ /* *”和和“* */ /”。3.1 棧棧分析可能出現(xiàn)的分析可能出現(xiàn)的不匹配不匹配的情況的情況:l到來的右分隔符到來的右分隔符并非是所并非是所“期待期待”的；的；例如：考慮下列括號序列：例如：考慮下列括號序列：（ ）或或（ ）)或或（ ）1 2 3 4 1 2 3 4 5 6 1 2 3 4 5l到來的是到來的是“不速之客不速之客”；l直到結(jié)束，也沒有到來直到結(jié)束，也沒有到來所所“期待期待”的括的括弧?；?。【例例1 1】分隔符匹配問題分隔符匹配問題- -問題分析問題分析3.1 棧?！纠? 1】分隔符匹配問題分隔符匹配問題- -問題

23、分析問題分析這這三種情況三種情況對應(yīng)到棧的操作即為：對應(yīng)到棧的操作即為： 1 1和棧頂?shù)淖蠓指舴幌嗥ヅ?；和棧頂?shù)淖蠓指舴幌嗥ヅ洌?2 2棧中并沒有左分隔符等在那里；棧中并沒有左分隔符等在那里； 3 3棧中還有左分隔符沒有等到和它棧中還有左分隔符沒有等到和它相匹配的右括弧。相匹配的右括弧。3.1 棧棧1）凡出現(xiàn)）凡出現(xiàn)左括弧左括弧，則，則進(jìn)棧進(jìn)棧；2）凡出現(xiàn)）凡出現(xiàn)右括弧右括弧，首先檢查棧是否空，首先檢查棧是否空 若若?？諚？?，則表明該，則表明該“右括弧右括弧”多余多余， 否則和棧頂元素比較，否則和棧頂元素比較， 若若相匹配相匹配，則，則“左括弧出棧左括弧出棧” ， 否則否則表明表明不匹配不

24、匹配。3）表達(dá)式檢驗(yàn)）表達(dá)式檢驗(yàn)結(jié)束結(jié)束時，時， 若若棧空?？眨瑒t表明表達(dá)式中，則表明表達(dá)式中匹配正確匹配正確， 否則否則表明表明“左括弧左括弧”有余有余。【例例1 1】分隔符匹配問題分隔符匹配問題- -問題分析問題分析3.1 棧?！纠? 1】分隔符匹配問題分隔符匹配問題- -程序代碼（程序代碼（P77-78P77-78）public class Example3_1 private final int LEFT = 0;/ 記錄記錄左左分隔符分隔符private final int RIGHT = 1;/ 記錄記錄右右分隔符分隔符private final int OTHER = 2;/

25、記錄其他字符記錄其他字符Import java.util.Scanner;public int verifyFlag(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 clas

26、s Example3_1 / 檢驗(yàn)左分隔符檢驗(yàn)左分隔符str1和右分隔符和右分隔符str2是否匹配是否匹配public 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】分隔符匹配問題分隔

27、符匹配問題- -程序代碼（程序代碼（P77-78P77-78）3.1 棧棧public class Example3_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

28、 372 *(- ) 遇） 8 372- *( )遇( 9 372- * 10 372-* 結(jié)束 動畫動畫3-3-73.1 棧?！纠? 3】表達(dá)式求值表達(dá)式求值問題分析問題分析先找運(yùn)算符，先找運(yùn)算符， 再找操作數(shù)再找操作數(shù) 例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) f動畫動畫3-3-6a b+(c-d/e) f3.1 棧棧【例例3 3】表達(dá)式求值表達(dá)式求值問題分析問題分析1) 設(shè)立一個設(shè)立一個操作數(shù)棧；操作數(shù)棧；2) 從左到右依次讀入后綴表達(dá)式中的字符從左到右依次讀入后綴表達(dá)式中的字符:若若當(dāng)前字符當(dāng)前字符是操作數(shù)是操作數(shù)，則壓入操作數(shù)棧。，則壓入操作

29、數(shù)棧。后綴式求值的操作步驟為：后綴式求值的操作步驟為：若若當(dāng)前字符當(dāng)前字符是運(yùn)算符是運(yùn)算符，則從棧頂彈出兩，則從棧頂彈出兩個操作數(shù)參與運(yùn)算，并將運(yùn)算結(jié)果壓入操個操作數(shù)參與運(yùn)算，并將運(yùn)算結(jié)果壓入操作數(shù)棧內(nèi)。作數(shù)棧內(nèi)。動畫動畫3-3-63.1 棧?！纠? 3】表達(dá)式求值表達(dá)式求值程序代碼程序代碼Example3_3.javaExample3_3.java( (書書P84-85)P84-85)3.1 棧棧【例例4 4】棧與遞歸問題棧與遞歸問題 在程序設(shè)計中，經(jīng)常會碰到多個函在程序設(shè)計中，經(jīng)常會碰到多個函數(shù)的嵌套調(diào)用。和匯編程序設(shè)計中主程數(shù)的嵌套調(diào)用。和匯編程序設(shè)計中主程序和子程序之間的鏈接和信息交

30、換相類序和子程序之間的鏈接和信息交換相類似，在高級語言編制的程序中，調(diào)用函似，在高級語言編制的程序中，調(diào)用函數(shù)和被調(diào)用函數(shù)之間的鏈接和信息交換數(shù)和被調(diào)用函數(shù)之間的鏈接和信息交換也是由編譯程序通過也是由編譯程序通過棧棧來實(shí)施的。來實(shí)施的。3.1 棧棧【例例4 4】棧與遞歸問題棧與遞歸問題 當(dāng)在一個函數(shù)的運(yùn)行期間當(dāng)在一個函數(shù)的運(yùn)行期間調(diào)用另一調(diào)用另一個函數(shù)個函數(shù)時，在時，在運(yùn)行該被調(diào)用函數(shù)之前運(yùn)行該被調(diào)用函數(shù)之前，需先完成三項(xiàng)任務(wù)：需先完成三項(xiàng)任務(wù)：3.1 棧棧【例例4 4】棧與遞歸問題棧與遞歸問題3.1 棧?！纠? 4】棧與遞歸問題棧與遞歸問題多個函數(shù)嵌套調(diào)用的規(guī)則是：多個函數(shù)嵌套調(diào)用的規(guī)則是

31、：此時的內(nèi)存管理實(shí)行此時的內(nèi)存管理實(shí)行“棧式管理?xiàng)Ｊ焦芾怼焙笳{(diào)用先返回后調(diào)用先返回 ！例如：例如：void 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 4】棧與遞歸問題棧與遞歸問題遞歸工作棧：遞歸工作棧：遞歸過程執(zhí)行過程中占用的遞歸過程執(zhí)行過程中占用的 數(shù)據(jù)區(qū)。數(shù)據(jù)區(qū)。遞歸工作記錄：遞歸工作記錄：每一層的遞歸參數(shù)合成每一層的遞歸參數(shù)合成 一個記錄。一個記錄。當(dāng)前活動記錄：當(dāng)前活動記錄：棧頂記錄指示當(dāng)前層的棧頂記錄指示當(dāng)前層的 執(zhí)行情況。

32、執(zhí)行情況。當(dāng)前環(huán)境指針：當(dāng)前環(huán)境指針：遞歸工作棧的棧頂指針。遞歸工作棧的棧頂指針。 遞歸函數(shù)執(zhí)行的過程可視為遞歸函數(shù)執(zhí)行的過程可視為同一函數(shù)同一函數(shù)進(jìn)進(jìn)行嵌套調(diào)用，例如：行嵌套調(diào)用，例如：3.1 棧?！纠? 4】棧與遞歸問題棧與遞歸問題漢諾塔問題描述漢諾塔問題描述 n n階漢諾塔問題：階漢諾塔問題：假設(shè)有三個分別命名為假設(shè)有三個分別命名為X X，Y Y和和Z Z的塔座，在塔座的塔座，在塔座X X上插有上插有n n個直徑大小各個直徑大小各不相同，且從小到大編號為不相同，且從小到大編號為1 1、2 2、n n的圓的圓盤?，F(xiàn)要求將塔座盤。現(xiàn)要求將塔座X X上的上的n n個圓盤借助塔座個圓盤借助塔座

33、Y Y移至移至塔座塔座Z Z上，并仍按同樣順序疊排。圓盤移動時必上，并仍按同樣順序疊排。圓盤移動時必須遵循下列規(guī)則：須遵循下列規(guī)則： 每次只能移動一個圓盤；每次只能移動一個圓盤； 圓盤可以插在圓盤可以插在X X，Y Y和和Z Z中的任何一個塔中的任何一個塔座上；座上； 任何時刻都不能將一個較大的圓盤壓在任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上。較小的圓盤之上。3.1 棧棧【例例4 4】棧與遞歸問題棧與遞歸問題漢諾塔問題漢諾塔問題public void hanoi (int n, char x, char y, char z)/ 將塔座x上按直徑由小到大且至上而下編號為1至n的n個圓盤按

34、規(guī)則搬到塔座z上，y可用作輔助塔座。1 2 if (n=1)3 move(x, 1, z); / 將編號為的圓盤從x移到z4 else 5 hanoi(n-1, x, z, y); / 將x上編號為至n-1的 /圓盤移到y(tǒng), z作輔助塔6 move(x, n, z); / 將編號為n的圓盤從x移到z7 hanoi(n-1, y, x, z); / 將y上編號為至n-1的 /圓盤移到z, x作輔助塔8 9 3.1 棧?！纠? 4】棧與遞歸問題棧與遞歸問題漢諾塔問題漢諾塔問題public void hanoi (int n, char x, char y, char z) 1 2 if (n=1

35、)3 move(x, 1, z); 4 else 5 hanoi(n-1, x, z, y); 6 move(x, n, z); 7 hanoi(n-1, y, x, z); 8 9 3.1 棧?！纠?】漢諾塔問題漢諾塔問題程序代碼程序代碼Example3_4.javaExample3_4.java( (書書P86-87)P86-87)3.2 隊(duì)列隊(duì)列3.2.1 3.2.1 隊(duì)列的概念隊(duì)列的概念隊(duì)列隊(duì)列是只允許在表的一端進(jìn)行插入，而在表是只允許在表的一端進(jìn)行插入，而在表 的另一端進(jìn)行刪除操作的一種的另一端進(jìn)行刪除操作的一種特殊線性表特殊線性表。 允許插入的一端稱為允許插入的一端稱為“隊(duì)尾隊(duì)尾

36、”，允許刪除的，允許刪除的一一 端稱為端稱為“隊(duì)首隊(duì)首”。(2) 棧棧是是“先進(jìn)先出先進(jìn)先出”的線性表（的線性表（FIFO）或）或 “后進(jìn)后出后進(jìn)后出”的線性表（的線性表（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ì)列的長度：）求隊(duì)列的長度：4）取隊(duì)首元素操作：）取隊(duì)首元素操作：5）入隊(duì)操作：）入隊(duì)操作：peek( )offer( x )

37、6）出隊(duì)操作：）出隊(duì)操作：poll ( ) 1. 1.基本操作基本操作3.2 隊(duì)列隊(duì)列3.1.2 3.1.2 棧的抽象數(shù)據(jù)類型描述棧的抽象數(shù)據(jù)類型描述 2. 2.隊(duì)列的抽象數(shù)據(jù)類型的隊(duì)列的抽象數(shù)據(jù)類型的JavaJava接口描述接口描述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)此接口的方

38、法有兩種實(shí)現(xiàn)此接口的方法有兩種: 順序隊(duì)列順序隊(duì)列鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列3.2 隊(duì)列隊(duì)列3.2.3 3.2.3 順序隊(duì)列及其基本操作的實(shí)現(xiàn)順序隊(duì)列及其基本操作的實(shí)現(xiàn)1. 順序隊(duì)列順序隊(duì)列非空隊(duì)列非空隊(duì)列空隊(duì)列空隊(duì)列a0a1an-1 rear(隊(duì)尾指針) maxSize-1queueElemfront(隊(duì)首指針)0 1 n-1frontstackElemrear maxSize-10 1 2 3.2 隊(duì)列隊(duì)列3.1.3 3.1.3 順序棧及其基本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)1. 順序隊(duì)列順序隊(duì)列思考思考隊(duì)空條件隊(duì)空條件?隊(duì)列滿條件隊(duì)列滿條件?如下問題如何描述如下問題如何描述?front=rear

39、rear=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. 順序隊(duì)列順序隊(duì)列 序號值：序號值：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

40、順序棧及其基本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)2. 循環(huán)順序隊(duì)列循環(huán)順序隊(duì)列 將順序隊(duì)列看成是首尾相聯(lián)的隊(duì)列。將順序隊(duì)列看成是首尾相聯(lián)的隊(duì)列。動畫動畫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ì)滿條件：front=rearfront=rear隊(duì)空與隊(duì)滿的條件相同隊(duì)空與隊(duì)滿的條件相同, ,無法判斷無法判斷, ,怎么辦？怎么辦？054321 frontreara0a1a2a3a4a53.2 隊(duì)列隊(duì)列3.2.3 3.2.3 順序棧及其基

41、本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)2. 循環(huán)順序隊(duì)列循環(huán)順序隊(duì)列 1. 1.設(shè)一個標(biāo)志變量設(shè)一個標(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=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è)置一個計數(shù)變量設(shè)置一個計數(shù)變量

42、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 隊(duì)列隊(duì)列3.2.3 3.2.3 順序棧及其基本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)2. 循環(huán)順序隊(duì)列循環(huán)順序隊(duì)列3. 3. 少用一個元素空間：如下圖少用一個元素空間：如下圖循環(huán)隊(duì)空條件：循環(huán)隊(duì)空條件：循環(huán)隊(duì)滿條件：循環(huán)隊(duì)滿條件：front

43、=rear（rear+1）% queueElem.length = =front054321 frontreara1a2a3a4a5空空3.2 隊(duì)列隊(duì)列3.2.3 3.2.3 順序棧及其基本操作的實(shí)現(xiàn)順序棧及其基本操作的實(shí)現(xiàn)3. 循環(huán)順序隊(duì)列類的描述循環(huán)順序隊(duì)列類的描述( (書中書中P91)P91)public class CircleSqQueue implements IQueue private Object queueElem; private int front; private int rear; /構(gòu)造一個容量為構(gòu)造一個容量為maxSize的空循環(huán)隊(duì)列函數(shù)的空循環(huán)隊(duì)列函數(shù) pub

44、lic 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ì)列類的描述( (見書見書P91)P91)public class CircleSqQueue implements IQueue public boolean isEmpty( ) / 判判空函數(shù)空函數(shù)public int length( ) / / 求隊(duì)列當(dāng)前長度函數(shù)求隊(duì)列當(dāng)前長度函數(shù)

45、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 CircleSqQueue implements IQueue /循環(huán)順序隊(duì)列類的描述結(jié)束循環(huán)順序隊(duì)列類的描述結(jié)束/ / 入隊(duì)操作的函數(shù)入隊(duì)操作的函數(shù)public

46、 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ì)列類的描述( (見書見書P91)P91)if (!isEmpty() else for (int i = front; i != rear; i = (i + 1) % queueElem.length) System.out.print(queueElemi.toString() + );System.out.println(此隊(duì)列為

47、空此隊(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插入到一個循環(huán)隊(duì)插入到一個循環(huán)隊(duì)列的隊(duì)尾。列的隊(duì)尾。rear054321fronta3a4a5x3.2 隊(duì)列隊(duì)列 1）若）若，則拋出異常后結(jié)束操作；，則拋出異常后結(jié)束操作； 2）若隊(duì)非滿，則將）若隊(duì)非滿，則將x進(jìn)隊(duì)，尾指針加進(jìn)隊(duì)，尾指針加1queueElemrear = x; /x入隊(duì)入隊(duì)if (rear+1)%queueElem.length=front) throw new Exc

48、eption(隊(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.length=front) throw new Exception(“隊(duì)列已滿隊(duì)列已滿);else queueElemrear = x; rear=(rear+1)% que

49、ueElem.length; 時間復(fù)雜度為：時間復(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ì)首元素刪除，并返回其值。a5front021054reara6a73.2 隊(duì)列隊(duì)列 1）若）若，則返回空值；，則返回空值； 2）若隊(duì)非空，則返回隊(duì)首元素且首指針加）若隊(duì)非空

50、，則返回隊(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 Object poll ( ) /算法3.7結(jié)束if (front = rear) return null;else Object t = queueElemfront;

51、front = (front + 1) % queueElem.length; return t; 時間復(fù)雜度為：時間復(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ì)列3.2.4 3.2.4 鏈隊(duì)列及其基本操作的實(shí)現(xiàn)鏈隊(duì)列及其基本操作的實(shí)現(xiàn)1. 鏈隊(duì)列鏈隊(duì)列 隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊(duì)列鏈隊(duì)列，其鏈?zhǔn)酱?，其鏈?zhǔn)酱鎯Y(jié)構(gòu)在此用儲結(jié)構(gòu)在此用不帶頭結(jié)點(diǎn)不帶頭結(jié)點(diǎn)的單鏈表來實(shí)現(xiàn)的單鏈表來實(shí)現(xiàn). . frontan-1a0a1 rear隊(duì)首指針隊(duì)

52、首指針隊(duì)尾指針隊(duì)尾指針3.2 隊(duì)列隊(duì)列3.2.4 3.2.4 鏈隊(duì)列及其基本操作的實(shí)現(xiàn)鏈隊(duì)列及其基本操作的實(shí)現(xiàn)1. 鏈隊(duì)列鏈隊(duì)列思考思考隊(duì)列空的條件隊(duì)列空的條件?隊(duì)列的長度隊(duì)列的長度?隊(duì)首元素隊(duì)首元素?如下問題如何描述如下問題如何描述?front=null需從隊(duì)首開始沿著需從隊(duì)首開始沿著nextnext指針依次對結(jié)點(diǎn)逐個進(jìn)指針依次對結(jié)點(diǎn)逐個進(jìn)行點(diǎn)數(shù)才能確定。行點(diǎn)數(shù)才能確定。front.getData( )隊(duì)尾元素隊(duì)尾元素?rear.getData( )3.2 隊(duì)列隊(duì)列3.2.4 3.2.4 鏈隊(duì)列及其基本操作的實(shí)現(xiàn)鏈隊(duì)列及其基本操作的實(shí)現(xiàn)2. 鏈隊(duì)列類的描述鏈隊(duì)列類的描述( (書中書中P93-

53、94)P93-94)import cho2.Node;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ì)列長度函數(shù)求隊(duì)列長度函數(shù)public int leng

54、th( ) 2. 鏈隊(duì)列類的描述鏈隊(duì)列類的描述( (書中書中P93-94)P93-94)Node p = front;int length = 0;while (p !=null) p = p.getNext(); /指針下移指針下移 +length; /計數(shù)器加計數(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() /

55、隊(duì)列隊(duì)列非空非空 elsereturn front.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

56、;while( p!=null ) System.out.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ì)的尾部（修改鏈）將

57、新結(jié)點(diǎn)插入鏈隊(duì)的尾部（修改鏈）隊(duì)非空時隊(duì)非空時: :隊(duì)空時隊(duì)空時: :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; 時間復(fù)雜度為：時間復(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ì)列

58、基本操作的實(shí)現(xiàn)鏈隊(duì)列基本操作的實(shí)現(xiàn)2) 鏈隊(duì)列的出隊(duì)操作鏈隊(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ì)首元素并返回其值18

59、30754256frontrearpc) 若刪除的是隊(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;時間復(fù)雜度為：

60、時間復(fù)雜度為：O(1)3. 鏈隊(duì)列基本操作的實(shí)現(xiàn)鏈隊(duì)列基本操作的實(shí)現(xiàn)2) 鏈隊(duì)列的出隊(duì)操作鏈隊(duì)列的出隊(duì)操作 poll()的實(shí)現(xiàn)的實(shí)現(xiàn)3.2 隊(duì)列隊(duì)列【例例 】編程實(shí)現(xiàn)求解的素數(shù)環(huán)問題編程實(shí)現(xiàn)求解的素數(shù)環(huán)問題3.2.5 3.2.5 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用【問題描述】【問題描述】將將1 1n n的的 n n個自然數(shù)排列成個自然數(shù)排列成環(huán)形，使得每相鄰兩數(shù)之和為素數(shù)，從而構(gòu)成環(huán)形，使得每相鄰兩數(shù)之和為素數(shù)，從而構(gòu)成一個素數(shù)環(huán)。一個素數(shù)環(huán)?！痉椒ǚ椒ā?先引入順序表類先引入順序表類SqlistSqlist和鏈隊(duì)列類和鏈隊(duì)列類LinkQueueLinkQueue，再創(chuàng)建，再創(chuàng)建SqlistSqlist類的一個對象類的一個對象L L作作為順序表，用于存放素數(shù)環(huán)的數(shù)據(jù)元素；