什麼是雙端佇列

Deque (Double-Ended Queue) 兼具堆疊與佇列特性，允許在兩端進行插入與移除操作。核心操作四種：

• push (addFirst)：前端插入
• pop (removeFirst)：前端移除並回傳
• inject (addLast)：尾端插入
• eject (removeLast)：尾端移除並回傳

所有操作時間複雜度為 O(1)。

完整類別實作

<?php
class DoubleQueue
{
    private $queue = [];

    // 尾端入隊
    public function addLast($value)
    {
        return array_push($this->queue, $value);
    }

    // 尾端出隊
    public function removeLast()
    {
        return array_pop($this->queue);
    }

    // 頭部入隊
    public function addFirst($value)
    {
        return array_unshift($this->queue, $value);
    }

    // 頭部出隊
    public function removeFirst()
    {
        return array_shift($this->queue);
    }

    // 清空佇列
    public function makeEmpty()
    {
        $this->queue = [];
    }

    // 取得頭部元素 (不移除)
    public function getFirst()
    {
        return reset($this->queue);
    }

    // 取得尾部元素 (不移除)
    public function getLast()
    {
        return end($this->queue);
    }

    // 取得長度
    public function getLength()
    {
        return count($this->queue);
    }
}
?>

簡化版 Deque 實作 (教學用)

<?php
class Deque
{
    public $queue = [];
    public $length = 0;

    public function frontAdd($node)
    {
        array_unshift($this->queue, $node);
        $this->countQueue();
    }

    public function frontRemove()
    {
        $node = array_shift($this->queue);
        $this->countQueue();
        return $node;
    }

    public function rearAdd($node)
    {
        array_push($this->queue, $node);
        $this->countQueue();
    }

    public function rearRemove()
    {
        $node = array_pop($this->queue);
        $this->countQueue();
        return $node;
    }

    private function countQueue()
    {
        $this->length = count($this->queue);
    }
}

// 使用範例
$fruit = new Deque();
echo $fruit->length . "<br>"; // 0

$fruit->frontAdd("Apple");
$fruit->rearAdd("Watermelon");

echo '<pre>';
print_r($fruit);
echo '</pre>';
/* 輸出：
0
Deque Object
(
    [queue] => Array
        (
            [0] => Apple
            [1] => Watermelon
        )
    [length] => 2
)
*/
?>

應用場景

• 瀏覽器歷史記錄：前進/後退雙向操作。
• 滑動視窗演算法：固定大小視窗的最大/最小值追蹤。
• 任務排程：優先級任務可插隊頭，一般任務加入隊尾。
• 緩衝區管理：資料流暫存與讀取。

效能提示

PHP 陣列底層是有序雜湊表，array_unshift/shift 需重新索引，大量資料時非真正 O(1)。高效能需求建議：

1. 使用 SplDoublyLinkedList (PHP 內建雙向鏈結清單)，原生支援 push/pop/shift/unshift 皆為 O(1)。
2. 或自行實作環狀緩衝區。

結語

雙端佇列是解決「雙向處理」問題的利器。PHP 透過陣列函數快速原型化，配合 SplDoublyLinkedList 可滿足生產環境效能需求。理解其操作語意，有助於設計更優雅的演算法。