進階佇列.

Presentation on theme: "進階佇列."— Presentation transcript:

1 進階佇列

2 環狀佇列 (Circular Queue)

3 定義 以一維陣列Q(0 To n-1)表示一個環狀佇列 指標front永遠以逆時鐘方向指向佇列前端元素的前一個位置
指標Rear則指向佇列尾端的元素

4 資料之加入和刪除 資料是加入到rear = (rear+1) mod n 的陣 列位置
刪除動作是刪掉陣列front = (front +1) mod n

5 環狀佇列的問題 其實環形佇列還剩餘一個空間可以使用，但是這是為了判斷以下的情形而預留的，不可使用：
佇列已空 q.rear =q.front 佇列已滿 q.rear =q.front 因此最多只能使用n-1個空間，而浪費一個空間。

6 環狀佇列已空或佇列已滿之判別條件皆為q.rear =q.front
容易產生模擬兩可的情形，如何修正改進這個兩個缺點呢？ 修正演算法 問題：如何區分佇列已空或佇列已滿 方法：修改環狀佇列已空或佇列已滿之條件 佇列已空之充要條件 q.rear = q.front 成立 佇列已滿之充要條件 q.front = (q.rear+1)%MaxQueue 成立 (空出最後一個空間不用)

7 基本運算之演算法 加入元素於環狀佇列之後端 void enqueue (int data)
/* 此函數將data放入環狀queue 之後端 */ { q.rear = (q.rear+1)%MaxQueue; /* 先將 q.rear指向下一個位置 */ if (q.front == q.rear+1) { printf (“ queue is full \n”); exit(1); } else q.item[q.rear] = data; //將q.rear +1後，再將新元素data放在q中

8 於環狀佇列之前端刪除元素 /* 將q.front +1後，此時q.front 指向 queue 之第一個元素，再傳回此值 */
int dequeue (void) /* 此函數自queue 之前端刪除元素 */ { if (q.front == q.rear) /* q.front == q.rear 表 queue 為空 */ { printf (“ queue is empty \n”); exit(1); } else { q.front = (q.front+1)%MaxQueue; return ( q.item[q.front] ); /* 將q.front +1後，此時q.front 指向 queue 之第一個元素，再傳回此值 */

9 問題： 環形佇列最多只能使用n-1個空間，而浪費 一個空間
方法：另外設立一個變數judge來區分 加入資料後 Judge＝1時，則表示佇列已滿 刪除資料後 Judge＝0時，則表示佇列已空

10 優先佇列 (Priority Queue)

11 使用時機 優先佇列經常被用來處理緊急或特權作業 也就是正常的排隊順序中允許高優先權的作業插隊。 例如醫院急診室，最嚴重的患者優先治療；
飛機場飛機在空中且油料快用完了，優先降落（使用跑道）

12 優先佇列結構 (採陣列)

13 優先佇列與堆疊、佇列的不同 元素進入的時間不是決定性的因素 優先佇列不擷取和移去最晚或最早插入的元素
它只根據佇列中那一個有最高優先權，才有最先機會被擷取。

14 優先佇列的製作－陣列 最簡單的方法是採用陣列 當我們要移除某元素，可搜尋整個串列中具有最高優先權者； 欲插入元素只須插在頭部便可。

15 優先佇列的製作－鏈結串列 另一種較好的方法是採用鏈結串列 串列內的元素依優先順序排列 最高優先順序者排在串列的頭部
要移除（服務）只須將頭部元素移除，它的後繼者就變成新的首端元素 插入將較複雜，須根據優先順序來決定其插入位置。

16 優先佇列結構 (採鏈結串列)  

17 雙向佇列 (Double Ended Queue)

18 定義 雙向佇列又稱為Deque 資料的刪除和加入可以指定發生在佇列那一端 此種佇列有兩個前端(Front)及尾端(Rear)

19 雙向佇列結構

20 雙向佇列的插入及刪除資料

21 雙向佇列基本運作資料流程圖 -(插入)

22 雙向佇列基本運作資料流程圖-(刪除)