資料結構：佇列
佇列（Queue）是資料結構中常見的一種線性結構，它遵循「先進先出」（FIFO, First In First Out）的原則。這種特性使得佇列在許多應用場景中非常實用，例如工作排程、印表機任務管理、廣度優先搜尋等。作為一位資料結構專家，本文將帶領你深入理解佇列的基本概念、操作方法、實作方式及其在程式設計中的應用。
一、佇列的定義
佇列是一種只允許在一端插入資料（稱為”尾端”Rear），而在另一端刪除資料（稱為”前端”Front）的線性資料結構。這種結構類似於生活中排隊的情境，最先進入佇列的人最先離開。
二、佇列的特性
- 先進先出（FIFO）：最先進入佇列的元素最先被移除。
- 只能從尾端插入，從前端刪除。
- 操作時間複雜度為 O(1)：基本的入列與出列操作均為常數時間完成。
三、佇列的基本操作
1. 初始化佇列
建立一個空佇列，準備進行後續操作。
2. 入列（Enqueue）
將資料放入佇列尾端。
3. 出列（Dequeue）
移除佇列前端的資料。
4. 取得前端元素（Front）
獲取佇列前端的元素，但不移除。
5. 判斷佇列是否為空（IsEmpty）
檢查佇列內是否沒有元素。
四、佇列的程式碼範例
以下為 C++ 範例：
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
q.push(10);
q.push(20);
q.push(30);
cout << "佇列前端元素: " << q.front() << endl; // 10
q.pop();
cout << "出列後，佇列前端元素: " << q.front() << endl; // 20
cout << "佇列是否為空: " << (q.empty() ? "是" : "否") << endl;
return 0;
}五、佇列的實作方式
1. 陣列實作
用陣列作為底層結構，但需要注意佇列可能會隨著元素出列而造成”空間浪費”，通常會使用「循環佇列」解決此問題。
2. 鏈結串列實作
使用單向鏈結串列，每個節點存儲資料及下一個節點的指標。無需固定大小，適合資料量變動的場景。
六、佇列的分類
1. 普通佇列
遵循 FIFO 原則的基本佇列。
2. 雙端佇列（Deque）
允許在前端和尾端都可插入和刪除元素。
3. 優先佇列（Priority Queue）
元素具有優先級，高優先級的元素會先出列。
七、佇列的應用場景
- 工作排程：系統根據請求到達的順序安排執行。
- 印表機佇列：列印任務按提交順序處理。
- 廣度優先搜尋（BFS）：圖論演算法中廣泛使用佇列輔助遍歷節點。
- 請求緩衝區：網路請求、資料流處理等場景常見佇列應用。
八、佇列的時間與空間複雜度
| 操作 | 時間複雜度 |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Front | O(1) |
| IsEmpty | O(1) |
空間複雜度：O(n)，n 為佇列中元素數量。
九、佇列的優缺點
優點：
- 操作簡單，高效能。
- 適合順序處理的場景。
缺點：
- 陣列實作可能會有空間浪費。
- 不適合需要隨機存取的場景。
十、最佳實踐
- 使用 STL 提供的
queue類別，避免手動實作基本功能。 - 若需要兩端插入和刪除操作，考慮使用雙端佇列（
deque）。 - 根據資料量及操作頻率選擇陣列或鏈結串列實作方式。
十一、結論
佇列是一種簡單但非常實用的資料結構，適合處理順序性、流程性任務。理解佇列的特性與操作方式，不僅能提升程式設計效率，還能在解決問題時選擇最適合的資料結構，提高程式性能與可讀性。