php实现双向队列

PHP 实现双向队列

在 PHP 中，双向队列（Deque）可以通过数组或 SplDoublyLinkedList 类实现。以下是两种常见的实现方式：

使用数组实现双向队列

数组在 PHP 中灵活性较高，可以通过数组函数模拟双向队列的操作。

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() {
        return array_shift($this->queue);
    }

    // 从队尾移除元素
    public function removeRear() {
        return array_pop($this->queue);
    }

    // 检查队列是否为空
    public function isEmpty() {
        return empty($this->queue);
    }

    // 返回队列大小
    public function size() {
        return count($this->queue);
    }
}

使用 SplDoublyLinkedList 实现双向队列

PHP 的 SPL（标准 PHP 库）提供了 SplDoublyLinkedList 类，可以直接用于实现双向队列。

$deque = new SplDoublyLinkedList();

// 从队首插入元素
$deque->unshift('Item1');

// 从队尾插入元素
$deque->push('Item2');

// 从队首移除元素
$frontItem = $deque->shift();

// 从队尾移除元素
$rearItem = $deque->pop();

// 检查队列是否为空
$isEmpty = $deque->isEmpty();

// 返回队列大小
$size = $deque->count();

注意事项

• 数组实现的简单直接，但频繁的插入和删除操作可能影响性能。
• SplDoublyLinkedList 是专门为双向操作优化的数据结构，适合需要高性能的场景。
• 双向队列的操作时间复杂度通常为 O(1)，但具体实现可能略有差异。