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

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

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

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

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

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 後端

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

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

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

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

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

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

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, 代表已空了

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

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

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

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開始

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];

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條件下 仍有一個空位

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

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

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