php实现双向队列

PHP 实现双向队列的方法

双向队列（Deque，Double-ended Queue）是一种允许在队列两端进行插入和删除操作的数据结构。PHP 中可以通过数组或 SplDoublyLinkedList 类实现双向队列。

使用数组实现双向队列

PHP 的数组本身支持灵活的操作，可以模拟双向队列的行为。以下是核心操作的实现方式：

初始化队列

$deque = [];

从队首插入元素

array_unshift($deque, $value);

从队尾插入元素

array_push($deque, $value);

从队首删除元素

$value = array_shift($deque);

从队尾删除元素

$value = array_pop($deque);

检查队列是否为空

$isEmpty = empty($deque);

使用 SplDoublyLinkedList 实现双向队列

PHP 的 SPL（Standard PHP Library）提供了 SplDoublyLinkedList 类，原生支持双向队列操作。以下是具体用法：

初始化双向队列

$deque = new SplDoublyLinkedList();

设置迭代模式（可选）

$deque->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO); // 先进先出（队列）
// 或
$deque->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO); // 后进先出（栈）

从队首插入元素

$deque->unshift($value);

从队尾插入元素

$deque->push($value);

从队首删除元素

$value = $deque->shift();

从队尾删除元素

$value = $deque->pop();

检查队列是否为空

$isEmpty = $deque->isEmpty();

获取队列长度

$length = $deque->count();

性能对比

• 数组实现：适合简单场景，但频繁的 array_shift 操作会导致重新索引，性能较低（时间复杂度 O(n)）。
• SplDoublyLinkedList：专为双向操作优化，所有操作的时间复杂度均为 O(1)，适合高性能需求场景。

示例代码

数组实现示例

$deque = [];
array_unshift($deque, "Front");
array_push($deque, "End");
$front = array_shift($deque);
$end = array_pop($deque);

SplDoublyLinkedList 示例

$deque = new SplDoublyLinkedList();
$deque->unshift("Front");
$deque->push("End");
$front = $deque->shift();
$end = $deque->pop();

注意事项

• 数组实现的 array_shift 会重置数字键名，可能导致意外行为。
• SplDoublyLinkedList 需要 PHP 5.3+ 版本支持。
• 若需线程安全，需自行实现锁机制。