棧與隊列(java版)

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

2、lete(i) Delete(n-1) Delete(0) 0in-1 棧和隊列是兩種棧和隊列是兩種操作受限操作受限的的線性線性表表，是兩種常用的數(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è)有編號為設(shè)有編號為1 1，2 2，3 3，4 4的四輛的四輛列車，順序進(jìn)一個棧式結(jié)構(gòu)的站臺列車，順序進(jìn)一個棧式

3、結(jié)構(gòu)的站臺，具體寫出這四輛列車開出車站的，具體寫出這四輛列車開出車站的所有可能的順序。所有可能的順序。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）求棧的長度：）求棧的長度：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件?棧滿條件棧滿條件?棧的長度棧的長度?棧頂元素棧頂元素?如下問題如何描述如下問題如何描述?top=0top=stackElem.lengthtopstackElemtop-1a0a1an-1 top=n stackElem 0 1

6、 n-13.1 棧棧2.2.順序棧類的描述順序棧類的描述( (書書P71-P71-與與P33P33順序表類對照學(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. 順序棧類的描述順

7、序棧類的描述( (見教材見教材P71)P71)public class SqStack implements 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. 順

8、序棧類的描述順序棧類的描述( (見教材見教材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)時間復(fù)雜度為：時間復(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)時間復(fù)雜度為：時間復(fù)雜度為：O(1)3.1 棧棧1. 鏈棧鏈棧 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧鏈棧，是運(yùn)算受限，是運(yùn)算受限的單鏈表，其插入和刪除操作僅限制在的單鏈表，其插入和刪除操作僅限制在鏈表的鏈表的表頭位置上表頭位置上進(jìn)行，故鏈棧沒有必要象單鏈表一進(jìn)行，故鏈棧沒有必

13、要象單鏈表一樣附加頭結(jié)點(diǎn)，樣附加頭結(jié)點(diǎn)，棧頂指針棧頂指針即為鏈表的即為鏈表的頭指針頭指針。 topa0an-1注意注意: : 鏈棧中鏈棧中指針的方向指針的方向an-2棧底棧底3.1 棧棧1. 鏈棧鏈棧思考思考?？諚l件?？諚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 棧棧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ù)元素個數(shù)函數(shù)求棧數(shù)據(jù)元素個數(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) 求鏈棧的長度操作求鏈棧的長度操作 length ()的實(shí)現(xiàn)的實(shí)現(xiàn) 計算出鏈棧中所包含的數(shù)據(jù)元素的個計算出鏈棧中所包含的數(shù)據(jù)元素的個數(shù)并返回其值。數(shù)并返回其值。 與求單鏈表長度的方法相同。與求單鏈表長度的方法相同。 ppplength1 2 3211830754256topp4p5p6p3.1 棧棧public int length ( ) /算法3

17、.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)插入到鏈棧的棧頂，使其成為新的棧頂元素。使其成為新的棧頂元素。 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)時間復(fù)雜度為：時間復(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)時間復(fù)雜度為：時間復(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. 分隔符匹配問題分隔符匹配問題例例2. 大數(shù)加法問題大數(shù)加法問題例例3. 表達(dá)式求值問題表達(dá)式求值問題例例4. 棧與遞歸問題棧與遞歸問題3.1 棧棧【例例1 1】分隔符匹配問題分隔符匹配問題- -問題分析問題分析 假設(shè)在表達(dá)式中（）或（ /* */）等為正確正確的格式，（ ）或（）)或（ ）均為不正確不正確的格式。則則 檢驗(yàn)分隔符是否匹配檢驗(yàn)分隔符是否匹配的方法可用的方法可用“期待的急迫程度期待的急迫程度”這個概念來描述。這個概念來描述。 Java Java程序中分隔符有圓、方、花括程序中分隔符有圓、方、花括號和注釋符號和注釋符“/ /* *”和和“* */ /”。3.1 棧棧分析

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

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

23、確， 否則否則表明表明“左括弧左括弧”有余有余。【例例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;/ 記錄其他字符記錄其他字符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】分隔符匹配問題分隔符匹配問題- -程序代碼（程序代碼（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é)束 動畫動畫3

27、-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】表達(dá)式求值表達(dá)式求值問題分析問題分析1) 設(shè)立一個設(shè)立一個操作數(shù)棧；操作數(shù)棧；2) 從左到右依次讀入后綴表達(dá)式中的字符從左到右依次讀入后綴表達(dá)式中的字符:若若當(dāng)前字符當(dāng)前字符是操作數(shù)是操作數(shù)，則壓入操作數(shù)棧。，則壓入操作數(shù)棧。后綴式求值的操作步驟為：后綴式求值的操作步驟為：若若當(dāng)前字符當(dāng)前字符是運(yùn)算符是運(yùn)算符，則從棧頂彈出兩，

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

29、數(shù)和被調(diào)用函數(shù)之間的鏈接和信息交換數(shù)和被調(diào)用函數(shù)之間的鏈接和信息交換也是由編譯程序通過也是由編譯程序通過棧棧來實(shí)施的。來實(shí)施的。3.1 棧?！纠? 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】棧與遞歸問題棧與遞歸問題3.1 棧?！纠? 4】棧與遞歸問題棧與遞歸問題多個函數(shù)嵌套調(diào)用的規(guī)則是：多個函數(shù)嵌套調(diào)用的規(guī)則是：此時的內(nèi)存管理實(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】棧與遞歸問題棧與遞歸問題遞歸工作棧：遞歸工作棧：遞歸過程執(zhí)行過程中占用的遞歸過程執(zhí)行過程中占用的 數(shù)據(jù)區(qū)。數(shù)據(jù)區(qū)。遞歸工作記錄：遞歸工作記錄：每一層的遞歸參數(shù)合成每一層的遞歸參數(shù)合成 一個記錄。一個記錄。當(dāng)前活動記錄：當(dāng)前活動記錄：棧頂記錄指示當(dāng)前層的棧頂記錄指示當(dāng)前層的 執(zhí)行情況。執(zhí)行情況。當(dāng)前環(huán)境指針：當(dāng)前環(huán)境指針：遞歸工作棧的棧頂指針。遞歸工作棧的棧頂指針。 遞歸函數(shù)執(zhí)行的過程可視為

31、遞歸函數(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的圓的圓盤。現(xiàn)要求將塔座盤?，F(xiàn)要求將塔座X X上的上的n n個圓盤借助塔座個圓盤借助塔座Y Y移至移至塔座塔座Z Z上，并仍按同樣順序疊排。圓盤移動時必上，并仍按同樣順序疊排。圓盤移動時必須遵循下

32、列規(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個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。1 2 if (n=1)3 move(x, 1, z); / 將編號為的

33、圓盤從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 4】棧與遞歸問題棧與遞歸問題漢諾塔問題漢諾塔問題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 棧棧【例例4】漢諾塔問題漢諾塔問題程序代碼程序代碼Example3_4.javaExample3_4.java( (書書P86-87)P86-87)3.2 隊列隊列隊列隊列是只允許在表的一端進(jìn)行插入，而在表是只允許在表的一端進(jìn)行插入，而在表 的另一端進(jìn)行刪除操作的一種的另一端進(jìn)行刪除操作的一種特殊線性表特殊線性表。 允許插入的一端稱為允許插入的一端稱為“隊尾隊尾”，允許刪除的，允許刪除的一一 端稱為端稱為“隊首隊首”。(2) 棧棧是是“先進(jìn)先出先進(jìn)先出”的線性表（的線性表（FIFO）或）或 “后進(jìn)后出后進(jìn)后出”

35、的線性表（的線性表（LILO）a0 a1 a2 an-1隊首隊首隊尾隊尾入隊入隊出隊出隊3.2 隊列隊列3.2.2 3.2.2 隊列的抽象數(shù)據(jù)類型描述隊列的抽象數(shù)據(jù)類型描述 clear( )1 1）隊列的置空操作：）隊列的置空操作： isEmpty( )2 2）隊列的判空操作：）隊列的判空操作： length( )3）求隊列的長度：）求隊列的長度：4）取隊首元素操作：）取隊首元素操作：5）入隊操作：）入隊操作：peek( )offer( x )6）出隊操作：）出隊操作：poll ( ) 1. 1.基本操作基本操作3.2 隊列隊列 2. 2.隊列的抽象數(shù)據(jù)類型的隊列的抽象數(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)此接口的方法有兩種: 順序隊列順序隊列鏈?zhǔn)疥犃墟準(zhǔn)疥犃?.2 隊列隊列1. 順序隊列順序隊列非空隊列非空隊列空隊列空隊列a0a1an-1 rear(隊尾指針) maxSize-1queueElemfron

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

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

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

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

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

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

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

44、 CircleSqQueue implements IQueue /循環(huán)順序隊列類的描述結(jié)束循環(huán)順序隊列類的描述結(jié)束/ / 入隊操作的函數(shù)入隊操作的函數(shù)public void offer( Object x) / 出隊操作的函數(shù)出隊操作的函數(shù)public void poll ( ) / / 輸出函數(shù)輸出函數(shù)( (從隊首到隊尾從隊首到隊尾) )public void display () 3. 循環(huán)順序隊列類的描述循環(huá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(此隊列為空此隊列為空);3.2 隊列隊列4. 循環(huán)順序隊列基本操作的實(shí)現(xiàn)循環(huán)順序隊列基本操作的實(shí)現(xiàn)1)循環(huán)順序隊列的入隊操作循環(huán)順序隊列的入隊操作 offer (x)的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.6) 將新元素將新元素x插入到一個循環(huán)隊插入到一個循環(huán)隊列的隊尾。列的隊尾。rear054321fronta3a4a5x3.2 隊列隊列 1）若）若，則拋出異常后結(jié)束操作；，則拋出異常后結(jié)束操作； 2）若隊非滿，則將）若隊非滿，則將x進(jìn)隊，尾指針加

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

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

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

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

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

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

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

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

54、ut.print(p.getData( ).tostring( )+ )p=p.getNext();3.2 隊列隊列3. 鏈隊列基本操作的實(shí)現(xiàn)鏈隊列基本操作的實(shí)現(xiàn)1) 鏈隊列的入隊操作鏈隊列的入隊操作 offer(x )的實(shí)現(xiàn)（算法的實(shí)現(xiàn)（算法 3.8) 插入新元素插入新元素x x使其成為新的隊尾元素。使其成為新的隊尾元素。 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)插入鏈隊的尾部（修改鏈）將新結(jié)點(diǎn)插入鏈隊的尾部（修改鏈）隊非空時隊非空時: :

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

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

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

58、列基本操作的實(shí)現(xiàn)2) 鏈隊列的出隊操作鏈隊列的出隊操作 poll()的實(shí)現(xiàn)的實(shí)現(xiàn)3.2 隊列隊列【例例 】編程實(shí)現(xiàn)求解的素數(shù)環(huán)問題編程實(shí)現(xiàn)求解的素數(shù)環(huán)問題3.2.5 3.2.5 隊列的應(yīng)用隊列的應(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和鏈隊列類和鏈隊列類LinkQueueLinkQueue，再創(chuàng)建，再創(chuàng)建SqlistSqlist類的一個對象類的一個對象L L作作為順序表，用于存放素數(shù)

59、環(huán)的數(shù)據(jù)元素；創(chuàng)建為順序表，用于存放素數(shù)環(huán)的數(shù)據(jù)元素；創(chuàng)建LinkQueueLinkQueue類的一個對象類的一個對象Q Q，作為隊列用于存放，作為隊列用于存放還未加入到素數(shù)環(huán)中的自然數(shù)。還未加入到素數(shù)環(huán)中的自然數(shù)。3.2 隊列隊列【例例 】編程實(shí)現(xiàn)求解的素數(shù)環(huán)問題編程實(shí)現(xiàn)求解的素數(shù)環(huán)問題3.2.5 3.2.5 隊列的應(yīng)用隊列的應(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)。【方法方法】 (2) (2) 初始化順序表初始化順序表L L和隊列和隊列Q: Q:

60、 將將1 1加入到加入到順序表順序表L L中，將中，將2 2n n的自然數(shù)全部加入到的自然數(shù)全部加入到Q Q隊列隊列中。中。3.2 隊列隊列【例例 】編程實(shí)現(xiàn)求解的素數(shù)環(huán)問題編程實(shí)現(xiàn)求解的素數(shù)環(huán)問題3.2.5 3.2.5 隊列的應(yīng)用隊列的應(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)。【方法方法】 (3) (3) 將出隊的隊首元素將出隊的隊首元素p p與素數(shù)環(huán)最后一與素數(shù)環(huán)最后一個數(shù)據(jù)元素個數(shù)據(jù)元素q q相加相加。 (a) (a)若兩數(shù)之和是素數(shù)并且若兩數(shù)之和是素數(shù)并且p p 不是隊列中不是隊列中的最后一個數(shù)據(jù)元素（或隊尾元素