PHP實現鍊錶隊列：使用帶尾指針實現先進先出隊列

什麼是鍊錶隊列

隊列是一種先進先出（FIFO）的數據結構，它只允許在隊尾添加元素，在隊頭刪除元素。鍊式隊列則是通過鍊錶實現的隊列結構，能夠動態擴展隊列的大小。鍊式隊列廣泛應用於許多需要先進先出特性的場景中。

鍊錶隊列實現

鍊錶隊列使用鍊錶結構來實現，鍊錶節點包含兩個部分：數據域和指針域。指針域指向下一個鍊錶節點。隊列的實現依賴於隊頭和隊尾指針，隊頭指針指向隊列中的第一個元素，而隊尾指針指向最後一個元素。

鍊錶節點定義

鍊錶節點由兩部分組成：數據域和指針域，指針域指向下一個節點。以下是PHP實現鍊錶節點的代碼：

 
class Node {
    public $data;
    public $next;
}

隊列定義

隊列定義包括隊頭和隊尾兩個指針。隊尾指針指向隊列中的最後一個元素，隊頭指針指向第一個元素。隊列的長度隨著元素的加入而增加，以下是PHP實現隊列的代碼：

 
class Queue {
    private $head;
    private $tail;

    public function __construct() {
        $this->head = null;
        $this->tail = null;
    }

    public function isEmpty() {
        return $this->head === null;
    }

    public function enqueue($data) {
        $newNode = new Node();
        $newNode->data = $data;
        $newNode->next = null;

        if ($this->isEmpty()) {
            $this->head = $this->tail = $newNode;
        } else {
            $this->tail->next = $newNode;
            $this->tail = $newNode;
        }
    }

    public function dequeue() {
        if ($this->isEmpty()) {
            return null;
        }

        $data = $this->head->data;
        $this->head = $this->head->next;

        if ($this->head === null) {
            $this->tail = null;
        }

        return $data;
    }
}

使用場景

鍊錶隊列常用於以下場景：

• 廣度優先搜索算法（BFS）
• 線程池任務分配
• 打印隊列等

總結

鍊錶隊列是實現先進先出（FIFO）數據結構的常用方式，適用於許多需要按順序處理任務的場景。通過鍊錶的靈活性，隊列可以動態擴展，適應各種應用需求。鍊錶隊列的實現不僅簡單且高效，是程序設計中不可或缺的工具。