PHP 队列和堆栈的数据结构实现详解

队列遵循“先进先出”原则，可使用数组或链表实现；堆栈遵循“后进先出”原则，同样可使用数组或链表实现。具体实现方式包括：队列数组实现、队列链表实现、堆栈数组实现、堆栈链表实现。实战案例演示了队列和堆栈在消息打印和数组逆序中的应用。

PHP 队列和堆栈的数据结构实现详解

队列和堆栈是一种常见的线性数据结构。它们拥有独特的特性，并在各种应用中广泛使用。本文将介绍 PHP 中队列和堆栈的数据结构实现，并提供实战案例。

队列

队列遵循“先进先出”（FIFO）原则。队列中最早插入的元素将首先被移除。可以使用数组或链表来实现队列。

数组实现：

class Queue
{
    private $queue = [];

    public function enqueue($item)
    {
        $this->queue[] = $item;
    }

    public function dequeue()
    {
        if (empty($this->queue)) {
            throw new Exception("Queue is empty");
        }
        return array_shift($this->queue);
    }
}

链表实现：

class Node
{
    public $data;
    public $next;

    public function __construct($data)
    {
        $this->data = $data;
        $this->next = null;
    }
}

class Queue
{
    private $head;
    private $tail;

    public function enqueue($item)
    {
        $node = new Node($item);
        if (empty($this->head)) {
            $this->head = $node;
            $this->tail = $node;
        } else {
            $this->tail->next = $node;
            $this->tail = $node;
        }
    }

    public function dequeue()
    {
        if (empty($this->head)) {
            throw new Exception("Queue is empty");
        }
        $item = $this->head->data;
        $this->head = $this->head->next;
        if (empty($this->head)) {
            $this->tail = null;
        }
        return $item;
    }
}

实战案例： 使用队列打印消息

$queue = new Queue();
$queue->enqueue("Hello");
$queue->enqueue("World");
while (!$queue->isEmpty()) {
    echo $queue->dequeue() . "<br>";
}

堆栈

堆栈遵循“后进先出”（LIFO）原则。堆栈中最后插入的元素将首先被移除。可以使用数组或链表来实现堆栈。

数组实现：

class Stack
{
    private $stack = [];

    public function push($item)
    {
        $this->stack[] = $item;
    }

    public function pop()
    {
        if (empty($this->stack)) {
            throw new Exception("Stack is empty");
        }
        return array_pop($this->stack);
    }
}

链表实现：

class Node
{
    public $data;
    public $next;

    public function __construct($data)
    {
        $this->data = $data;
        $this->next = null;
    }
}

class Stack
{
    private $top;

    public function push($item)
    {
        $node = new Node($item);
        $node->next = $this->top;
        $this->top = $node;
    }

    public function pop()
    {
        if (empty($this->top)) {
            throw new Exception("Stack is empty");
        }
        $item = $this->top->data;
        $this->top = $this->top->next;
        return $item;
    }
}

实战案例： 使用堆栈逆序一个数组

$stack = new Stack();
$array = [1, 2, 3, 4, 5];
foreach ($array as $item) {
    $stack->push($item);
}
$reversedArray = [];
while (!$stack->isEmpty()) {
    $reversedArray[] = $stack->pop();
}
print_r($reversedArray);

以上是PHP 队列和堆栈的数据结构实现详解的详细内容。更多信息请关注PHP中文网其他相关文章！