PHP 雙端隊列 實作：支援長度限制、輸入/輸出受限、同端進出模式、完整資料結構教學

Deque (Double-Ended Queue) 結合 Queue (FIFO) 與 Stack (LIFO) 特性，允許兩端插入刪除。本文實作功能完整的 DEQue 類，支援 6 種操作模式、長度上限、同端進出限制，附帶詳細註解與測試案例，適合資料結構教學與實務應用。

Deque 核心操作與模式定義

完整類實作

<?php
class DEQue {
    private array $queue = [];
    private int $maxLength = 0; // 0 = 無限制
    private int $type = 1;      // 模式 1-6
    private int $frontCount = 0; // 前端插入計數 (模式6用)
    private int $rearCount = 0;  // 後端插入計數 (模式6用)

    public function __construct(int $type = 1, int $maxLength = 0) {
        $this->type = in_array($type, range(1,6)) ? $type : 1;
        $this->maxLength = max(0, $maxLength);
    }

    /** 前端插入 */
    public function frontAdd(mixed $data): bool {
        if ($this->type === 3) return false; // 前端禁止插入
        if ($data === null || $this->isFull()) return false;
        array_unshift($this->queue, $data);
        $this->recordAdd(1);
        return true;
    }

    /** 前端移除 */
    public function frontRemove(): mixed {
        if ($this->type === 2) return null; // 前端禁止移除
        if (!$this->checkRemove(1)) return null;
        if (empty($this->queue)) return null;
        $data = array_shift($this->queue);
        $this->recordRemove(1);
        return $data;
    }

    /** 後端插入 */
    public function rearAdd(mixed $data): bool {
        if ($this->type === 5) return false; // 後端禁止插入
        if ($data === null || $this->isFull()) return false;
        array_push($this->queue, $data);
        $this->recordAdd(2);
        return true;
    }

    /** 後端移除 */
    public function rearRemove(): mixed {
        if ($this->type === 4) return null; // 後端禁止移除
        if (!$this->checkRemove(2)) return null;
        if (empty($this->queue)) return null;
        $data = array_pop($this->queue);
        $this->recordRemove(2);
        return $data;
    }

    public function clear(): bool {
        $this->queue = [];
        $this->frontCount = $this->rearCount = 0;
        return true;
    }

    public function isFull(): bool {
        return $this->maxLength > 0 && count($this->queue) >= $this->maxLength;
    }

    public function getLength(): int {
        return count($this->queue);
    }

    public function toArray(): array {
        return $this->queue;
    }

    // === 私有輔助 ===
    private function recordAdd(int $end): void {
        if ($this->type === 6) {
            if ($end === 1) $this->frontCount++;
            else $this->rearCount++;
        }
    }

    private function recordRemove(int $end): void {
        if ($this->type === 6) {
            if ($end === 1) $this->frontCount--;
            else $this->rearCount--;
        }
    }

    private function checkRemove(int $end): bool {
        if ($this->type !== 6) return true;
        return ($end === 1) ? $this->frontCount > 0 : $this->rearCount > 0;
    }
}
?>

測試案例與輸出

<?php
require 'DEQue.php';

echo "=== 測試 1: 標準模式 (無限長度) ===\n";
$dq = new DEQue(1);
$dq->frontAdd('a'); $dq->rearAdd('b'); $dq->frontAdd('c'); $dq->rearAdd('d');
// 佇列內部順序: c, a, b, d
$out = [];
while ($dq->getLength()) $out[] = $dq->rearRemove(); // 後端全出: d, b, a, c
echo "後端依序移除: " . implode(', ', $out) . "\n";
// 輸出: 後端依序移除: d, b, a, c

echo "\n=== 測試 2: 模式3 (前端僅出) + 長度限制5 ===\n";
$dq = new DEQue(3, 5);
$inserts = [
    $dq->rearAdd('a'), $dq->rearAdd('b'), $dq->frontAdd('c'), // 失敗
    $dq->rearAdd('d'), $dq->rearAdd('e'), $dq->rearAdd('f'), $dq->rearAdd('g'), // 第7次失敗
];
echo "插入結果: " . implode(', ', array_map(fn($v) => $v ? 'T' : 'F', $inserts)) . "\n";
// 輸出: 插入結果: T, T, F, T, T, T, F

echo "\n=== 測試 3: 模式6 (同端進出) ===\n";
$dq = new DEQue(6);
$dq->frontAdd('a'); $dq->frontAdd('b'); $dq->frontAdd('c');
$dq->rearAdd('d');
// 嘗試從後端移除兩次 (第二次失敗，因後端只進了一個)
$out = [
    $dq->rearRemove(), // d
    $dq->rearRemove(), // null
    $dq->frontRemove(), // c
    $dq->frontRemove(), // b
    $dq->frontRemove(), // a
];
echo "移除序列: " . implode(', ', array_map(fn($v) => $v ?? 'NULL', $out)) . "\n";
// 輸出: 移除序列: d, NULL, c, b, a
?>

時間複雜度分析

高效能場景建議：若頻繁前端操作，改用 SplDoublyLinkedList (內建雙向鏈表，兩端 O(1)) 或自行實作環狀緩衝區。

SplDoublyLinkedList 替代方案 (PHP 內建、高效)

<?php
$dll = new SplDoublyLinkedList();
$dll->push('a');  // 後端入
$dll->unshift('b'); // 前端入
$dll->push('c');
echo "前端出: " . $dll->shift() . "\n"; // b
echo "後端出: " . $dll->pop() . "\n";   // c
echo "剩餘: " . $dll->count() . "\n";   // 1 (a)
// 可設定迭代模式: $dll->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO | SplDoublyLinkedList::IT_MODE_KEEP);
?>

應用場景

• 瀏覽器歷史記錄：後進先出 (Stack) + 前進後退 (Deque)。
• 滑動視窗演算法：固定長度 Deque 維護窗口最大/最小值 (單調隊列)。
• 任務調度：優先任務前端插入，普通任務後端插入。
• 撤銷/重做：兩棧模式 (模式 6)，操作入前端，撤銷出前端，重做入後端。
• 緩衝區/流控制：生產者後端入，消費者前端出，滿則阻塞/丟棄。

DEQue 類展示了陣列模擬雙端隊列的完整邏輯與模式控制，配合 SplDoublyLinkedList 內建高效實作，可滿足從教學驗證到高效能生產環境的多樣需求。