php实现一个双向队列

实现双向队列的基本思路

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

使用数组实现双向队列

PHP数组本身支持灵活的操作，可以模拟双向队列的行为。以下是基于数组的实现示例：

class ArrayDeque {
    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（Standard PHP Library）提供了SplDoublyLinkedList类，它原生支持双向队列操作：

class SplDeque {
    private $deque;

    public function __construct() {
        $this->deque = new SplDoublyLinkedList();
    }

    public function addFront($item) {
        $this->deque->unshift($item);
    }

    public function addRear($item) {
        $this->deque->push($item);
    }

    public function removeFront() {
        if ($this->deque->isEmpty()) {
            return null;
        }
        return $this->deque->shift();
    }

    public function removeRear() {
        if ($this->deque->isEmpty()) {
            return null;
        }
        return $this->deque->pop();
    }

    public function isEmpty() {
        return $this->deque->isEmpty();
    }

    public function size() {
        return $this->deque->count();
    }
}

性能比较

数组实现的优势在于语法简单，适合小型队列。但对于大型数据集，SplDoublyLinkedList的性能更好，因为它是专门为这类操作优化的数据结构。

数组的array_shift操作时间复杂度为O(n)，因为它需要重新索引数组。而SplDoublyLinkedList的shift和unshift操作都是O(1)时间复杂度。

使用示例

$deque = new SplDeque();
$deque->addFront(1);
$deque->addRear(2);
echo $deque->removeFront(); // 输出1
echo $deque->removeRear();  // 输出2

注意事项

实现时应考虑边界条件，如空队列时的操作。所有删除方法都应检查队列是否为空，避免错误。

对于线程安全的应用场景，需要考虑额外的同步机制。PHP默认是单线程运行，但在多进程环境下共享队列时需要注意。