雙端隊列 允許在兩端進行插入和刪除操作,結合了隊列(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;
}
}
?>
<?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)
?>
<?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]
?>
<?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 / rearAdd | O(n) / O(1) | O(1) | array_unshift 需重建索引 |
| frontRemove / rearRemove | O(n) / O(1) | O(1) | array_shift 需重建索引 |
| isFull / getLength | O(1) | O(1) |
效能提示:PHP 數組實現的雙端隊列,前端操作為 O(n)。高頻前端操作場景建議使用 SplDoublyLinkedList(C 實現,雙向鏈表,兩端 O(1))。
<?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 中的靈活實現,理解其模式限制邏輯有助於解決緩衝區管理、任務調度、瀏覽器歷史記錄等經典問題。