Python 資料結構：佇列（Queue）(04)

在學習資料結構時，佇列（Queue） 是一種基礎且重要的結構。它的運作規則非常直觀，就像日常生活中的排隊一樣：先到的人先被服務，後來的人只能排在隊伍最後。正因為這種簡單卻嚴謹的 先進先出（FIFO） 特性，佇列成為電腦科學中許多系統與演算法的核心工具。
從作業系統的行程排程，到印表機的任務管理，再到人工智慧演算法中的廣度優先搜尋（BFS），佇列都扮演著不可或缺的角色。本文將帶你從基礎原理出發，逐步學會如何在 Python 中建立並操作佇列，並理解它在真實世界中的應用價值。

佇列的核心概念

佇列由一系列節點組成，並且支援三個核心操作：

• 入隊（enqueue）：將新元素加入佇列尾端。
• 出隊（dequeue）：移除並返回佇列前端的元素，確保先進先出的規則。
• 窺視（peek）：查看前端元素的值但不移除，用於檢查下一個處理項目。

透過這三個操作，佇列能夠以有序且穩定的方式處理資料流程。

Queue 類別

初始化結構

佇列需要追蹤前端（head）和尾端（tail），並可選擇設定最大容量限制。

class Queue:
    def __init__(self, max_size=None):
        self.head = None
        self.tail = None
        self.max_size = max_size  # 最大容量
        self.size = 0             # 當前大小

這樣的設計不僅能支援一般的無界佇列，還能實作出有界佇列，避免溢位。

管理佇列的方法

為了提升佇列的可靠性與實用性，我們設計了幾個輔助方法：

• get_size()：回傳目前佇列的大小。
• has_space()：檢查是否還能加入新元素（防止溢位）。
• is_empty()：檢查佇列是否為空（防止下溢）。

這些檢查機制確保佇列在任何情況下都能安全運作。

peek() 方法

peek() 方法讓我們能夠查看佇列前端的值而不移除它：

def peek(self):
    return self.head.get_value()

在空佇列呼叫 peek() 可能會造成錯誤，因此需要額外檢查，讓操作更安全。

peek() 方法對於需要檢查下一個要處理項目但不實際移除它的場景非常有用，例如在處理任務前先確認任務類型。

實作 enqueue() 方法

enqueue() 方法是將元素加入佇列的核心功能：

def enqueue(self, value):
    if self.has_space():
        item_to_add = Node(value)
        print("Adding " + str(item_to_add.get_value()) + " to the queue!")
        if self.is_empty():
            self.head = item_to_add
            self.tail = item_to_add
        else:
            self.tail.set_next_node(item_to_add)
            self.tail = item_to_add
        self.size += 1
    else:
        print("Sorry, no more room!")

加入元素時，需考慮以下三種情境：

1. 空佇列：新元素同時成為 head 與 tail。
2. 非空佇列：新元素接在尾端，並更新 tail。
3. 已滿佇列：無法新增，避免溢位。

實作 dequeue() 方法

dequeue() 方法從佇列前端移除並返回元素：

def dequeue(self):
    if not if self.has_space(): 
        item_to_remove = self.head
        print("Removing " + str(item_to_remove.get_value()) + " from the queue!")

        if self.size == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.get_next_node()

        self.size -= 1
        return item_to_remove.get_value()
    else:
        print("This queue is totally empty!")

同樣地，出隊操作需要處理不同狀況：

• 空佇列：禁止移除，避免下溢。
• 單一元素：移除後需將 head 與 tail 重設為 None。
• 多元素佇列：更新 head 指向下一個節點。

佇列操作的視覺化理解

透過視覺化方式理解佇列的運作：元素從尾部進入（enqueue），從前端離開（dequeue）。這種 FIFO 的特性使佇列成為處理按序任務的理想資料結構。

在實際應用中，佇列常用於任務調度、緩衝區管理、以及廣度優先搜尋演算法等場景。

防止溢位與下溢的重要性

• 溢位（Overflow）：有界佇列滿時再加入新元素，會導致資源耗盡。
• 下溢（Underflow）：嘗試從空佇列移除元素，會造成錯誤。

透過 has_space() 和 is_empty() 方法，能有效避免這些情況，確保佇列的正確性與健壯性。

結語

佇列看似簡單，卻是許多進階資料結構與演算法的基礎。透過本文的學習，你不僅能夠自己實作出一個功能完整的 Queue 類別，更能理解它在軟體開發與系統設計中的重要性。只要掌握了佇列，你就多了一項處理資料流與任務調度的強大工具，這將成為你邁向更複雜資料結構與演算法的必經之路。