第04章棧和隊列(Java版)

1、數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 1第第4章章 棧和隊列棧和隊列l(wèi)4.1 棧棧l4.2 隊列隊列l(wèi)4.3 遞歸遞歸 目的：目的：使用?；蜿犃星蠼鈶?yīng)用問題。使用棧或隊列求解應(yīng)用問題。 要求：要求：棧和隊列的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)。棧和隊列的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)。 重點：重點：棧和隊列的設(shè)計和應(yīng)用。棧和隊列的設(shè)計和應(yīng)用。 難點：難點：?；蜿犃械氖褂脠龊?，以及如何使用?；蜿犃械氖褂脠龊?，以及如何使用 棧和隊列求解應(yīng)用問題。棧和隊列求解應(yīng)用問題。數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 24.1 棧棧4.1.1 棧抽象數(shù)據(jù)類型棧抽象數(shù)據(jù)類型 棧棧（stack）是一種線性表）是一種線性表，插入和刪

2、除操作插入和刪除操作只允許在線性表的一端進(jìn)行。先進(jìn)后出。只允許在線性表的一端進(jìn)行。先進(jìn)后出。數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 3圖圖4.1 棧（順序棧）及其狀態(tài)變化棧（順序棧）及其狀態(tài)變化 A, B, C, D 入棧入棧, 入棧入棧, 出棧出棧, 入棧入棧, 入棧入棧, 出棧出棧, 出棧出棧, 出棧出棧 【思考題思考題4-1】 入棧入棧A, B, C, D，出棧，出棧A, B, C, D、D, C, B, A？還有哪些？有哪些不可能的出棧序列？為什么？還有哪些？有哪些不可能的出棧序列？為什么？數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 4棧抽象數(shù)據(jù)類型棧抽象數(shù)據(jù)類型ADT，棧接口，棧接口pu

3、blic interface Stack public abstract boolean isEmpty(); /判空判空 public abstract void push(T x); /x入棧入棧 public abstract T peek(); /返回棧頂，未出棧返回棧頂，未出棧 public abstract T pop(); /出棧，返回棧頂出棧，返回棧頂數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 5習(xí)題習(xí)題4-3習(xí)習(xí)4-3 能否使用一個線性表對象作為棧，或?qū)Ｄ芊袷褂靡粋€線性表對象作為棧，或?qū)Ｂ暶鳛槔^承線性表？入棧調(diào)用聲明為繼承線性表？入棧調(diào)用insert(0,x)函數(shù)，函數(shù)，出棧

4、調(diào)用出棧調(diào)用remove(0)函數(shù)？為什么？函數(shù)？為什么？【習(xí)題解答習(xí)題解答】都不能。都不能。 數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 64.1.2 順序棧順序棧/順序棧類，最終類，實現(xiàn)棧接口，順序棧類，最終類，實現(xiàn)棧接口，T表示元素類型表示元素類型public final class SeqStack implements Stack private SeqList list; /順序表順序表 public SeqStack(int capacity) /構(gòu)造空棧構(gòu)造空棧 public SeqStack() /構(gòu)造空棧構(gòu)造空棧 public boolean isEmpty() /判空判空 p

5、ublic void push(T x) /x入棧入棧 public T peek() /返回棧頂（未出棧）返回棧頂（未出棧） public T pop() /出棧，返回棧頂元素出棧，返回棧頂元素數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 7習(xí)題解答習(xí)題解答4-4 使用順序表對象作使用順序表對象作為棧成員變量的操作效率分析為棧成員變量的操作效率分析 數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 84.1.3 鏈?zhǔn)綏ｆ準(zhǔn)綏D圖4.3 鏈?zhǔn)綏５娜霔：统鰲２僮麈準(zhǔn)綏５娜霔：统鰲２僮?數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 9鏈?zhǔn)綏ｎ愭準(zhǔn)綏ｎ怢inkedStack /鏈?zhǔn)綏ｎ?，最終類，實現(xiàn)棧接口，鏈?zhǔn)綏ｎ悾罱K

6、類，實現(xiàn)棧接口，T表示元素類型表示元素類型public final class LinkedStack implements Stack private SinglyList list; /單鏈表單鏈表 public LinkedStack() /構(gòu)造空棧構(gòu)造空棧 public boolean isEmpty() /判空判空 public void push(T x) /x入棧入棧 public T peek() /返回棧頂（未出棧）返回棧頂（未出棧） public T pop() /出棧，返回棧頂元素出棧，返回棧頂元素數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 10習(xí)題解答習(xí)題解答4-4 使用單

7、鏈表對象作使用單鏈表對象作為棧成員變量的操作效率分析為棧成員變量的操作效率分析 數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 114.1.4 棧的應(yīng)用棧的應(yīng)用1. 棧是嵌套調(diào)用機(jī)制的實現(xiàn)基礎(chǔ)棧是嵌套調(diào)用機(jī)制的實現(xiàn)基礎(chǔ) 2. 使用棧以非遞歸方式實現(xiàn)遞歸算法使用棧以非遞歸方式實現(xiàn)遞歸算法 數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 12【例例4.1】 括號匹配的語法檢查。括號匹配的語法檢查。圖圖4.5 表達(dá)式中圓括號匹配的語法檢查表達(dá)式中圓括號匹配的語法檢查數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 13【例例4.2】 使用棧計算算術(shù)表達(dá)式值使用棧計算算術(shù)表達(dá)式值中綴表達(dá)式：中綴表達(dá)式：1+2*(3-4)+5數(shù)

8、據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 14習(xí)題習(xí)題4-5【習(xí)題解答習(xí)題解答】ABCDEF+*G/-H+*+IJ+K*-習(xí)習(xí)4-5 中綴表達(dá)式如下，中綴表達(dá)式如下， 寫出后綴表達(dá)式。寫出后綴表達(dá)式。 A+B*(C-D*(E+F)/G+H)-(I+J)*K數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 15（1）將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式）將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 16（2）后綴表達(dá)式求值）后綴表達(dá)式求值 數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 17Expressionpublic class Expression StringBuffer toPostfix(

9、String infix) /返回將返回將infix中綴表達(dá)式轉(zhuǎn)換成的后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)換成的后綴表達(dá)式 int toValue(StringBuffer postfix) /計算后綴表達(dá)式的值計算后綴表達(dá)式的值 【思考題思考題4-2】 數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 184.2 隊列隊列4.2.1 隊列抽象數(shù)據(jù)類型隊列抽象數(shù)據(jù)類型隊列隊列（queue）是一種特殊的線性表，其插入和刪除操）是一種特殊的線性表，其插入和刪除操作分別在線性表的兩端進(jìn)行。先進(jìn)先出。作分別在線性表的兩端進(jìn)行。先進(jìn)先出。數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 194.2.1 隊列抽象數(shù)據(jù)類型隊列抽象數(shù)據(jù)類型/

10、隊列接口，描述隊列抽象數(shù)據(jù)類型，隊列接口，描述隊列抽象數(shù)據(jù)類型，T表示元素類型表示元素類型public interface Queue public abstract boolean isEmpty(); /判空判空 public abstract boolean add(T x); /x入隊入隊 public abstract T peek(); /返回隊頭，沒有刪除返回隊頭，沒有刪除 public abstract T poll(); /出隊，返回隊頭出隊，返回隊頭數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 20習(xí)題習(xí)題4-8習(xí)習(xí)4-8 能否使用一個線性表對象作為隊列，能否使用一個線性表對象作

11、為隊列， 或或?qū)㈥犃新暶鳛槔^承線性表，入棧調(diào)用將隊列聲明為繼承線性表，入棧調(diào)用insert(x)函數(shù)，出棧調(diào)用函數(shù)，出棧調(diào)用remove(0)函數(shù)？為函數(shù)？為什么？什么？【習(xí)題解答習(xí)題解答】都不能。都不能。數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 214.2.2 順序隊列順序隊列1.順序隊列順序隊列 （1）使用順序表，出隊效率低使用順序表，出隊效率低數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 22（2） 使用數(shù)組，存在假溢出使用數(shù)組，存在假溢出不移動數(shù)據(jù)元素不移動數(shù)據(jù)元素 數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 232. 順序循環(huán)隊列順序循環(huán)隊列 front=(front+1) % length;r

12、ear=(rear+1) % length;數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 243. 順序循環(huán)隊列類順序循環(huán)隊列類 /順序循環(huán)隊列類，最終類，實現(xiàn)隊列接口，順序循環(huán)隊列類，最終類，實現(xiàn)隊列接口，T元素類型元素類型public final class SeqQueue implements Queue private Object element; /數(shù)組數(shù)組 private int front, rear; /隊列頭尾下標(biāo)隊列頭尾下標(biāo) public SeqQueue(int capacity)/構(gòu)造空隊列構(gòu)造空隊列 public SeqQueue() /構(gòu)造空隊列構(gòu)造空隊列 publi

13、c boolean isEmpty(); /判空判空 public boolean add(T x); /x入隊入隊 public T peek(); /返回隊頭，沒有刪除返回隊頭，沒有刪除 public T poll(); /出隊，返回隊頭出隊，返回隊頭 數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 254.2.3 鏈?zhǔn)疥犃墟準(zhǔn)疥犃校?）使用單鏈表，入隊效率低）使用單鏈表，入隊效率低 數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 26（2）單鏈表設(shè)計，增加尾指針）單鏈表設(shè)計，增加尾指針 數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 27鏈?zhǔn)疥犃蓄愭準(zhǔn)疥犃蓄怢inkedQueue /鏈?zhǔn)疥犃蓄?，最終類，實現(xiàn)隊列

14、接口，鏈?zhǔn)疥犃蓄?，最終類，實現(xiàn)隊列接口，T元素類型元素類型public final class LinkedQueue implements Queue private Node front, rear; /隊頭和隊尾結(jié)點隊頭和隊尾結(jié)點 public LinkedQueue() /構(gòu)造空隊列構(gòu)造空隊列 public boolean isEmpty(); /判空判空 public boolean add(T x); /x入隊入隊 public T peek(); /返回隊頭，沒有刪除返回隊頭，沒有刪除 public T poll(); /出隊，返回隊頭出隊，返回隊頭數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版

15、）第4章 284.2.4 隊列的應(yīng)用隊列的應(yīng)用【例例4.3】 求解素數(shù)環(huán)問題。求解素數(shù)環(huán)問題。數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 29【例例4.3】 求解素數(shù)環(huán)問題。求解素數(shù)環(huán)問題。public class PrimeRing public PrimeRing(int max) public SortedSeqList createPrime(int max)【思考題思考題4-3】使用循環(huán)雙鏈表存儲素數(shù)集合使用循環(huán)雙鏈表存儲素數(shù)集合和素數(shù)環(huán)。和素數(shù)環(huán)。 使用棧？使用棧？數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 30實驗實驗4-13 走迷宮走迷宮(a) 棧存儲經(jīng)過的點，出棧返回上一個點，棧存儲

16、經(jīng)過的點，出棧返回上一個點，再尋找其他路徑再尋找其他路徑數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 31實驗實驗4-13 走迷宮走迷宮數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 32實驗實驗4-14 騎士游歷騎士游歷數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 33實驗實驗4-14 騎士游歷騎士游歷88棋盤，從棋盤，從(0,0)開開始的一次游歷路徑始的一次游歷路徑55棋盤，棋盤，一次不成功游歷路徑一次不成功游歷路徑數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 344.2.5 優(yōu)先隊列優(yōu)先隊列 n優(yōu)先隊列優(yōu)先隊列（Priority Queue），隊列中的每個元素都），隊列中的每個元素都有一個優(yōu)先級，每次出隊的是具有

17、最高優(yōu)先級的元有一個優(yōu)先級，每次出隊的是具有最高優(yōu)先級的元素。素。n優(yōu)先隊列的存儲結(jié)構(gòu)。分別使用一個順序表、排序優(yōu)先隊列的存儲結(jié)構(gòu)。分別使用一個順序表、排序順序表、單鏈表、排序單鏈表、循環(huán)雙鏈表、排序順序表、單鏈表、排序單鏈表、循環(huán)雙鏈表、排序循環(huán)雙鏈表作為優(yōu)先隊列的成員變量，分析優(yōu)先隊循環(huán)雙鏈表作為優(yōu)先隊列的成員變量，分析優(yōu)先隊列的入隊和出隊操作的效率。列的入隊和出隊操作的效率。 數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 35習(xí)題習(xí)題4-13 優(yōu)先隊列優(yōu)先隊列優(yōu)先隊列，分別使用各種線性表。優(yōu)先隊列，分別使用各種線性表。(E,4), (D,3), (A,1), (F,3), (B,2), (C,

18、1)習(xí)題解答習(xí)題解答數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 36習(xí)題習(xí)題4-13數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 37優(yōu)先隊列類優(yōu)先隊列類PriorityQueueT extends Comparable /優(yōu)先隊列類（升或降），最終類，實現(xiàn)隊列接口，優(yōu)先隊列類（升或降），最終類，實現(xiàn)隊列接口，T是元素類型是元素類型public final class PriorityQueueT extends Comparable implements Queue private SortedCirDoublyList list; /排序循環(huán)雙鏈表排序循環(huán)雙鏈表 private boolean as

19、c; /asc指定升序（指定升序（true）或降序）或降序 public PriorityQueue(boolean asc) /構(gòu)造空隊列構(gòu)造空隊列 public PriorityQueue() /構(gòu)造空隊列，默認(rèn)升序構(gòu)造空隊列，默認(rèn)升序 public boolean isEmpty(); /判空判空 public boolean add(T x); /x入隊入隊 public T peek(); /返回隊頭，沒有刪除返回隊頭，沒有刪除 public T poll(); /出隊，返回隊頭出隊，返回隊頭數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 38【例例4.4】 進(jìn)程按優(yōu)先級調(diào)度管理進(jìn)程按優(yōu)先級

20、調(diào)度管理/進(jìn)程類進(jìn)程類public class Process implements Comparable private String name; /進(jìn)程名進(jìn)程名 private int priority; /優(yōu)先級優(yōu)先級 public Process(String name, int priority) public Process(String name) public String toString() public int compareTo(Process p)數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 391. 遞歸定義遞歸定義2. 遞歸算法遞歸算法 f(n)=nf(n-1)【思考題

21、思考題4-4】public static int factorial(int n) /求求階乘階乘n!，遞歸方法，遞歸方法 4.3 遞歸遞歸10,1!(1)! 2nnnnn數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 40【思考題思考題4-4】求階乘求階乘n!public static int factorial(int n) /遞歸方法遞歸方法 if (n0) /拋出無效參數(shù)異常拋出無效參數(shù)異常 throw new IllegalArgumentException(n=+n); if (n=0 | n=1) /邊界條件，遞歸結(jié)束條件邊界條件，遞歸結(jié)束條件 return 1; return n*fa

22、ctorial(n-1); /遞歸調(diào)用，遞推通式遞歸調(diào)用，遞推通式數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 41【例例4.5】 求求Fibonacci序列。序列。0,1( )(1)(2) 2nnf nf nf nn數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 42打印數(shù)字塔打印數(shù)字塔 public static void line(int i) if (i10) line(i+1); System.out.print(String.format(%3d,i);執(zhí)行執(zhí)行l(wèi)ine(1)結(jié)果？結(jié)果？輸出輸出10 9 8 7 6 5 4 3 2 1數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 43習(xí)題解答例習(xí)題解答

23、例4.1 打印數(shù)字塔打印數(shù)字塔 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 4 5 6 5 4 3 2 1 1 2 3 4 5 6 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 44【例例4.6】計算算術(shù)表達(dá)式的值，計算算術(shù)表達(dá)式的值，遞歸算法。遞歸算法。 算術(shù)表達(dá)式算術(shù)表達(dá)式 項項項項項項項項項項項項 因子因子因子因子因子因子因子因子因子因子 因子因子%因子因子因子因子 常數(shù)常

24、數(shù)（算術(shù)表達(dá)式算術(shù)表達(dá)式）整數(shù)整數(shù) 數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字整數(shù)整數(shù)數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字 0123456789數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 45算術(shù)表達(dá)式語法圖算術(shù)表達(dá)式語法圖 數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 46算術(shù)表達(dá)式類算術(shù)表達(dá)式類ArithmeticExpression /算術(shù)表達(dá)式（整數(shù)、不包括位運(yùn)算）算術(shù)表達(dá)式（整數(shù)、不包括位運(yùn)算）public class ArithmeticExpression private String infix; /中綴算術(shù)表達(dá)式中綴算術(shù)表達(dá)式 private int index; /當(dāng)前字符序號當(dāng)前字符序號 public Arithmet

25、icExpression(String infix) public int intValue() /計算表達(dá)式，返回整數(shù)計算表達(dá)式，返回整數(shù) private int term() /計算計算項項 private int factor() /計算計算因子因子 private int constant() /計算計算常數(shù)常數(shù)數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4章 473. 單鏈表的遞歸算法單鏈表的遞歸算法 （1）遍歷單鏈表的遞歸算法）遍歷單鏈表的遞歸算法 public String toString() return ( + this.toString(this.head.next) + );private String toString(Node p) /遞歸算法遞歸算法 if (p=null) return ; /遞歸結(jié)束條件遞歸結(jié)束條件 String str=p.data.toString(); if (p.next!=null) str+=, ; return str+toString(p.next); /遞歸調(diào)用遞歸調(diào)用數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）第4