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中文網其他相關文章！