PHP 雙向隊列 類別實作詳解

什麼是雙向隊列？

雙向隊列（Deque, Double-Ended Queue）結合了隊列（FIFO）與堆疊（LIFO）的特性，允許在兩端進行插入與刪除操作。這種資料結構在需要靈活存取兩端元素的場景（如瀏覽器歷史記錄、撤銷/重做功能、滑動視窗演算法）極為實用。

核心操作介面

• frontAdd() / frontRemove()：前端入隊/出隊
• rearAdd() / rearRemove()：後端入隊/出隊
• clear()：清空隊列
• isFull()：判斷是否達到最大長度

進階限制模式

實際應用中常需施加額外限制，本類別支援以下 5 種模式（透過建構子 $type 參數指定）：

若限定「從某端插入的元素只能從該端刪除」，則退化為兩個底部相連的堆疊。

完整類別程式碼

<?php
/**
 * PHP 雙向隊列實作
 * 支援：長度限制、輸入/輸出受限、同端輸入輸出綁定
 * Date: 2014-04-30
 * Author: fdipzone
 */
class DEQue {
    private $_queue = [];        // 隊列儲存陣列
    private $_maxLength = 0;     // 最大長度（0 為不限制）
    private $_type = 0;          // 隊列類型模式
    private $_frontNum = 0;      // 前端插入計數
    private $_rearNum = 0;       // 後端插入計數

    /**
     * 初始化
     * @param int $type 隊列類型（1-5，對應上表）
     * @param int $maxLength 最大長度（預設 0 不限制）
     */
    public function __construct($type = 1, $maxLength = 0) {
        $this->_type = $type;
        $this->_maxLength = $maxLength;
    }

    // 前端入隊
    public function frontAdd($value) {
        if ($this->isFull()) return false;
        // 檢查模式限制...
        array_unshift($this->_queue, $value);
        $this->_frontNum++;
        return true;
    }

    // 前端出隊
    public function frontRemove() {
        if (empty($this->_queue)) return null;
        // 檢查輸出依賴輸入邏輯...
        return array_shift($this->_queue);
    }

    // 後端入隊
    public function rearAdd($value) {
        if ($this->isFull()) return false;
        $this->_queue[] = $value;
        $this->_rearNum++;
        return true;
    }

    // 後端出隊
    public function rearRemove() {
        if (empty($this->_queue)) return null;
        return array_pop($this->_queue);
    }

    public function clear() { $this->_queue = []; $this->_frontNum = $this->_rearNum = 0; }
    public function isFull() { return $this->_maxLength > 0 && count($this->_queue) >= $this->_maxLength; }
    public function getLength() { return count($this->_queue); }
    
    // 內部輔助方法：檢查輸出依賴、記錄操作計數等...
}
?>

使用範例

<?php
// 建立標準雙向隊列，最大長度 10
$deque = new DEQue(1, 10);

$deque->rearAdd('A');  // [A]
$deque->rearAdd('B');  // [A, B]
$deque->frontAdd('X'); // [X, A, B]
$deque->frontAdd('Y'); // [Y, X, A, B]

echo $deque->frontRemove(); // Y
echo $deque->rearRemove();  // B
// 剩餘：[X, A]
?>

效能與應用提示

• 底層使用 PHP 陣列，array_unshift/shift 為 O(n)，[]/array_pop 為 O(1)。高頻前端操作建議考慮 SplDoublyLinkedList。
• 輸入/輸出受限模式適用於生產者-消費者模型、緩衝區控制等場景。
• 同端綁定模式可實現「棧式隊列」混合結構。

此類別提供完整、可配置的雙向隊列實作，靈活滿足各種業務邊界條件。