当前位置：首页 > article >正文

PHP实现双向队列

article 2024/11/22 5:44:09

在 PHP 中，虽然标准库没有直接提供一个双向队列（Deque）的实现，但我们可以使用 SplDoublyLinkedList 类来实现这一功能。SplDoublyLinkedList 是一个双向链表，它允许我们在列表的头部和尾部进行插入和删除操作，这符合双向队列的基本特性。

下面是一个使用 SplDoublyLinkedList 实现双向队列的示例代码：

<?php

class Deque {
    private $deque;

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

    // 在队列尾部添加元素
    public function enqueue($value) {
        $this->deque->push($value);
    }

    // 在队列头部添加元素（也可以看作是在队列的另一端添加）
    public function enqueueFront($value) {
        $this->deque->unshift($value);
    }

    // 从队列尾部移除元素
    public function dequeue() {
        if ($this->isEmpty()) {
            throw new UnderflowException("Deque is empty, cannot dequeue.");
        }
        return $this->deque->pop();
    }

    // 从队列头部移除元素（也可以看作是在队列的另一端移除）
    public function dequeueFront() {
        if ($this->isEmpty()) {
            throw new UnderflowException("Deque is empty, cannot dequeue from front.");
        }
        return $this->deque->shift();
    }

    // 获取队列头部的元素（不移除）
    public function peek() {
        if ($this->isEmpty()) {
            throw new UnderflowException("Deque is empty, cannot peek.");
        }
        return $this->deque->bottom();
    }

    // 获取队列尾部的元素（不移除）
    public function peekEnd() {
        if ($this->isEmpty()) {
            throw new UnderflowException("Deque is empty, cannot peek at end.");
        }
        return $this->deque->top();
    }

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

    // 获取队列中的元素数量
    public function count() {
        return $this->deque->count();
    }

    // 打印队列中的元素（用于调试）
    public function printDeque() {
        echo implode(' <-> ', $this->deque->toArray()) . "\n";
    }
}

// 示例用法
$deque = new Deque();
$deque->enqueue(1);
$deque->enqueue(2);
$deque->enqueueFront(0);
$deque->printDeque(); // 输出: 0 <-> 1 <-> 2
echo "Peek: " . $deque->peek() . "\n"; // 输出: Peek: 1
echo "Dequeue: " . $deque->dequeue() . "\n"; // 输出: Dequeue: 1
$deque->printDeque(); // 输出: 0 <-> 2
echo "Peek end: " . $deque->peekEnd() . "\n"; // 输出: Peek end: 2
echo "Dequeue front: " . $deque->dequeueFront() . "\n"; // 输出: Dequeue front: 0
$deque->printDeque(); // 输出: 2
?>

在这个示例中，Deque 类封装了一个 SplDoublyLinkedList 实例，并提供了标准的双向队列操作，如 enqueue（在尾部添加）、enqueueFront（在头部添加）、dequeue（从尾部移除）、dequeueFront（从头部移除）、peek（查看头部元素）、peekEnd（查看尾部元素）、isEmpty（检查是否为空）和 count（获取元素数量）。此外，还有一个 printDeque 方法用于打印队列中的元素，便于调试。