资料结构简介课件.ppt

1、14.4 佇列cba入口入口出口出口尾端尾端(rear)頭端頭端(front)cb出口出口尾端尾端(rear)頭端頭端(front)入口入口dcb尾端尾端(rear)頭端頭端(front)入口入口特徵：刪除刪除新增新增 d24.4.1 以陣列實作佇列234.4.1 以陣列實作佇列移動門(ch4_queue_1.java)優點：簡單缺點：還有空位卻認為已滿解決方法：當有 remove 動作時，搬移資料，讓剩下的所有佇列資料都由陣列索引位置 0 開始 或參考 4.5.5 環狀 佇列適用於限量服務，不適合不限量、但座位有限的服務44.4.2以串列實作佇列(ch4_queue_2.java)class

2、 Node int data;Node link;class Queue Node front;Node rear;54.4.2以串列實作佇列(ch4_queue_2.java)範例 ch4_queue_2.java 未處理64.4.2以串列實作佇列(ch4_queue_2.java)基本動作如下：1.建立一個 空佇列：生成 front 跟 rear 節點，而且兩者的 link 都是 null2.void add(int data):生成新節點，將 data 值存在此節點，依佇列是否為空，分別處理(第 4 頁投影片)3.int remove():刪除並傳回佇列頭端資料4.int getfron

3、t():傳回頭端資料5.int getrear():傳回尾端資料6.boolean empty():傳回佇列是否為空之布林值練習：int getlength()：傳回長度如果想以串列實作，但又要限制佇列長度(最多為 n)，則可以檢查 getlength()是否等於 n，來判斷是否佇列已滿784.5 變形堆疊和變形佇列4.5.1,4.5.2 多重堆疊，多重佇列 課本這兩節跳過課本：將一陣列切成 3 段，每段實作一堆疊(佇列)，當某一堆疊(佇列)滿了，其他堆疊(佇列)還有空間時，需重新分配，處理起來太複雜。其實可以用之前設計之 Stack 或 Queue 來實作。重新設計：class ThreeS

4、tack Stack s1;Stack s2;Stack s3;int s1_max_size;/optional int s2_max_size;/optional int s3_max_size;/optional void push(int i,int data)int pop(int i)boolean full(int i)boolean empty(int i)class ThreeQueue Queue q1;Queue q2;Queue q3;int q1_max_size;/optional int q2_max_size;/optional int q3_max_size;

5、/optional void add(int i,int data)int remove(int i)boolan full(int i)boolean empty(int i)如果對堆疊容量有設限4.5.1,4.5.2 多重堆疊，多重佇列(重新設計，補充)其方法(以多重堆疊為例：ch4_threestack.java)建構子:初始化 3 個堆疊void push(int i,int data)：新增資料 data 到第 i 個堆疊int pop(int i):由第 i 個堆疊取出資料(要移除)boolean full(int i):檢查第 i 個堆疊是否滿了(對堆疊容量有設限時才需要)boo

6、lean empty(int i)：檢查第 i 個堆疊是否為空 也可擴充為可變長度之多重堆疊(ch4_MultiStack.java)建構子：以整數陣列代表需要新增的堆疊的各個長度限制9104.5.3 優先佇列課本作法 1：將一陣列切成 3 段，每段實作一佇列，由左到右分級課本作法 2：以鍊結串列114.5.3 優先佇列(補充)重新設計:視為一個佇列，由 3 個佇列實作，新增時可設定要加入第幾個佇列。移除時會由 q1,q2,q3 依續移除class PriorityQueue Queue q1;Queue q2;Queue q3;int q1_max_size;int q2_max_size;

7、int q3_max_size;void add(int i,int data)int remove()boolan full()boolean empty()常用於服務有分等級時，例如 q1 為頭等艙旅客，q2 為商務艙旅客，q3 為經濟艙旅客。add 表示旅客到達櫃台排隊。remove 表示請排在最前面旅客到櫃台接受服務(但需依照等級)練習：請畫出經過以下動作後，各佇列內容：add(1,1)、add(2,2)、add(3,3)、add(2,4)、remove()、remove()、remove()、add(1,5)、remove()124.5.4 雙向佇列(DQueue)課本：將一個陣列切

8、成 2 半重新設計class DQueue Queue q1;Queue q2;int max_size;/兩個佇列長度和 void add(int i,int data)int remove(int i)boolan full()boolean empty()return q1.empty()&q2.empty();134.5.5以陣列實作環狀佇列(ch4_cqueue.java)4.4.1 以陣列實作佇列的缺點改進的想法：1.當有 remove 動作時，搬移資料，讓剩下的所有佇列資料都由陣列索引位置 0 開始(作業)2.將陣列的頭尾相接，以利用空出來的位置4.5.5 環狀佇列(ch4_cqueue.java)144.5.5 環狀佇列1516練習 1.為了使用陣列來實作不限量、但座位有限的佇列服務，請改進 ch4_queue_1.java 還有空位卻認為已滿的缺點，當有 remove 動作時，搬移陣列資料，讓剩下的所有佇列資料都由陣列索引位置 0 開始(由於以上這個特性，這樣的佇列不需要 front)。請改寫 ch4_queue_1.java 所有方法，並加以測試。2.請以堆疊陣列完成 可變長度之多重堆疊的相關方法，並加以測試3.完成 優先佇列的相關方法，並加以測試17