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

WBOY
发布: 2024-05-07 09:42:01
原创
368 人浏览过

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

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中文网其他相关文章!

相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!