PHP 實作雙向佇列：支援長度限制、輸入輸出受限與端點綁定模式

雙向佇列允許在兩端進行插入與刪除操作，兼具堆疊與佇列特性。本文實作 DEQue 類別，支援六種操作模式、最大長度限制、輸入/輸出受限、端點綁定（先進先出/後進先出）等進階特性，適合資料結構教學與特定業務場景。

六種操作模式

核心程式碼

<?php
class DEQue {
    private $_queue = [];
    private $_maxLength = 0;
    private $_type = 1;
    private $_frontNum = 0;
    private $_rearNum = 0;

    public function __construct($type = 1, $maxlength = 0) {
        $this->_type = in_array($type, range(1,6)) ? $type : 1;
        $this->_maxLength = intval($maxlength);
    }

    public function frontAdd($data = null) {
        if ($this->_type == 3) return false; // 前端輸入受限
        if ($data !== null && !$this->isFull()) {
            array_unshift($this->_queue, $data);
            $this->setAddNum(1);
            return true;
        }
        return false;
    }

    public function frontRemove() {
        if ($this->_type == 2) return null; // 前端輸出受限
        if (!$this->checkRemove(1)) return null;
        if ($this->getLength() > 0) {
            $data = array_shift($this->_queue);
            $this->setRemoveNum(1);
            return $data;
        }
        return null;
    }

    public function rearAdd($data = null) {
        if ($this->_type == 5) return false; // 後端輸入受限
        if ($data !== null && !$this->isFull()) {
            array_push($this->_queue, $data);
            $this->setAddNum(2);
            return true;
        }
        return false;
    }

    public function rearRemove() {
        if ($this->_type == 4) return null; // 後端輸出受限
        if (!$this->checkRemove(2)) return null;
        if ($this->getLength() > 0) {
            $data = array_pop($this->_queue);
            $this->setRemoveNum(2);
            return $data;
        }
        return null;
    }

    public function clear() {
        $this->_queue = [];
        $this->_frontNum = $this->_rearNum = 0;
        return true;
    }

    public function isFull() {
        return $this->_maxLength > 0 && $this->_maxLength == $this->getLength();
    }

    private function getLength() { return count($this->_queue); }

    private function setAddNum($endpoint) {
        if ($this->_type == 6) {
            $endpoint == 1 ? $this->_frontNum++ : $this->_rearNum++;
        }
    }

    private function setRemoveNum($endpoint) {
        if ($this->_type == 6) {
            $endpoint == 1 ? $this->_frontNum-- : $this->_rearNum--;
        }
    }

    private function checkRemove($endpoint) {
        if ($this->_type == 6) {
            return $endpoint == 1 ? $this->_frontNum > 0 : $this->_rearNum > 0;
        }
        return true;
    }
}
?>

使用範例

<?php
require 'DEQue.class.php';

// 範例 1：標準雙向佇列
$obj = new DEQue();
$obj->frontAdd('a'); // 前端入
$obj->rearAdd('b');  // 後端入
$obj->frontAdd('c');
$obj->rearAdd('d');
// 內部順序：c, a, b, d

$result = [];
$result[] = $obj->rearRemove();  // d
$result[] = $obj->rearRemove();  // b
$result[] = $obj->frontRemove(); // c
$result[] = $obj->frontRemove(); // a
print_r($result); // 輸出順序：d, b, c, a

// 範例 2：前端僅輸出、最大長度 5
$obj = new DEQue(3, 5);
$insert = [];
$insert[] = $obj->rearAdd('a'); // true
$insert[] = $obj->rearAdd('b'); // true
$insert[] = $obj->frontAdd('c'); // false（前端不可輸入）
$insert[] = $obj->rearAdd('d'); // true
$insert[] = $obj->rearAdd('e'); // true
$insert[] = $obj->rearAdd('f'); // true
$insert[] = $obj->rearAdd('g'); // false（滿）
var_dump($insert);

// 範例 3：端點綁定模式
$obj = new DEQue(6);
$obj->frontAdd('a');
$obj->frontAdd('b');
$obj->frontAdd('c');
$obj->rearAdd('d');

$result = [];
$result[] = $obj->rearRemove();  // d
$result[] = $obj->rearRemove();  // null（後端無輸入記錄）
$result[] = $obj->frontRemove(); // c
$result[] = $obj->frontRemove(); // b
$result[] = $obj->frontRemove(); // a
var_dump($result);

應用場景

• 瀏覽器歷史記錄：模式 1，前端新增造訪，兩端可導航。
• 訊息佇列與堆疊混合：模式 2/3，一端生產一端消費。
• 撤銷/重做管理器：模式 6，操作從一端進必須從同端出，確保順序正確。
• 緩衝區流控：搭配 maxlength 實現背壓機制。

效能說明

• 基於 PHP 陣列實現，array_unshift/shift 為 O(n)，array_push/pop 為 O(1)。
• 高頻前端操作場景建議改用 SplDoublyLinkedList (SPL) 獲得 O(1) 雙端操作。
• 記憶體佔用隨佇列增長線性增加，maxlength 可防止失控。

DEQue 以清晰的模式定義封裝了複雜的端點限制邏輯，是理解雙向佇列變體與實作受限緩衝區的優良教學與實務參考。