CHAPTER 4 隨 書 光 碟 4-1 4-3 環 形 佇 列 由 於 佇 列 有 一 個 問 題, 就 是 前 端 (Front) 尚 有 空 位 時, 再 加 入 元 素, 卻 發 現 此 佇 列 已 滿 此 時 的 解 決 方 法 就 是 使 用 環 形 佇 列 (Circular Queue) 定 義 是 指 一 種 環 形 結 構 的 佇 列 作 法 將 一 維 陣 列 的 第 0 個 元 素, 存 放 到 環 形 佇 列 第 0 個 位 置 中, 一 維 陣 列 的 第 1 個 元 素, 存 放 到 環 形 佇 列 第 1 個 位 置 中, 以 此 類 推, 同 時 Q[0] 為 Q[N-1] 的 下 一 個 元 素 圖 解 說 明 圖 4-4 環 形 佇 列 缺 點 佇 列 滿 了, 浪 費 一 個 空 格 沒 有 使 用, 若 再 加 入 一 個 項 目 時,Rear 等 於 0, 也 就 是 Front 等 於 Rear, 如 此 無 法 分 辨 此 時 佇 列 是 空 的 還 是 滿 的 因 此, 環 形 佇 列 必 須 浪 費 一 個 空 格 當 Front 等 於 Rear 時, 環 形 佇 列 為 空 的 當 (Rear+1) Mod N 等 於 Front 時, 環 形 佇 列 為 已 滿
4-2 1. 使 用 一 般 佇 列 存 放 資 料 時, 當 前 端 (Front) 尚 有 空 位 時, 再 加 入 元 素, 卻 發 現 此 佇 列 已 滿, 請 問 此 時 使 用 下 列 那 一 個 方 法 較 佳? (A) 優 先 佇 列 (B) 環 形 佇 列 (C) 雙 向 佇 列 (D) 以 上 皆 非 2. 在 環 形 佇 列 中, 它 是 利 用 一 種 Q[0: N-1] 的 一 維 陣 列 來 存 放 資 料, 請 問 佇 列 Q[0] 是 那 一 項 的 下 一 個 元 素? (A) Q[1] (B) Q[2] (C) Q[N-1] (D) Q[N-2] 3. 使 用 環 形 佇 列 存 放 資 料 時, 往 往 會 浪 費 多 少 空 間? (A) 1 (B) 2 (C) 3 (D) 3 個 以 上 4-3.1 環 形 佇 列 的 基 本 運 作 功 能 其 實 環 形 佇 列 基 本 運 作 功 能 必 須 撰 寫 以 下 三 個 函 數, 才 能 算 是 一 個 完 整 環 形 結 構 的 功 能 1. Create(CQueue) 函 數 2. Add 函 數 3. Delete 函 數
CHAPTER 4 隨 書 光 碟 4-3 一 Create (CQueue) 函 數 是 指 用 來 建 立 一 個 空 的 環 形 佇 列 ( 一 ) 演 算 法 #define N 10 // 定 義 環 形 佇 列 大 小 char CQueue[N]; // 以 陣 列 CQueue 當 作 佇 列 int Rear=-1; // 設 定 後 端 的 索 引 值 之 初 值 為 -1 int Front=-1; // 設 定 前 端 的 索 引 值 之 初 值 為 -1 ( 二 ) 陣 列 的 記 憶 體 配 置 ( 空 的 Circular Queue) 圖 解 說 明 假 設 我 們 定 義 N = 10 ( 也 就 是 編 號 0~9) 共 10 個 空 間, 並 且 Front 與 Rear 的 初 始 值 都 為 -1, 其 中,Front 指 標 是 用 來 記 錄 目 前 環 形 佇 列 前 端 的 索 引 值, 並 且 Rear 指 標 是 用 來 記 錄 目 前 環 形 佇 列 後 端 的 索 引 值, 而 Front 與 Rear 指 標 初 始 值 設 為 -1 表 示 環 形 佇 列 為 空 參 看 隨 書 光 碟 二 Add 函 數 是 指 加 入 新 項 目 到 環 形 佇 列 中
4-4 ( 一 ) 演 算 法 將 資 料 放 入 環 形 佇 列 01 02 03 Procedure Add(item,CQueue) Begin Rear=(Rear+1) Mod N //N 代 表 環 形 佇 列 大 小 04 if (Rear=Front) 05 Circular Queue Is Full; //Circular Queue 已 滿 06 else 07 { 08 09 CQueue[Rear]=item; 10 } 11 12 End End Procedure ( 二 ) 實 例 假 設 現 在 有 3 個 資 料 項, 分 別 為 A, B, C, 接 下 來, 請 依 序 將 這 三 個 資 料 項 加 入 環 形 佇 列 中, 並 且 呈 現 以 上 佇 列 運 作 之 後 的 Front 與 Rear 之 值 步 驟 一 : 當 我 們 要 加 入 第 一 個 資 料 項 時, 演 算 法 會 先 計 算 欲 加 入 資 料 的 所 在 位 置 Rear 指 標, 此 時,Rear 指 標 從 -1 指 向 0 ( 也 就 是 Rear 加 1 之 後, 除 以 8, 再 取 餘 數 ), 並 且 Rear 指 標 不 等 於 Front 指 標, 所 以, 會 將 資 料 項 A 加 入 Rear 指 標 所 在 的 佇 列 中
CHAPTER 4 隨 書 光 碟 4-5 步 驟 二 : 當 我 們 要 加 入 第 二 個 資 料 項 時, 演 算 法 會 再 計 算 欲 加 入 資 料 的 所 在 位 置 Rear 指 標, 此 時,Rear 指 標 從 0 指 向 1 ( 也 就 是 Rear 加 1 之 後, 除 以 8, 再 取 餘 數 ), 並 且 Rear 指 標 不 等 於 Front 指 標, 所 以, 會 將 資 料 項 B 加 入 Rear 指 標 所 在 的 佇 列 中
4-6 步 驟 三 : 當 我 們 要 加 入 第 三 個 資 料 項 時, 演 算 法 會 再 計 算 欲 加 入 資 料 的 所 在 位 置 Rear 指 標, 此 時,Rear 指 標 從 1 指 向 2 ( 也 就 是 Rear 加 1 之 後, 除 以 8, 再 取 餘 數 ), 並 且 Rear 指 標 不 等 於 Front 指 標, 所 以, 會 將 資 料 項 C 加 入 Rear 指 標 所 在 的 佇 列 中 假 設 有 一 個 空 的 環 形 佇 列 CQueue, 實 施 下 列 動 作 : Add A Add B,C Delete Add D Delete Add E,F,G,H,I Add J Delete Delete Delete Delete Delete Delete Delete 請 呈 現 以 上 佇 列 運 作 之 後 的 Front 與 Rear 之 值
CHAPTER 4 隨 書 光 碟 4-7
4-8 參 看 隨 書 光 碟 三 Delete 函 數 是 指 從 環 形 佇 列 中 取 出 資 料 ( 一 ) 演 算 法 從 環 形 佇 列 刪 除 資 料 01 02 03 04 05 06 07 08 09 10 11 Procedure Delete(item, CQueue) Begin if (Front=Rear) Circular Queue Is Empty; //Queue 為 空 else { Front=(Front+1) Mod N item=cqueue[front]; } End End Procedure ( 二 ) 實 例 假 設 目 前 在 環 形 佇 列 中 已 經 有 3 個 資 料 項, 分 別 為 A, B, C, 此 時, 欲 取 出 A 資 料 項, 請 問 環 形 佇 列 運 作 之 後 的 Front 與 Rear 之 值 為 何?
CHAPTER 4 隨 書 光 碟 4-9 當 我 們 想 從 環 形 佇 列 中 取 出 資 料 項 時, 演 算 法 會 先 判 斷 Front 指 標 是 否 等 於 Rear 指 標, 如 果 不 是, 則 必 須 先 計 算 欲 取 出 資 料 的 所 在 位 置, 此 時,Front 值 等 於 0 ( 也 就 是 Front 加 1 之 後, 除 以 8, 再 取 餘 數 ), 然 後, 再 從 環 形 佇 列 中 取 出 Front 指 標 所 在 位 置 的 資 料 四 分 析 1. 若 硬 要 使 用 N 個 空 間, 則 Rear = Front 條 件 式 成 立 時, 將 無 法 區 分 出 佇 列 是 否 真 的 Full 或 Empty, 如 下 圖 所 示 2. 判 斷 佇 列 是 否 已 滿 或 為 空, 則 使 用 相 同 的 條 件 式 (Rear=Front) 3. 加 入 或 刪 除 動 作 的 時 間 複 雜 度 均 為 O(1)
4-10 參 看 隨 書 光 碟 老 師 上 課 動 態 展 示 檔 案 請 參 隨 書 光 碟
CHAPTER 4 隨 書 光 碟 4-11 1. 加 入 5 個 資 料 項 2. 刪 除 A 資 料 項 1. 當 採 用 環 形 佇 列 其 佇 列 元 素 個 數 為 Size 時, 判 斷 佇 列 為 滿 的 條 件 是 : (A) Rear mod Size = Front (B) (Rear+1) mod Size = Front (C) Front = Rear (D) (Front + 1) mod Size = Rear 2. 當 採 用 環 形 佇 列 其 佇 列 元 素 個 數 為 Size 時, 判 斷 佇 列 為 空 的 條 件 是 : (A) Rear mod Size = Front (B) (Rear + 1) mod Size = Front (C) Front = Rear (D) (Front + 1) mod Size = Rear 3. 用 陣 列 來 實 作 環 形 佇 列 時, 當 佇 列 某 一 時 間 點 資 料, 如 下 圖 所 示 時, 其 中 位 置 [1][2][3] 代 表 有 資 料,Front 與 Rear 分 別 為 何 :
4-12 (A) Front = 3, Rear = 3 (B) Front=3, Rear = 1 (C) Front = 0, Rear = 3 (D) Front = 3, Rear=0 4-3.2 環 形 佇 列 的 改 良 由 於 傳 統 的 環 形 佇 列 會 浪 費 一 個 空 間, 因 此, 其 改 良 作 法 就 是 另 外 再 增 加 一 個 變 數 (Tag) 來 判 斷, 以 記 錄 每 一 次 的 動 作 優 點 最 多 可 以 利 用 到 N 個 空 間 缺 點 Add 與 Delete 動 作 均 須 額 外 多 加 一 條 件 判 斷 式 一 Add (item, CQueue) 將 資 料 加 入 環 形 佇 列 ( 一 ) 演 算 法 Procedure Add(item,CQueue) Begin Rear=(Rear+1) Mod n if (Rear=Front) And (Tag=1) CircularQueue Is Full; // 佇 列 已 滿 else { CQueue[Rear]=item; if(rear=front) then Tag=1;
CHAPTER 4 隨 書 光 碟 4-13 } End End Procedure ( 二 ) 實 例 假 設 我 們 現 在 有 一 個 環 形 佇 列, 共 8 個 空 間 ( 也 就 是 編 號 0~7), 並 且 已 經 存 入 7 個 資 料 項, 如 圖 所 示 接 下 來, 我 們 想 再 加 入 一 個 資 料 項 J, 請 呈 現 運 作 之 後 的 Front 與 Rear 之 值 及 環 形 佇 列 的 狀 態 當 我 們 要 加 入 資 料 項 時, 演 算 法 會 先 計 算 欲 加 入 資 料 的 所 在 位 置 Rear 指 標, 此 時,Rear 指 標 從 0 指 向 1, 我 們 發 現 Rear 指 標 等 於 Front 指 標, 但 是,Tag 為 0, 表 示 環 形 佇 列 還 沒 有 滿
4-14 所 以, 我 們 還 可 以 再 將 J 元 素 加 入 環 形 佇 列 中 此 時, 演 算 法 會 再 判 斷 Rear 指 標 是 否 等 於 Front 指 標, 並 且 Tag 是 否 等 於 1, 如 果 不 是, 就 可 以 再 將 資 料 項 加 入 佇 列 中, 然 後, 再 設 定 Tag 等 於 1 因 此, 可 清 楚 得 知 增 加 一 個 Tag 指 標 之 後, 就 可 以 改 善 環 形 佇 列 浪 費 一 個 空 間 的 問 題
CHAPTER 4 隨 書 光 碟 4-15 二 Delete (item,cqueue) 從 環 形 佇 列 刪 除 資 料 ( 一 ) 演 算 法 Procedure Delete(item, CQueue) Begin if (Front=Rear) And (Tag=0) Circular Queue Is Empty; // 佇 列 為 空 else { Front=(Front+1) Mod n item=cqueue[front]; if(rear=front) then Tag=0; } End End Procedure ( 二 ) 實 例 假 設 我 們 現 在 有 一 個 環 形 佇 列, 共 8 個 空 間 ( 也 就 是 編 號 0~7), 並 且 只 存 放 1 個 資 料 項 A, 如 圖 所 示 接 下 來, 我 們 想 取 出 此 資 料 項 A, 請 呈 現 運 作 之 後 的 Front 與 Rear 之 值 及 環 形 佇 列 的 狀 態 當 我 們 要 取 出 資 料 項 時, 演 算 法 會 先 判 斷 Rear 指 標 是 否 等 於 Front 指 標, 並 且 Tag 是 否 等 於 0, 因 此, 我 們 發 現 Front = -1 而 Rear = 0, 所 以, 佇 列 不 為 空 因 此, 先 計 算 欲 取 出 資 料 的 所 在 Front 指 標, 然 後, 再 取 出 資 料 項 A
4-16 取 出 資 料 項 A 之 後, 最 後, 再 判 斷 Rear 指 標 是 否 等 於 Front 指 標, 如 果 是 的 話, 則 設 Tag 為 0 因 此,Rear 指 標 等 於 Front 指 標, 並 且 設 Tag 為 0, 所 以, 代 表 此 佇 列 為 空
CHAPTER 4 隨 書 光 碟 4-17 請 利 用 C 語 言 撰 寫 一 個 環 形 佇 列 的 程 式 環 形 佇 列 Enqueue( ) 以 及 Dequeue( ) 程 式 檔 名 :ch4-3.2 01 #define NUM 8 // 定 義 環 形 佇 列 大 小 02 void Enqueue(int); // 宣 告 Enqueue 副 程 式 03 int Dequeue(void); // 宣 告 Dequeue 副 程 式 04 void PrintQueue(void); // 宣 告 列 印 目 前 環 形 佇 列 的 內 容 之 副 程 式 05 06 07 08 09 10 11 12 13 14 typedef struct queue { int CQueue[NUM]; int Rear; int Front; } Queue; Queue qu; int main(void) // 主 程 式 { int op=0,item; qu.rear = 0;
4-18 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 qu.front = 0; printf("=============== 程 式 描 述 =======================\n"); printf("= 程 式 名 稱 :ch4-3.2.c =\n"); printf("= 程 式 目 的 : 環 形 佇 列 進 行 Enqueue 以 及 Dequeue =\n"); printf("==============================================\n"); while(1) { printf("=============================================\n"); printf("= 1.Enqueue( 加 入 ) =\n"); printf("= 2.Dequeue( 刪 除 ) =\n"); printf("= 3. 顯 示 目 前 環 形 佇 列 的 內 容 =\n"); printf("= 4. 結 束 =\n"); printf("=============================================\n"); printf(" 請 輸 入 你 的 操 作 :"); scanf("%d",&op); switch(op) { case 1: printf(" 請 輸 入 你 要 加 入 的 資 料 :"); scanf("%d",&item); Enqueue(item); // 呼 叫 Enqueue 副 程 式 break; case 2: item = Dequeue( ); // 呼 叫 Dequeue 副 程 式 if(item!= -1) printf("%d 是 從 環 形 佇 列 刪 除 的 資 料 \n",item); break; case 3: PrintQueue( ); // 呼 叫 列 印 環 形 佇 列 的 內 容 之 副 程 式 break; case 4: printf("\n"); // 結 束 return (0); } } system("pause"); // 使 程 式 暫 停 在 執 行 畫 面 讓 我 們 看 到 結 果 return 0; } void Enqueue(int item) // 加 入 item 到 佇 列 中 的 副 程 式 { qu.rear = (qu.rear+1)%num; if((qu.rear)%num == qu.front) { printf(" 環 形 佇 列 是 滿 的!\n"); system("pause");
CHAPTER 4 隨 書 光 碟 4-19 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 exit(1); } else qu.cqueue[qu.rear] = item; } int Dequeue(void) // 從 佇 列 中 刪 除 item 的 副 程 式 { if(qu.front == qu.rear) { printf(" 環 形 佇 列 是 空 的!\n"); system("pause"); exit(1); } else { qu.front = (qu.front+1)%num; return qu.cqueue[qu.front]; } } void PrintQueue(void) // 顯 示 目 前 環 形 佇 列 的 內 容 之 副 程 式 { int i; printf(" 目 前 環 形 佇 列 的 內 容 :"); for(i=qu.rear;i!=qu.front;i=(i+num-1)%num) printf("%d ",qu.cqueue[i]); printf("\n"); } 1 在 儲 存 佇 列 元 素 時, 以 環 狀 陣 列 來 取 代 線 性 陣 列, 最 主 要 可 以 得 到 下 列 那 一 項 優 點 : (A) 較 節 省 儲 存 空 間 (B) 易 於 修 正 佇 列 的 前 端 索 引 (C) 避 免 大 量 資 料 搬 移 (D) 可 儲 存 較 多 資 料 項 2. 為 了 讓 環 形 佇 列 可 以 使 用 N 個 空 間, 增 加 一 個 變 數 (Tag), 因 此, 當 佇 列 已 滿, Tag 一 般 會 設 定 為 多 少? (A) Tag = -1 (B) Tag = 0 (C) Tag = 1 (D) Tag = 2
4-20 4-4 進 階 佇 列 在 前 面 單 元 中, 我 們 已 經 學 會 一 般 佇 列 與 環 狀 佇 列, 因 此, 在 本 單 元 中, 我 們 再 來 介 紹 比 較 特 殊 的 佇 列 例 如 : 優 先 佇 列 及 雙 向 佇 列 1. 優 先 佇 列 2. 雙 向 佇 列 1. 基 本 上, 我 們 所 探 討 的 佇 列, 除 了 一 般 佇 列 之 外, 還 有 那 些 佇 列 呢? (A) 環 狀 佇 列 (B) 優 先 佇 列 (C) 雙 向 佇 列 (D) 以 上 皆 是 2. 下 列 那 一 種 佇 列 具 有 兩 端 都 可 做 加 入 與 取 出 資 料 的 動 作? (A) 環 狀 佇 列 (B) 優 先 佇 列 (C) 雙 向 佇 列 (D) 以 上 皆 是 4-4.1 優 先 佇 列 在 優 先 佇 列 (Priority Queue) 中, 其 元 素 的 加 入 及 刪 除 不 須 遵 守 先 進 先 出 的 特 性 這 種 情 況 在 日 常 生 活 中 時 常 遇 到, 例 如 : 醫 院 的 急 診 室 捷 運 座 位 提 供 老 幼 婦 孺 者 之 博 愛 座 等 等
CHAPTER 4 隨 書 光 碟 4-21 定 義 1. 優 先 佇 列 是 一 種 不 必 遵 守 先 進 先 出 佇 列 的 有 序 串 列 2. 每 一 個 佇 列 的 元 素, 都 給 予 一 個 優 先 順 序 權, 其 數 字 最 大 者 代 表 有 最 高 優 先 權 缺 點 在 經 常 需 要 大 量 資 料 異 動 時, 無 法 預 先 知 道 需 要 保 留 多 少 後 端 空 間 給 插 入 的 工 作 使 用 假 設 現 在 有 三 個 佇 列, 分 別 是 A 佇 列 B 佇 列 及 C 佇 列, 而 這 三 個 佇 列 的 優 先 權 分 別 為 2, 3, 4 ( 其 中 數 值 愈 大, 代 表 優 先 權 愈 高 ), 接 下 來, 請 利 用 一 般 佇 列 與 優 先 佇 列 來 比 較 這 三 個 佇 列 的 差 異 圖 4-5 優 先 佇 列 結 構 首 先, 我 們 先 來 看 上 面 的 一 般 佇 列, 由 於 每 一 個 佇 列 的 優 先 權 都 相 同, 因 此, A 佇 列 先 到, 所 以, 先 處 理, 而 B 佇 列 排 在 A 佇 列 的 後 面, 所 以, 等 A 佇 列 處 理 完 成 之 後, 才 能 處 理 B 佇 列, 並 且 C 佇 列 是 最 晚 到 的 佇 列, 所 以, 最 後 處 理 如 上 圖 所 示 ( 一 ) 一 般 佇 列 ( 優 先 權 相 同, 先 到 先 處 理 )
4-22 ( 二 ) 優 先 佇 列 由 於 優 先 佇 列 不 須 遵 守 先 進 先 出 的 特 性, 因 此, 雖 然 C 佇 列 是 最 晚 到 的 佇 列, 但 優 先 權 最 高, 所 以, 最 早 被 處 理 而 B 佇 列 是 第 二 早 到 的 佇 列, 並 且 它 的 優 先 權 排 在 C 佇 列 之 後, 所 以, 第 二 個 被 處 理 A 佇 列 的 優 先 權 最 低, 雖 然 是 最 早 到 的 佇 列, 但 是, 最 後 才 處 理 如 下 圖 所 示
CHAPTER 4 隨 書 光 碟 4-23 1. 請 問 在 資 料 結 構 中 那 一 種 佇 列 在 加 入 及 刪 除 時 不 須 遵 守 先 進 先 出 的 特 性? (A) 雙 向 佇 列 (B) 一 般 佇 列 (C) 環 形 佇 列 (D) 優 先 佇 列 2. 在 優 先 佇 列 中, 一 般 可 以 利 用 那 兩 種 資 料 結 構 來 解 決? (A) 陣 列 及 矩 陣 (B) 陣 列 及 串 列 (C) 串 列 與 樹 (D) 陣 列 與 圖 形 4-4.2 雙 向 佇 列 定 義 雙 向 佇 列 (Double-Ended Queue: Deque) 是 一 種 特 殊 的 資 料 結 構, 它 的 兩 端 都 可 做 加 入 與 取 出 資 料 的 動 作, 不 像 堆 疊 的 LIFO 或 佇 列 的 FIFO 亦 即 它 是 一 種 前 後 兩 端 都 可 輸 入 或 取 出 資 料 的 有 序 串 列 如 圖 4-6 所 示
4-24 圖 4-6 雙 向 佇 列 (Deque) 假 設 我 們 循 序 輸 入 一 串 數 字 :1, 2, 3, 4, 5, 6, 7, 請 問 是 否 可 以 輸 出 5174236 呢? 循 序 輸 入 一 串 數 字 :1, 2, 3, 4, 5, 6, 7, 順 序 如 下 : 輸 出 : 先 輸 出 5, 再 輸 出 1, 又 輸 出 7, 但 是, 下 一 個 輸 出 不 是 2 就 是 6, 無 法 輸 出 4, 因 此, 在 循 序 輸 入 1, 2, 3, 4, 5, 6, 7 的 情 況 下, 無 法 得 到 5174236 的 輸 出 結 果 參 看 隨 書 光 碟 1. 利 用 雙 向 佇 列 循 序 輸 入 1, 2, 3, 4, 5, 6, 7, 試 問 絕 不 可 能 得 到 哪 種 輸 出? (A) 7, 6, 1, 2, 5, 3, 4 (B) 7, 1, 2, 6, 3, 4, 5 (C) 1, 2, 7, 3, 6, 5, 4 (D) 1, 7, 4, 3, 2, 6, 5 2. 利 用 雙 向 佇 列 循 序 輸 入 1, 2, 3, 4, 5, 6 及 7, 則 下 列 那 些 結 果 為 可 能 的 輸 出 排 列? (A) 5174236 (B) 5172346 (C) 5172436 (D) 5173426 4-5 佇 列 在 電 腦 資 料 處 理 的 應 用 佇 列 在 電 腦 科 學 中 的 應 用 相 當 廣 泛, 例 如 電 腦 模 擬 (Computer Simulation) 作 業 系 統 (OS) 電 腦 資 源 的 分 配 都 是 利 用 佇 列 來 表 示 雖 然 佇 列 與 堆 疊 都 可 以 利 用 陣 列 來 實 作, 但 是, 佇 列 在 電 腦 中 的 應 用 與 堆 疊 大 不 相 同, 因 此, 佇 列 大 多 運 用 於 硬 體 流 程 的 控 制 並 且 由 於 佇 列 具 有 先 進 先 出 (First In First Out) 的 特 性, 所 以, 經 常 被 運 用 在 電
CHAPTER 4 隨 書 光 碟 4-25 腦 的 作 業 系 統, 以 安 排 電 腦 執 行 工 作 (Job) 的 優 先 順 序 在 電 腦 的 硬 體 結 構 中, 最 常 應 用 於 緩 衝 區 上, 舉 例 來 說, 有 時 候 電 腦 在 執 行 某 一 龐 大 的 應 用 程 式 時, 系 統 反 應 通 常 變 得 非 常 遲 頓, 對 於 使 用 者 由 鍵 盤 輸 入 的 資 料, 常 常 會 有 漏 接 的 情 況, 因 此 設 計 師 在 電 腦 的 記 憶 體 上, 規 劃 出 緩 衝 區, 一 旦 使 用 者 於 鍵 盤 上 輸 入 資 料 時, 便 會 先 儲 存 於 緩 衝 區 上, 等 CPU 不 忙 碌 時, 再 一 個 個 讀 至 記 憶 體 處 理, 因 此 比 較 不 會 有 資 料 漏 接 的 情 況, 而 緩 衝 區 的 結 構 本 身 就 是 一 種 先 進 先 出 的 佇 列 結 構, 如 下 圖 所 示 資 料 來 源 :http://www.chwa.com.tw/tresource/hs/book2/ch7/7-3.htm
4-26 1. 佇 列 在 電 腦 科 學 中 的 應 用 相 當 廣 泛, 下 列 何 者 是 佇 列 的 應 用? (A) 電 腦 模 擬 (B) 作 業 系 統 (C) 電 腦 資 源 的 分 配 (D) 以 上 皆 是 2. 假 設 現 在 有 一 位 同 學 想 列 印 三 個 檔 案 的 文 件 資 料, 接 下 來 進 行 一 連 列 的 動 作 如 下 : T1 時 間 : 按 列 印 A.doc T2 時 間 : 按 列 印 B.doc T3 時 間 : 按 列 印 C.doc 請 問 以 上 三 個 檔 案 在 列 印 機 佇 列 中 的 順 序 為 何? (A) (B) (C) (D)