數(shù)據(jù)結(jié)構(gòu)Java版第4章棧與隊(duì)列

1、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（Java版）版）葉核亞葉核亞數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（Java版）版） 第1章 緒論 第2章 線性表 第3章 排序第4章 棧與隊(duì)列 第5章 數(shù)組和廣義表 第6章 樹和二叉樹 第7章 查找 第8章 圖 第9章 綜合應(yīng)用設(shè)計(jì)第4章 棧與隊(duì)列 棧和隊(duì)列是兩種特殊的線性表。與線性表一樣，棧和隊(duì)列的數(shù)據(jù)元素之間具有順序的邏輯關(guān)系，都可以采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；與線性表不同的是，線性表的插入和刪除操作不受限制，可以在任意位置進(jìn)行，而棧和隊(duì)列的插入和刪除操作受到限制，棧的插入和刪除操作只允許在線性表的一端進(jìn)行，而隊(duì)列的插入和刪除操作則分別在線性表的兩端進(jìn)行。 棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的

2、特點(diǎn)是先進(jìn)先出，兩者在實(shí)際問(wèn)題中有著廣泛的應(yīng)用。 4.1 棧 4.2 隊(duì)列 4.3 遞歸數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4.1 棧n4.1.1 棧的定義n4.1.2 棧的抽象數(shù)據(jù)類型n4.1.3 棧的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)n4.1.4 棧的應(yīng)用舉例數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4.1.1 棧的定義n棧（stack）是一種特殊的線性表，其插入和刪除操作只允許在線性表的一端進(jìn)行。n允許操作一端稱為棧頂（top），不允許操作的一端稱為棧底（bottom）。n棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)的，標(biāo)識(shí)棧頂當(dāng)前位置的變量稱為棧頂指針。n棧中插入數(shù)據(jù)元素的過(guò)程稱為入棧（push），刪除數(shù)據(jù)元素的過(guò)程稱為出棧（pop）。n當(dāng)棧中沒(méi)有數(shù)

3、據(jù)元素時(shí)稱之為空棧。圖4.1 棧結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4.1.2 棧的抽象數(shù)據(jù)類型1棧的數(shù)據(jù)元素 2棧的基本操作n棧的初始化，設(shè)置棧狀態(tài)為空。n判斷棧的狀態(tài)是否為空。n判斷棧的狀態(tài)是否已滿。n入棧：將數(shù)據(jù)元素插入棧中作為新的棧頂數(shù)據(jù)元素的過(guò)程。在入棧之前必須判斷棧的狀態(tài)是否已滿，如果棧不滿，則接收新數(shù)據(jù)元素入棧，否則產(chǎn)生上溢錯(cuò)誤（overflow）。n出棧：取出當(dāng)前棧頂數(shù)據(jù)元素，下一個(gè)數(shù)據(jù)元素成為新的棧頂數(shù)據(jù)元素的過(guò)程。在出棧之前，必須判斷棧的狀態(tài)是否為空。如果棧的狀態(tài)為空，產(chǎn)生下溢錯(cuò)誤（underflow）。n獲得棧頂數(shù)據(jù)元素，此時(shí)該數(shù)據(jù)元素未出棧。數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞棧的

4、接口StackInterfacepackage ds_java;public interface StackInterface /棧的接口 public boolean isEmpty(); /判斷棧的狀態(tài)是否為空 public boolean isFull(); /判斷棧的狀態(tài)是否已滿 public boolean push(Object k); /k對(duì)象入棧 public Object pop(); /出棧 public Object get(); /獲得棧頂元素，未出棧數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4.1.3 棧的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)1棧的順序存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)package ds_java;i

5、mport ds_java.StackInterface;public class Stack1 implements StackInterface /棧的順序存儲(chǔ)結(jié)構(gòu) private Object table; private final int empty=-1; /聲明整數(shù)常量 private int top=empty; /top為棧頂元素下標(biāo)數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞順序棧的操作實(shí)現(xiàn) （1）棧的初始化構(gòu)造方法申請(qǐng)table數(shù)組的存儲(chǔ)空間準(zhǔn)備存放棧的數(shù)據(jù)元素，設(shè)置棧初始狀態(tài)為空。算法如下： public Stack1(int n) /帶參數(shù)時(shí)，構(gòu)造具有n個(gè)存儲(chǔ)單元的空棧 table=

6、new Objectn; top=empty; /設(shè)置棧初始狀態(tài)為空 public Stack1() /不帶參數(shù)時(shí)，構(gòu)造具有10個(gè)存儲(chǔ)單元的空棧 this(10); （2）判斷棧狀態(tài)是否為空 public boolean isEmpty() /判斷棧的狀態(tài)是否為空 數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞【例4.1】 使用順序棧的基本操作import ds_java.Stack1;class Stack1_ex public static void main(String args) int i=0,n=4; Stack1 s1=new Stack1(20); System.out.print(Push:

7、 ); while(i0) /有參數(shù)時(shí)， expstr1=args0; /獲得表達(dá)式字符串 System.out.println(expstr1+ isValid +isValid(expstr1); public static String isValid(String expstr) Stack1 s1=new Stack1(30); /創(chuàng)建空棧 char ch; int i=0;數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞判斷表達(dá)式中括號(hào)是否匹配的算法描述 數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4.2 隊(duì)列n4.2.1 隊(duì)列的定義n4.2.2 隊(duì)列的抽象數(shù)據(jù)類型n4.2.3 隊(duì)列的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)n4.2.4 隊(duì)列

8、的應(yīng)用舉例數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4.2.1 隊(duì)列的定義n隊(duì)列（queue）是一種特殊的線性表，其插入和刪除操作分別在線性表的兩端進(jìn)行。n向隊(duì)列中插入元素的過(guò)程稱為入隊(duì)（enqueue），刪除元素的過(guò)程稱為出隊(duì)（dequeue）。n允許入隊(duì)的一端為隊(duì)尾（rear），允許出隊(duì)的一端為隊(duì)頭（front）。標(biāo)識(shí)隊(duì)頭和隊(duì)尾當(dāng)前位置的變量稱為隊(duì)頭指針和隊(duì)尾指針。n當(dāng)隊(duì)列中沒(méi)有數(shù)據(jù)元素時(shí)稱作空隊(duì)列。數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4.2.2 隊(duì)列的抽象數(shù)據(jù)類型1隊(duì)列的數(shù)據(jù)元素2隊(duì)列的基本操作n隊(duì)列的初始化，設(shè)置隊(duì)列狀態(tài)為空。n判斷隊(duì)列的狀態(tài)是否為空。n判斷隊(duì)列的狀態(tài)是否已滿。n入隊(duì)：將數(shù)據(jù)元素從隊(duì)尾處加入

9、隊(duì)列的過(guò)程。在入隊(duì)之前必須判斷隊(duì)列的狀態(tài)是否已滿，如果隊(duì)列不滿，則接收新數(shù)據(jù)元素入隊(duì)，隊(duì)列滿時(shí)數(shù)據(jù)元素不能入隊(duì)，產(chǎn)生上溢錯(cuò)誤（overflow）。n出隊(duì)：從隊(duì)頭處取出數(shù)據(jù)元素的過(guò)程。在出隊(duì)之前，必須判斷隊(duì)列的狀態(tài)是否為空。隊(duì)列空時(shí)，取不到元素，產(chǎn)生下溢錯(cuò)誤（underflow）。數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞隊(duì)列的接口QueueInterfacepackage ds_java;public interface QueueInterface /隊(duì)列的接口 public boolean isEmpty(); /判斷隊(duì)列狀態(tài)是否為空 public boolean isFull(); /判斷隊(duì)列狀態(tài)是否

10、已滿 public boolean enqueue(Object k); /k對(duì)象入隊(duì) public Object dequeue(); /出隊(duì) 數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4.2.3 隊(duì)列的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)1隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)10203001234frontrear304001234frontrear(b) 隊(duì)列的“假溢出”(a) 以數(shù)組存儲(chǔ)隊(duì)列的數(shù)據(jù)元素50數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞2順序循環(huán)隊(duì)列及操作實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞順序循環(huán)隊(duì)列的操作實(shí)現(xiàn) package ds_java;import ds_java.QueueInterface;public class Queue1 i

11、mplements QueueInterface/順序循環(huán)隊(duì)列 private Object table; private int front,rear; /front和rear為隊(duì)列頭尾下標(biāo)Queue1類的一個(gè)對(duì)象就是一個(gè)隊(duì)列。隊(duì)列數(shù)據(jù)元素的類型是Object。順序循環(huán)隊(duì)列的操作實(shí)現(xiàn)如下，這些算法寫在Queue1類中，作為Queue1類的方法。（1）隊(duì)列的初始化構(gòu)造方法申請(qǐng)table數(shù)組的存儲(chǔ)空間準(zhǔn)備存放隊(duì)列數(shù)據(jù)元素，設(shè)置隊(duì)列初始狀態(tài)為空，即front =0且rear=0。算法如下： public Queue1(int n) /構(gòu)造長(zhǎng)度為n的空隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞【例4.4】

12、使用順序循環(huán)隊(duì)列的基本操作。import ds_java.Queue1;class Queue1_ex public static void main(String args) int i=0,n=2; Queue1 q1=new Queue1(20); while(iargs.length) q1.enqueue(argsi); /入隊(duì) System.out.print(Enqueue: +argsi+t); q1.output(); i+; for(i=0;in;i+)數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)n隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以單向鏈表實(shí)現(xiàn)，設(shè)front和rear分別指

13、向隊(duì)頭和隊(duì)尾結(jié)點(diǎn)。 1 2 1 frontrear(c) 一個(gè)元素入隊(duì)(a) 設(shè)置隊(duì)列為空f(shuō)ront=nullrear=null(b) 第一個(gè)元素入隊(duì)data nextfrontrearrear 1 2 front(d) 一個(gè)元素出隊(duì)rear(e) 最后一個(gè)元素出隊(duì)后，隊(duì)列狀態(tài)為空f(shuō)ront=null rear=nullfront數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞鏈?zhǔn)疥?duì)列的基本操作實(shí)現(xiàn) package ds_java;import ds_java.OnelinkNode;import ds_java.Onelink1;public class Queue2 extends Onelink1/隊(duì)列的鏈

14、式存儲(chǔ)結(jié)構(gòu) private OnelinkNode front,rear;Queue2類的一個(gè)對(duì)象就是一個(gè)隊(duì)列。其中，成員變量front和rear分別指向隊(duì)頭和隊(duì)尾結(jié)點(diǎn)，結(jié)點(diǎn)類型為單向鏈表的結(jié)點(diǎn)類OnelinkNode，結(jié)點(diǎn)數(shù)據(jù)域的類型為int。鏈?zhǔn)疥?duì)列的基本操作實(shí)現(xiàn)如下，這些算法寫在Queue2類中，作為Queue2類的方法。（1）隊(duì)列的初始化構(gòu)造方法創(chuàng)建一條單向鏈表用做隊(duì)列，設(shè)置隊(duì)列狀態(tài)為空鏈表。算法如下： public Queue2() /構(gòu)造空隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4.2.4 隊(duì)列的應(yīng)用舉例n1處理等待問(wèn)題時(shí)系統(tǒng)設(shè)立隊(duì)列n隊(duì)列具有“先進(jìn)先出”的特性，當(dāng)需要按一定次序等待時(shí)，

15、系統(tǒng)需設(shè)立一個(gè)隊(duì)列。2實(shí)現(xiàn)廣度遍歷算法時(shí)使用隊(duì)列n實(shí)現(xiàn)廣度遍歷算法，如按層次遍歷二叉樹、以廣度優(yōu)先算法遍歷圖，都需要使用隊(duì)列。詳細(xì)算法將在以后的章節(jié)中介紹。數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞【例4.5】 解素?cái)?shù)環(huán)問(wèn)題。將n個(gè)數(shù)（1n）排列成環(huán)形，使得每相鄰兩數(shù)之和為素?cái)?shù)，構(gòu)成一個(gè)素?cái)?shù)環(huán)。import ds_java.Queue2; /引用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列，元素為int型import ds_java.LinearList1; /引用順序存儲(chǔ)結(jié)構(gòu)的線性表public class Primering /求素?cái)?shù)環(huán) public static boolean isPrime(int k) /判斷k是否為素?cái)?shù)

16、 int j=2; if(k=2) return true; if(k2 & k%2=0) return false; else 數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4.3 遞歸1問(wèn)題的定義是遞歸的2算法是遞歸的n如果能夠分解成幾個(gè)相對(duì)簡(jiǎn)單且解法相同或類似的子問(wèn)題時(shí)，只要解決了子問(wèn)題，那么原問(wèn)題就迎刃而解，這就是遞歸求解。例如，5！=54！。n當(dāng)分解后的子問(wèn)題可以直接解決時(shí)，就停止分解。這些可以直接求解的問(wèn)題稱為遞歸結(jié)束條件。例如，1！=1。n根據(jù)遞歸定義，編寫能夠直接反映遞歸定義的遞歸函數(shù)來(lái)求解。2)!1(1 , 01!nnnnn2)2() 1(10)(nnfnfnnnf，數(shù)據(jù)結(jié)構(gòu)（Java版）葉核

17、亞【例4.6】 求n！。public class Factorial static int f(int n) /遞歸方法 if(n=0 | n=1) return 1; else System.out.println(n+!=+n+*+(n-1)+!); return n*f(n-1); public static void main(String args) int i=5;數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞【例4.7】 打印數(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

18、 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 題目本身雖不是遞歸定義的，但可以用遞歸算法求解。程序如下：public class Dig9_r static void count(int i,int n) /遞歸方法 if(in)數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞3數(shù)據(jù)結(jié)構(gòu)是遞歸的n將單向鏈表結(jié)點(diǎn)類的next鏈與指向鏈表第1個(gè)結(jié)點(diǎn)的head遞歸定義為：指向一個(gè)單向鏈表非指向一個(gè)空鏈表及nullnullheadnext data nexthead(b) 單向鏈表head=null(a) 空鏈表數(shù)據(jù)結(jié)構(gòu)（Java版）