佇列 (Queue).

Presentation on theme: "佇列 (Queue)."— Presentation transcript:

1 佇列 (Queue)

2 定義及特性 佇列 (Queue)，是一個有序的串列 所有的加入與刪除發生在串列的不同端
加入的一端為尾端(Rear) 刪除一端稱為前端(Front) 具有先進先出(First-In-First-Out；簡稱FIFO)特性 佇列中所含的元素是同質的，有相同的型式(type)。

3 典型的佇列

4 佇列的表示法及基本運作

5 佇列的應用 佇列在電腦科學中有很廣泛的應用，例如電腦模擬 (Computer simulation)，作業系統裡電腦資源的分配，有很多是用佇列來表示的。佇列的應用最常見的如下：   作業系統的工作排序   用於印表機或作業系統的Spooling   計算機的模擬 (Simulation)   資料通訊   從佇列的特徵看起來，陣列或鏈結串列都可以用來描述佇列，和堆疊比較起來，除了元素進出的順序不同以外，兩者十分地相像，有趣的是，在應用上，兩者的適用性卻有極大的差異。  

6 佇列的表示法及基本運作 CREATE(Q)：建立空的佇列 ADDQ(data, Q)：將資料加入佇列的尾端(rear)
DELETEQ(Q)：傳回佇列前端(front)的資料，並將該筆資料自佇列中刪除 FRONT(Q)：傳回佇列前端的資料，但不將該筆資料自佇列中刪除 EMPTY(Q)：若佇列內已無任何資料，就傳回真值(True)，否則為假值(False) FULL(Q)：若佇列內已滿，就傳回真值(True)，否則為假值(False)

7 表示法 佇列的表示法和堆疊一樣，有陣列和鏈結串列兩種 陣列是屬於循序配置，而鏈結串列則屬於動態配置。 必須具備下列功能：
產生佇列結構：宣告一個陣列或鏈結串列結構，並設成空佇列，即Front = Rear = -1或Front = Rear =NULL 將資料放入佇列：若佇列未滿，則改變Rear指標後將資料存入佇列的Rear位置。 刪除資料：若佇列不是空的，則改變Front指標後，將Front所指到之佇列元素刪除。 判斷佇列是否滿溢：當Rear = N -1，表示佇列滿溢。 判斷佇列是否是空的：當Front = Rear時，為空佇列。

8 佇列的實作模擬 佇列的操作包括：建立佇列、檢查佇列中是否有元素、檢查佇列是否已滿、計算佇列中的元素總數、新增元素到佇列中、與從佇列中移除元素。 實作模擬佇列的方法兩種：一是使用一維陣列，二是使用鏈結串列。與堆疊相同，我們仍以一個一維陣列來呈現佇列的運算：

9 陣列模擬佇列 以一維陣列Q(1 To n)表示一個佇列 其中 空佇列之充要條件 q.rear =q.front
刪除元素 由前端 q.front後移一格，q.rear不變

10 陣列圖解 建立一個陣列如下和兩個變數： char Q[1 to 4]; int rear = -1 ， front = -1;
索引 1 2 3 值 註標 (front = -1) (rear = -1)

11 放入A之後如下 放入B之後如下 索引 1 2 3 值 A 註標 (front = -1) (rear = 0) 索引 1 2 3 值 A B
1 2 3 值 A 註標 (front = -1) (rear = 0) 放入B之後如下 索引 1 2 3 值 A B 註標 (front = -1) (rear = 1)

12 放入C之後如下 輸出A之後如下 索引 1 2 3 值 B C 註標 (front =0) (rear = 2) 索引 1 2 3 值 A B
1 2 3 值 A B C 註標 (front = -1) (rear = 2) 輸出A之後如下 索引 1 2 3 值 B C 註標 (front =0) (rear = 2)

13 發現rear和 front相等，所以知道現在是空無一物。
輸出B之後如下 索引 1 2 3 值 C 註標 (front = 1) (rear = 2) 輸出C之後如下 索引 1 2 3 值 註標 (rear = 2) (front = 2) 發現rear和 front相等，所以知道現在是空無一物。

14 佇列基本運算的演算法與程式

15 佇列的抽象化資料型態(ADT) 基本方法(函數)
enqueue(obj)： 此函數將物件obj 由串列的尾端加入 輸入：物件obj 輸出：無 支援方法(函數) size()：此函數決定佇列中物件之個數 輸入：無 輸出：整數 isEmpty()：此函數判別佇列是否空了 輸入：無 輸出：邏輯值

16 佇列的基本運算 空佇列之充要條件 rear =front 佇列元素個數 = rear- front

17 佇列之宣告 一般陣列表示佇列 #define MaxSize 100 /* 佇列大小 */
int struct queue [MaxSize]； /* 以陣列表示佇列 */ int front, rear； /* front表陣列佇列第一個元素前一格位置，rear表後端之位置*/

18 以Structure(結構體)表示佇列 #define MaxQueue 100 /* 佇列大小 */
typedef struct queue { /* 以結構體表示佇列*/ int item[MaxQueue] ; /* 陣列item儲存佇列項目*/ int front, rear; } q ; /* front表陣列佇列第一個元素前一格位置，rear表後端之位置*/

19 佇列中 一般陣列表示佇列 Structure的佇列 front = 0; /*front 起始值 */
rear = - 1; /*rear 起始值 */ Structure的佇列 q.front = -1; /* q.front 起始值 */ q.rear = - 1; /* q.rear 起始值 */

20 加入元素 演算法：虛擬碼 Procedure Qadd(int queue[ ] , element ) { index rear ;
if (rear ＞佇列的最後位置) 　顯示佇列已滿的錯誤訊息; else rear ＝ rear＋1; queue[ rear ] = element 傳回 queele [rear ]; }

21 C語言：程式碼(一) void QAdd (int queue [ ] , int MaxSize , int rear , int x )
{ if ( rear >= MaxSize - 1) printf(“佇列已滿了…”) ; else queue [+ + rear ]＝x ; }

22 C語言：程式碼(二) void queue (int data) /* 此函數將data放入queue 之後端 */ {
if (q.rear == MaxQueue-1) { printf (“ queue is full \n”); exit(1); } else q.item[++q.rear] = data; //將q.rear +1後，再將新元素data 放在q中

23 刪除元素 演算法：虛擬碼 Procedure QDel(int queue[ ] ) { index front , rear ;
if (front ＞= rear) 　顯示佇列已空的錯誤訊息; else front ＝ front＋1; 傳回 queue [front ]; }

24 C語言：程式碼(一) void QDel (int queue [ ] , int front , int rear ) {
if ( front >= rear ) printf(“佇列已空了，無資料可刪…”) ; else ｛ front + +; printf(“ %d 已從佇列中刪除了 ” , queue [front ] ; }

25 C語言：程式碼(二) int dequeue (void) /* 此函數自queue 之前端刪除元素 */ {
if (q.front == q.rear) /* q.front == q.rear 表 queue 為空 */ { printf (“ queue is empty \n”); exit(1); } else return ( q.item[++q.front] ); /* 將q.rear +1後，此時q.front 指向 queue 之第一個元素，再傳回此值 */

26 範例 以下是一個以結構定義的Queue，包含加入及刪除節點 #include <stdio。h>
struct node {                           // 宣告一個結構 int number; struct node *next; }; void showmain(); struct node *add(struct node *);         // 將新節點加入Queue。 struct node *out(struct node *);         // 將新節點輸出Queue。

27 void main() { struct node *real = NULL，*front = NULL;         // 將其預設為NULL do{ showmain(); switch (getche()) case '1': real = add(real); if (front == NULL)           // 當front為NULL時，front=real front = real; } break;

28 case '2': front = out(front); break; case '3': exit(0); default: printf("\nIt is wrong，pleace input again\n"); } }while (1);

29 void showmain() { printf("<1>add a value\n"); printf("<2>output a value\n"); printf("<3>exit\n"); } struct node *add(struct node *real) struct node *New; New = (struct node *)malloc(sizeof(struct node)); printf("pleace input a number"); scanf("%d"，&(New->number)); New->next = NULL; if (real != NULL)  real ->next = New;              // 新節點接在real之後 real = New;                                       // real指向新節點 return (real);

30 struct node *out(struct node *front)
{ struct node *freenode; if (front != NULL) printf("\nThe pop number is %d\n"，front->number); freenode = front; front = front ->next; free(freenode);          // 釋放記憶體 return (front); } else printf("\nNo Node\n"); return (NULL);

31 佇列之缺點 使用過的佇列空間無法再使用，容易造成無謂之浪費，而改善方式則是視佇列為一個環 (circular)，即環狀佇列 (circular queue)；另外亦有優先佇列 (Priority Queues) 及雙向佇列 (Double Ended Queues) 兩種佇列方式，提供了較彈性的資料處理方式。在下面的單元即針對這些變形的佇列，其資料結構的運作與特點。