萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 雙端隊列 (Deque) 實現:支持長度限制、輸入/輸出受限與棧模式

一、數據結構原理

雙端隊列 允許在兩端進行插入和刪除操作,結合了隊列(FIFO)與棧(LIFO)的特性。本實現支持 6 種運行模式:

類型代碼前端後端典型用途
標準雙端隊列1進/出進/出通用緩衝區
前端只入2只進進/出優先級隊列(高優先級插前端)
前端只出3只出進/出後進先出棧輔助
後端只入4進/出只進普通隊列(入隊在後端)
後端只出5進/出只出先進先出隊列輔助
端點綁定模式6進出綁定進出綁定兩棧底部相連(棧對)

二、完整類實現

<?php
/**
 * DEQue - 雙端隊列實現
 * 支持:長度限制、輸入受限、輸出受限、端點綁定
 */
class DEQue {
    private $_queue = [];
    private $_maxLength = 0;  // 0 = 無限制
    private $_type = 1;       // 1-6 模式
    private $_frontNum = 0;   // 前端入隊計數(模式6用)
    private $_rearNum = 0;    // 後端入隊計數(模式6用)

    public function __construct($type = 1, $maxlength = 0) {
        $this->_type = in_array($type, range(1, 6)) ? $type : 1;
        $this->_maxLength = (int)$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->getLength() >= $this->_maxLength;
    }

    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;
    }
}
?>

三、使用示例

示例 1:標準雙端隊列(類型 1,無長度限制)

<?php
require 'DEQue.class.php';
$obj = new DEQue();

$obj->frontAdd('a'); // [a]
$obj->rearAdd('b');  // [a, b]
$obj->frontAdd('c'); // [c, a, b]
$obj->rearAdd('d');  // [c, a, b, d]

// 出隊順序:後端兩次 -> 前端兩次
$result = [
    $obj->rearRemove(), // d
    $obj->rearRemove(), // b
    $obj->frontRemove(), // c
    $obj->frontRemove()  // a
];
print_r($result); // Array([0]=>d, [1]=>b, [2]=>c, [3]=>a)
?>

示例 2:前端只出、長度限制 5(類型 3)

<?php
$obj = new DEQue(3, 5); // 前端只能出,最大長度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); // [true, true, false, true, true, true, false]
?>

示例 3:端點綁定模式(類型 6,像兩個棧底部相連)

<?php
$obj = new DEQue(6); // 輸出依賴輸入:從哪端進必須從哪端出

$obj->frontAdd('a'); // 前端棧: [a]
$obj->frontAdd('b'); // 前端棧: [b, a]
$obj->frontAdd('c'); // 前端棧: [c, b, a]
$obj->rearAdd('d');  // 後端棧: [d]

$result = [];
$result[] = $obj->rearRemove(); // d (後端棧彈出)
$result[] = $obj->rearRemove(); // null (後端棧空,不能從前端棧取)
$result[] = $obj->frontRemove(); // c
$result[] = $obj->frontRemove(); // b
$result[] = $obj->frontRemove(); // a
print_r($result); // [d, null, c, b, a]
?>

四、效能特性與應用場景

操作時間復雜度空間復雜度說明
frontAdd / rearAddO(n) / O(1)O(1)array_unshift 需重建索引
frontRemove / rearRemoveO(n) / O(1)O(1)array_shift 需重建索引
isFull / getLengthO(1)O(1)

效能提示:PHP 數組實現的雙端隊列,前端操作為 O(n)。高頻前端操作場景建議使用 SplDoublyLinkedList(C 實現,雙向鏈表,兩端 O(1))。

五、SplDoublyLinkedList 替代方案

<?php
$dll = new SplDoublyLinkedList();
$dll->push('a');      // 後端入隊
$dll->unshift('b');   // 前端入隊
$dll->pop();          // 後端出隊
$dll->shift();        // 前端出隊

// 設置模式:IT_MODE_LIFO (棧) / IT_MODE_FIFO (隊列) / IT_MODE_DELETE / IT_MODE_KEEP
$dll->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO | SplDoublyLinkedList::IT_MODE_KEEP);
foreach ($dll as $val) echo $val . "\n";
?>

DEQue 類展示了數據結構在 PHP 中的靈活實現,理解其模式限制邏輯有助於解決緩衝區管理、任務調度、瀏覽器歷史記錄等經典問題。

copyright © 萬盛學電腦網 all rights reserved