Presentation is loading. Please wait.

Presentation is loading. Please wait.

資料結構與演算法 課程教學投影片.

Similar presentations


Presentation on theme: "資料結構與演算法 課程教學投影片."— Presentation transcript:

1 資料結構與演算法 課程教學投影片

2 第八章–佇列 本章各段大綱 8-1 佇列概觀 8-2 佇列的資料結構和操作 8-3 環狀佇列 8-4 雙向佇列和特殊佇列

3 8-1 佇列概觀-定義 「佇列」(Queue) 定義 抽象的邏輯結構 將物件排列成隊伍,有入口和出口 物件只能從入口進入,只能從出口出去
不能從中間插隊 定義 佇列是一個有序串列(ordered list) 所有加入的動作只能在一個特定的入口進行 刪除的動作只能在一個特定的出口進行

4 8-1 佇列概觀-特性 先進先出 後進後出 加入元素到佇列中稱為加入(Addition) 自佇列中刪除元素稱為刪除(Delete)
first in first out (FIFO) 後進後出 last in last out ( LILO) 加入元素到佇列中稱為加入(Addition) 自佇列中刪除元素稱為刪除(Delete)

5 8-1 佇列概觀-範例 (1) 放入A (2) 放入B (3) 取出A (4) 放入C (5) 取出B (6)取出C (4) (2) (1)
放入ABC  輸出ABC,次序未變

6 8-1 佇列概觀-定義 定義 如果Q={ai,ai+1,..., aj-1,aj}為一佇列,則稱ai為前端(front)元素,aj為後端(rear)元素,i為前端(front),j為後端(rear),增加資料時由後端加入,刪除資料時由前端刪除,rear-front+1為佇列長度(length) 即在佇列中的元素個數 ai aj ... i 前端 j 後端

7 8-1 佇列概觀-運用 列印佇列 CPU分時(time sharing)作業 鍵盤緩衝區的應用
因列印工作較緩慢,以佇列方式安排列印工作,使系統可以對使用者的其他需求作即時處理 CPU分時(time sharing)作業 CPU以排序方式,將處理的工作置於佇列中,以分時的方式輪流處理佇列中的工作 鍵盤緩衝區的應用 輸入鍵盤資料時,系統未能即時反應輸入動作時,以鍵盤緩衝區作為佇列暫存資料

8 8-2 佇列的資料結構和操作 define maxq 100; char queue[maxq]; int front =-1;
int rear =-1; real=2 real=0 real=1 real=0

9 8-2 佇列的資料結構和操作 判斷佇列是否已滿 判斷佇列是否為空 front rear maxtop-1 1
    if (rear==maxtop-1)      … /*佇列已滿*/     else      … /*佇列未滿*/     end if 判斷佇列是否為空     if (rear==front)      … /*佇列為空*/      … /*佇列不為空*/ 1 ai aj ... front rear

10 8-2 佇列的資料結構和操作 將資料放入佇列 void addq(int data) {
    if (isfull())queuefull() /*isfull()檢查是否queue已滿*/     else queue[++rear]=data /*queuefull()是作相關處理*/ } /*rear先加1, 再當成queue的指標放入data 已刪除的區域 作用中的區域 未放入的區域 a.原先的位置 ... front=i rear=n maxq-1 已刪除的區域 作用中的區域 未放入的區域 b.加入資料 (addq) ... front=i 不變 rear=n+1 maxq-1

11 8-2 佇列的資料結構和操作 將資料從佇列取出 int delq() { a.原先狀態 b.刪除資料 (delq)
    if (isempty()) /*isempty是檢查佇列是否已空了*/    {    queueempty(); /*queueempty是佇列空時,又要取出資料的處理*/     return 0; /*傳回0代表失敗*/     }else return queue[++front]; /*一切正常front,加1,且傳回資料*/ } 已刪除的區域 作用中的區域 未放入的區域 a.原先狀態 ... front=i rear=n (課本誤植為n+1) maxq-1 已刪除的區域 作用中的區域 未放入的區域 b.刪除資料 (delq) ... rear=n maxq-1 ++front => front=i+1

12 8-2 佇列的資料結構和操作 佇列已滿否? 在addq()演算法中, rear只會往後增加,最多至max-1 int isfull() {
    if (real==max-1) return 1; /* 1代表已滿 */   else return 0;  /* 0代表未滿 */ } 已刪除的區域 作用中的區域 未放入的區域 a.原先狀態 ... ...... maxq-1 front=i rear 已刪除的區域 作用中的區域 b.增加資料 (delq) ... ...... front=i rear=maxq-1

13 8-2 佇列的資料結構和操作 佇列已空否? 檢查佇列是否已空時, front 一直往rear逼近,且rear==front時代表佇列已經空了
int isempty() {     if (front==real) return 1; /* 1代表已空了 */   else return 0;  /* 0代表未空 */ } 已刪除的區域 作用中的區域 未放入的區域 a.原先狀態 ... ...... maxq-1 front=i rear=i+1 已刪除的區域 b.刪除資料 (delq) ... ...... front=rear=i+1 c.刪除資料時, real=front, 代表已空了

14 8-2 佇列的資料結構和操作 範例1 (pp.8-10) 輸入到佇列的整數資料 由佇列輸出的整數資料

15 8-3 環狀佇列 線性佇列: 環形陣列: 以前端front 紀錄刪除資料及後端rear紀錄新增加資料的位置
rear到達末端:陣列很快達到佇列已滿的狀態,但front之前都沒有資料 環形陣列: 重新利用已刪除區域,當rear到達最大值時從前端開始編號放入新資料 佇列已滿:所有位置放滿資料

16 8-3 環狀佇列 front 和rear到達maxq-1時,重新設為0開始 以C為例,採用%運算子 當rear=maxq-1時

17 8-3 環狀佇列 d1 d2 d1 d2 d3 d2 d3 d4 d2 d3 1 2 3 4 5 問題 //當front==rear時無法
問題 //當front==rear時無法 //知道是否為空的或已滿 環狀佇列宣告 define maxq 6 int queue[maxq]; int front=-1; // 此初始設定會導致無法判斷已滿的狀況 int rear=-1; (1)目前狀態front=2, rear=4 d1 d2 1 2 3 4 5 (2)加入d3, front=2, rear=5 d1 d2 d3 1 2 3 4 5 d2 d3 1 2 3 4 5 (3)刪除d1, front=3, rear=5 d4 d2 d3 1 2 3 4 5 (4)加入d4, front=3, rear=0 (rear+1)%6 =(4+1)%6 =5 (front+1)%6 =(2+1)%6 =3 (rear+1)%6 =(5+1)%6 =0 此時rear從0開始,同理front到達5時,也會從0開始

18 8-3 環狀佇列-演算法 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 /* 演算法名稱:addcq & delcq */ /* 輸入: */ /* 輸出: */ defint cmaxq 100; char cqueue[cmaxq]; int cfront=-1; int crear=-1; void addcq (int data) { if (iscfull()) cqueuefull() else cqueue [++rear%cmaxq]=data } int delcq() if (iscempty()) cqueueempty(); return 0; else return cqueue[++cfront%cmaxq];

19 8-3 環狀佇列-演算法 /*請參考前面範本說明,並非如此 在((rear+1)%maxq = ftont條件下 仍有一個空位 01 02
03 04 05 06 07 08 09 /* 演算法名稱:iscEmpty */ /* 輸入: */ /* 輸出: */ int iscEmpty() { if (rear==ftont) return 1; /*1代表佇列已空*/ else return 0; /*0代表佇列未空*/ } 01 02 03 04 05 06 07 08 09 10 /* 演算法名稱:iscfull */ /* 輸入: */ /* 輸出: */ int iscfull() { if ((rear+1)%maxq = ftont) return 1; /*1代表佇列已滿*/ else return 0; /*0代表佇列未滿*/ } /*請參考前面範本說明,並非如此 在((rear+1)%maxq = ftont條件下 仍有一個空位

20 8-3 環狀佇列-演算法 課本範例程式所遭遇問題 請改寫課本程式使其環狀佇列可以發揮功能 並未發揮偵測佇列已滿或已空的功能
front及rear的初始設定不適合環狀序列 資料取出的動作並未將資料從佇列中刪除 請改寫課本程式使其環狀佇列可以發揮功能

21 8-4 雙向佇列和特殊佇列 特殊佇列 重點在於改變先前介紹的addq()或addcq演算法
例如,假如將佇列結構應用在醫院診所的掛號系統,如果求診者一視同仁,都按照掛號編號看診,則當有需要急診之某一病患,或者有優先權較高者可以把要處理的先放到佇列的最前面,這樣在從佇列取出時就可以最先取出了

22 8-4 雙向佇列和特殊佇列 雙向佇列 線性佇列和環狀佇列只能有唯一的入口和唯一的出口,此稱為單向佇列(single-end-queue),佇列可加以變化成為兩端都可入口和出口的雙向佇列(double-end-queue,dqueue)。 雙向佇列是擴充原先前端front只能刪除資料,後端rear只能增加資料的功能,讓前端front可能加入資料,後端rear也能刪除資料,因此可改為左端(left)和右端(right)。Left或right要加入資料或刪除資料是由你設計的程式來控制。


Download ppt "資料結構與演算法 課程教學投影片."

Similar presentations


Ads by Google