php实现一个双向队列
PHP 实现双向队列
双向队列（Deque）是一种允许在队列两端进行插入和删除操作的线性数据结构。PHP 可以通过数组或 SplDoublyLinkedList 类实现双向队列。
使用数组实现双向队列
数组是 PHP 中最基础的数据结构，可以通过 array_push、array_pop、array_shift 和 array_unshift 实现双向队列的基本操作。
class Deque {
private $queue = [];
// 从队首插入元素
public function addFront($item) {
array_unshift($this->queue, $item);
}
// 从队尾插入元素
public function addRear($item) {
array_push($this->queue, $item);
}
// 从队首删除元素
public function removeFront() {
if ($this->isEmpty()) {
return null;
}
return array_shift($this->queue);
}
// 从队尾删除元素
public function removeRear() {
if ($this->isEmpty()) {
return null;
}
return array_pop($this->queue);
}
// 检查队列是否为空
public function isEmpty() {
return empty($this->queue);
}
// 获取队列大小
public function size() {
return count($this->queue);
}
}使用 SplDoublyLinkedList 实现双向队列
PHP 的 SPL（标准 PHP 库）提供了 SplDoublyLinkedList 类，可以高效地实现双向队列。
class Deque {
private $list;
public function __construct() {
$this->list = new SplDoublyLinkedList();
}
// 从队首插入元素
public function addFront($item) {
$this->list->unshift($item);
}
// 从队尾插入元素
public function addRear($item) {
$this->list->push($item);
}
// 从队首删除元素
public function removeFront() {
if ($this->isEmpty()) {
return null;
}
return $this->list->shift();
}
// 从队尾删除元素
public function removeRear() {
if ($this->isEmpty()) {
return null;
}
return $this->list->pop();
}
// 检查队列是否为空
public function isEmpty() {
return $this->list->isEmpty();
}
// 获取队列大小
public function size() {
return $this->list->count();
}
}示例用法
$deque = new Deque();
$deque->addFront(1); // 队列: [1]
$deque->addRear(2); // 队列: [1, 2]
$deque->addFront(3); // 队列: [3, 1, 2]
echo $deque->removeFront(); // 输出 3
echo $deque->removeRear(); // 输出 2性能比较
- 数组实现：简单直观，但在队首插入或删除元素时，
array_unshift和array_shift的时间复杂度为 O(n)，因为需要重新索引数组。 SplDoublyLinkedList实现：操作的时间复杂度均为 O(1)，性能更高，适合频繁的双端操作。
如果需要高性能的双向队列，推荐使用 SplDoublyLinkedList。
