04: 本節課介紹佇列的基本概念及其在數據處理中的應用。

佇列

#

佇列是一種特殊的線性表，其操作受限於先進先出（FIFO）的原則。這意味著元素只能從佇列的一端（隊尾）新增，而從另一端（隊頭）刪除。佇列的這種操作方式類似於人們在日常生活中排隊的情景，確保了數據處理的有序性。

順序佇列與鏈式佇列

#

佇列可以通過順序存儲（使用陣列）和鏈式存儲（使用鏈表）兩種方式實現。順序佇列容易產生 “假溢出” 問題，而鏈式佇列則更靈活，無須關心存儲空間的限制。

操作詳解

#

在順序佇列中，新增操作（入隊）在隊尾進行，刪除操作（出隊）在隊頭進行，對於循環佇列可有效解決 “假溢出” 問題。鏈式佇列的操作則更為直接，新增和刪除操作均在 O(1) 時間內完成。不論哪種佇列，查找操作需要遍歷整個佇列，時間複雜度為 O(n)。

Go語言實現佇列

#

以下是用 Go 語言實現的佇列操作示例。

type Queue struct {
    items []int
}

// 入隊操作
func (q *Queue) Enqueue(item int) {
    q.items = append(q.items, item)
}

// 出隊操作
func (q *Queue) Dequeue() int {
    if len(q.items) == 0 {
        return -1 // 佇列為空
    }
    item := q.items[0]
    q.items = q.items[1:]
    return item
}

// 檢查佇列是否為空
func (q *Queue) IsEmpty() bool {
    return len(q.items) == 0
}

小結

#

佇列，作為一種先進先出的線性表結構，在數據處理上保證了元素的有序性。它在順序存儲和鏈式存儲下都有各自的特點，但無論如何實現，佇列的基本操作—增加、刪除和查找—都是為了維護數據的先進先出原則。佇列在計算機科學中被廣泛應用於各種場景，如任務調度、資料流處理等。