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章 棧與隊列 第5章 數(shù)組和廣義表 第6章 樹和二叉樹 第7章 查找 第8章 圖 第9章 綜合應(yīng)用設(shè)計第4章 棧與隊列 棧和隊列是兩種特殊的線性表。與線性表一樣，棧和隊列的數(shù)據(jù)元素之間具有順序的邏輯關(guān)系，都可以采用順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)；與線性表不同的是，線性表的插入和刪除操作不受限制，可以在任意位置進行，而棧和隊列的插入和刪除操作受到限制，棧的插入和刪除操作只允許在線性表的一端進行，而隊列的插入和刪除操作則分別在線性表的兩端進行。 棧的特點是后進先出，隊列的

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

3、據(jù)元素時稱之為空棧。圖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ù)元素的過程。在入棧之前必須判斷棧的狀態(tài)是否已滿，如果棧不滿，則接收新數(shù)據(jù)元素入棧，否則產(chǎn)生上溢錯誤（overflow）。n出棧：取出當前棧頂數(shù)據(jù)元素，下一個數(shù)據(jù)元素成為新的棧頂數(shù)據(jù)元素的過程。在出棧之前，必須判斷棧的狀態(tài)是否為空。如果棧的狀態(tài)為空，產(chǎn)生下溢錯誤（underflow）。n獲得棧頂數(shù)據(jù)元素，此時該數(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對象入棧 public Object pop(); /出棧 public Object get(); /獲得棧頂元素，未出棧數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4.1.3 棧的存儲結(jié)構(gòu)及實現(xiàn)1棧的順序存儲結(jié)構(gòu)及操作實現(xiàn)package ds_java;i

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

6、new Objectn; top=empty; /設(shè)置棧初始狀態(tài)為空 public Stack1() /不帶參數(shù)時，構(gòu)造具有10個存儲單元的空棧 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ù)時， expstr1=args0; /獲得表達式字符串 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版）葉核亞判斷表達式中括號是否匹配的算法描述 數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4.2 隊列n4.2.1 隊列的定義n4.2.2 隊列的抽象數(shù)據(jù)類型n4.2.3 隊列的存儲結(jié)構(gòu)及實現(xiàn)n4.2.4 隊列

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

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

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

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

12、使用順序循環(huán)隊列的基本操作。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); /入隊 System.out.print(Enqueue: +argsi+t); q1.output(); i+; for(i=0;in;i+)數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞3隊列的鏈式存儲結(jié)構(gòu)及操作實現(xiàn)n隊列的鏈式存儲結(jié)構(gòu)以單向鏈表實現(xiàn)，設(shè)front和rear分別指

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

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

15、系統(tǒng)需設(shè)立一個隊列。2實現(xiàn)廣度遍歷算法時使用隊列n實現(xiàn)廣度遍歷算法，如按層次遍歷二叉樹、以廣度優(yōu)先算法遍歷圖，都需要使用隊列。詳細算法將在以后的章節(jié)中介紹。數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞【例4.5】 解素數(shù)環(huán)問題。將n個數(shù)（1n）排列成環(huán)形，使得每相鄰兩數(shù)之和為素數(shù)，構(gòu)成一個素數(shù)環(huán)。import ds_java.Queue2; /引用鏈式存儲結(jié)構(gòu)的隊列，元素為int型import ds_java.LinearList1; /引用順序存儲結(jié)構(gòu)的線性表public class Primering /求素數(shù)環(huán) public static boolean isPrime(int k) /判斷k是否為素數(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問題的定義是遞歸的2算法是遞歸的n如果能夠分解成幾個相對簡單且解法相同或類似的子問題時，只要解決了子問題，那么原問題就迎刃而解，這就是遞歸求解。例如，5！=54！。n當分解后的子問題可以直接解決時，就停止分解。這些可以直接求解的問題稱為遞歸結(jié)束條件。例如，1！=1。n根據(jù)遞歸定義，編寫能夠直接反映遞歸定義的遞歸函數(shù)來求解。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é)點類的next鏈與指向鏈表第1個結(jié)點的head遞歸定義為：指向一個單向鏈表非指向一個空鏈表及nullnullheadnext data nexthead(b) 單向鏈表head=null(a) 空鏈表數(shù)據(jù)結(jié)構(gòu)（Java版）