资料结构简介课件

14.4佇列cba入口出口尾端(rear)頭端(front)cb出口尾端(rear)頭端(front)入口dcb尾端(rear)頭端(front)入口特徵：刪除新增d14.4佇列cba入口出口尾端(rear)頭端(fron24.4.1以陣列實作佇列224.4.1以陣列實作佇列234.4.1以陣列實作佇列—移動門(ch4_queue_1.java)優點：簡單缺點：還有空位卻認為已滿解決方法：當有remove動作時，搬移資料，讓剩下的所有佇列資料都由陣列索引位置0開始

或參考4.5.5環狀佇列適用於限量服務，不適合不限量、但座位有限的服務34.4.1以陣列實作佇列—移動門(ch4_queue_44.4.2以串列實作佇列(ch4_queue_2.java)

classNode{intdata;Nodelink;}classQueue{Nodefront;Noderear;}44.4.2以串列實作佇列(ch4_queue_2.java54.4.2以串列實作佇列(ch4_queue_2.java)範例ch4_queue_2.java未處理54.4.2以串列實作佇列(ch4_queue_2.java64.4.2以串列實作佇列(ch4_queue_2.java)基本動作如下：建立一個空佇列：生成front跟rear節點，而且兩者的link都是nullvoidadd(intdata):生成新節點，將data值存在此節點，依佇列是否為空，分別處理(第4頁投影片)intremove():刪除並傳回佇列頭端資料intgetfront():傳回頭端資料intgetrear():傳回尾端資料booleanempty():傳回佇列是否為空之布林值練習：intgetlength()：傳回長度如果想以串列實作，但又要限制佇列長度(最多為n)，則可以檢查getlength()是否等於n，來判斷是否佇列已滿64.4.2以串列實作佇列(ch4_queue_2.java7784.5變形堆疊和變形佇列4.5.1,4.5.2多重堆疊，多重佇列[課本這兩節跳過]課本：將一陣列切成3段，每段實作一堆疊(佇列)，當某一堆疊(佇列)滿了，其他堆疊(佇列)還有空間時，需重新分配，處理起來太複雜。其實可以用之前設計之Stack或Queue來實作。重新設計：classThreeStack{Stacks1;Stacks2;Stacks3;ints1_max_size;//optionalints2_max_size;//optionalints3_max_size;//optionalvoidpush(inti,intdata)intpop(inti)booleanfull(inti)booleanempty(inti)}classThreeQueue{Queueq1;Queueq2;Queueq3;intq1_max_size;//optionalintq2_max_size;//optionalintq3_max_size;//optionalvoidadd(inti,intdata)intremove(inti)boolanfull(inti)booleanempty(inti)}如果對堆疊容量有設限84.5變形堆疊和變形佇列4.5.1,4.5.2多重堆4.5.1,4.5.2多重堆疊，多重佇列(重新設計，補充)其方法(以多重堆疊為例：ch4_threestack.java)建構子:初始化3個堆疊voidpush(inti,intdata)：新增資料data到第i個堆疊intpop(inti):由第i個堆疊取出資料(要移除)booleanfull(inti):檢查第i個堆疊是否滿了(對堆疊容量有設限時才需要)booleanempty(inti)：檢查第i個堆疊是否為空也可擴充為可變長度之多重堆疊(ch4_MultiStack.java)建構子：以整數陣列代表需要新增的堆疊的各個長度限制94.5.1,4.5.2多重堆疊，多重佇列(重新設計，補充104.5.3優先佇列課本作法1：將一陣列切成3段，每段實作一佇列，由左到右分級課本作法2：以鍊結串列104.5.3優先佇列課本作法1：將一陣列切成3段，114.5.3優先佇列(補充)重新設計:視為一個佇列，由3個佇列實作，新增時可設定要加入第幾個佇列。移除時會由q1,q2,q3依續移除classPriorityQueue{Queueq1;Queueq2;Queueq3;intq1_max_size;intq2_max_size;intq3_max_size;voidadd(inti,intdata)intremove()boolanfull()booleanempty()}常用於服務有分等級時，例如q1為頭等艙旅客，q2為商務艙旅客，q3為經濟艙旅客。add表示旅客到達櫃台排隊。remove表示請排在最前面旅客到櫃台接受服務(但需依照等級)練習：請畫出經過以下動作後，各佇列內容：add(1,1)、add(2,2)、add(3,3)、add(2,4)、remove()、remove()、remove()、add(1,5)、remove()114.5.3優先佇列(補充)重新設計:視為一個佇列，124.5.4雙向佇列(DQueue)課本：將一個陣列切成2半重新設計classDQueue{Queueq1;Queueq2;intmax_size;//兩個佇列長度和voidadd(inti,intdata)intremove(inti)boolanfull()booleanempty(){returnq1.empty()&&q2.empty();}}124.5.4雙向佇列(DQueue)課本：將一個陣列切134.5.5以陣列實作環狀佇列(ch4_cqueue.java)4.4.1

以陣列實作佇列的缺點改進的想法：當有remove動作時，搬移資料，讓剩下的所有佇列資料都由陣列索引位置0開始(作業)將陣列的頭尾相接，以利用空出來的位置134.5.5以陣列實作環狀佇列(ch4_cqueue.ja4.5.5環狀佇列(ch4_cqueue.java)144.5.5環狀佇列(ch4_cqueue.java)144.5.5環狀佇列154.5.5環狀佇列151616練習為了使用陣列來實作不限量、但座位有限的佇列服務，請改進ch4_queue_1.java還有空位卻認為已滿的缺點，當有remove動作時，搬移陣列資料，讓剩下的所有佇列資料都由陣列索引位置0開始(由於以上這個特性，這樣的佇列不需要front)。請改寫ch4_queue_1.java所有方法，並加以測試。請以堆疊陣列完成可變長度之多重堆疊的相關方法，並加以測試完成優先佇列的相關方法，並加以測試17練習為了使用陣列來實作不限量、但座位有限的佇列服務，請改進184.4佇列cba入口出口尾端(rear)頭端(front)cb出口尾端(rear)頭端(front)入口dcb尾端(rear)頭端(front)入口特徵：刪除新增d14.4佇列cba入口出口尾端(rear)頭端(fron194.4.1以陣列實作佇列1924.4.1以陣列實作佇列2204.4.1以陣列實作佇列—移動門(ch4_queue_1.java)優點：簡單缺點：還有空位卻認為已滿解決方法：當有remove動作時，搬移資料，讓剩下的所有佇列資料都由陣列索引位置0開始

或參考4.5.5環狀佇列適用於限量服務，不適合不限量、但座位有限的服務34.4.1以陣列實作佇列—移動門(ch4_queue_214.4.2以串列實作佇列(ch4_queue_2.java)

classNode{intdata;Nodelink;}classQueue{Nodefront;Noderear;}44.4.2以串列實作佇列(ch4_queue_2.java224.4.2以串列實作佇列(ch4_queue_2.java)範例ch4_queue_2.java未處理54.4.2以串列實作佇列(ch4_queue_2.java234.4.2以串列實作佇列(ch4_queue_2.java)基本動作如下：建立一個空佇列：生成front跟rear節點，而且兩者的link都是nullvoidadd(intdata):生成新節點，將data值存在此節點，依佇列是否為空，分別處理(第4頁投影片)intremove():刪除並傳回佇列頭端資料intgetfront():傳回頭端資料intgetrear():傳回尾端資料booleanempty():傳回佇列是否為空之布林值練習：intgetlength()：傳回長度如果想以串列實作，但又要限制佇列長度(最多為n)，則可以檢查getlength()是否等於n，來判斷是否佇列已滿64.4.2以串列實作佇列(ch4_queue_2.java247254.5變形堆疊和變形佇列4.5.1,4.5.2多重堆疊，多重佇列[課本這兩節跳過]課本：將一陣列切成3段，每段實作一堆疊(佇列)，當某一堆疊(佇列)滿了，其他堆疊(佇列)還有空間時，需重新分配，處理起來太複雜。其實可以用之前設計之Stack或Queue來實作。重新設計：classThreeStack{Stacks1;Stacks2;Stacks3;ints1_max_size;//optionalints2_max_size;//optionalints3_max_size;//optionalvoidpush(inti,intdata)intpop(inti)booleanfull(inti)booleanempty(inti)}classThreeQueue{Queueq1;Queueq2;Queueq3;intq1_max_size;//optionalintq2_max_size;//optionalintq3_max_size;//optionalvoidadd(inti,intdata)intremove(inti)boolanfull(inti)booleanempty(inti)}如果對堆疊容量有設限84.5變形堆疊和變形佇列4.5.1,4.5.2多重堆4.5.1,4.5.2多重堆疊，多重佇列(重新設計，補充)其方法(以多重堆疊為例：ch4_threestack.java)建構子:初始化3個堆疊voidpush(inti,intdata)：新增資料data到第i個堆疊intpop(inti):由第i個堆疊取出資料(要移除)booleanfull(inti):檢查第i個堆疊是否滿了(對堆疊容量有設限時才需要)booleanempty(inti)：檢查第i個堆疊是否為空也可擴充為可變長度之多重堆疊(ch4_MultiStack.java)建構子：以整數陣列代表需要新增的堆疊的各個長度限制264.5.1,4.5.2多重堆疊，多重佇列(重新設計，補充274.5.3優先佇列課本作法1：將一陣列切成3段，每段實作一佇列，由左到右分級課本作法2：以鍊結串列104.5.3優先佇列課本作法1：將一陣列切成3段，284.5.3優先佇列(補充)重新設計:視為一個佇列，由3個佇列實作，新增時可設定要加入第幾個佇列。移除時會由q1,q2,q3依續移除classPriorityQueue{Queueq1;Queueq2;Queueq3;intq1_max_size;intq2_max_size;intq3_max_size;voidadd(inti,intdata)intremove()boolanfull()booleanempty()}常用於服務有分等級時，例如q1為頭等艙旅客，q2為商務艙旅客，q3為經濟艙旅客。add表示旅客到達櫃台排隊。remove表示請排在最前面旅客到櫃台接受服務(但需依照等級)練習：請畫出經過以下動作後，各佇列內容：add(1,1)、add(2,2)、add(3,3)、add(2,4)、remove()、remove()、remove()、add(1,5)、remove()114.5.3優先佇列(補充)重新設計:視為一個佇列，294.5.4雙向佇列(DQueue)課本：將一個陣列切成2半重新設計classDQueue{Queueq1;Queueq2;intmax