PHP中的堆栈和队列简介-DEV365 开发者社区

堆

堆栈是一种数据结构，其中将项目添加和删除，以结束，首先（LIFO）顺序。将元素插入堆栈被称为“推动”操作，删除元素称为“ pop”操作。

简单示例：图像您打开浏览器，然后访问youtube.com，然后访问google.com，最后是gmail.com。

您当前的浏览历史记录看起来像这样（'gmail.com'是您当前打开的网站）：
youtube.com->google.com->gmail.com

在实践中使用堆栈的一个示例是在网络浏览器中单击“返回”按钮时，该按钮可让您在离开它之后返回上一个网页Google.com，而当前的网页gmail.com正在从堆栈的顶部取出。

youtube.com->google.com

如果您再次单击返回，您就回来了。

youtube.com

堆栈中的节点

一个节点是一个基本单元，可存储一块数据并引用列表中的下一个和上一个节点。类似于单链接列表。

class Node
{
    public $value;
    public $next;

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

此节点类有两个字段：
1，存储元素值的数据，
2，下一步，是对列表中的下一个节点的引用

堆栈中的构造函数

让我们创建一个代表堆栈数据结构的类。

此类有两个实例变量：

$top：对列表中的第一个节点的引用，
$height：一个数量计算堆栈中节点数量的整数（这是1个，因为我们在构造函数中创建了一个新节点）。

class Stack
{
    public $top;
    public $height;

    public function __construct(public $value)
    {
        $newNode = new Node($value);
        $this->top = $newNode;
        $this->height = 1;
    }
}

在转到主要操作之前，让我们创建一个辅助方法来打印堆栈中的所有节点。

说明：

在方法printStack()中，我们定义了局部变量$temp，并分配了 $ this-> top的值，这是对列表中的第一个节点的引用。

然后，它进入一个段循环，直到$temp不为空，这意味着没有更多的 next 节点。

呼应值后，该函数分配了$temp $temp->next的值，将$temp移至列表中的下一个节点 ，以继续循环。

public function printStack()
{
    $temp = $this->top;
    while ($temp != null) {
        echo $temp->value."\n";
        $temp = $temp->next;
    }
}

推

当我们将节点“按”堆栈上时，我们将一个新元素添加到堆栈顶部。堆栈遵循LIFO（最后一次）原理，这意味着添加到堆栈中的最后一个元素将是第一个要删除的元素。因此，当您将新节点推入堆栈时，该新节点将是堆栈的新顶级节点。

在图像中从左到右，我们正在添加值。首先，7，然后是最终6。

说明：

我们创建一个新节点。
如果堆栈为空，则将新节点分配为第一个节点，而顶部引用则指向它。
如果堆栈不是空的，则使用下一个引用将新节点连接到当前顶部节点。
顶部引用已更新为新节点。
最后，我们增加了堆栈的计数（高度）。

从上到下，我们正在访问“堆叠”在彼此上的网站。

public function push($value)
{
    $newNode = new Node($value);
    if ($this->height == 0) {
        $this->top = $newNode;
    } else {
        $newNode->next = $this->top;
        $this->top = $newNode;
    }
    $this->height++;
}

// $s = new Stack('youtube.com'); 
// $s->push('google.com');
// $s->push('gmail.com');
// $s->printStack();
// 
// gmail.com
// google.com
// youtube.com

流行音乐

“ pop”是堆栈上的一个操作，该操作可去除堆栈顶部的元素并返回。该操作还将堆栈的顶部引用更新为下一个元素，并减少堆栈的计数（高度）。

记住：要成为堆栈的事物，您只需要从同一端添加和删除即可。

在图像中从左到右，我们正在删除值。首先，6，然后是最终。

说明：

如果堆栈为空，我们返回null。
其他，我们为堆栈的当前顶部分配一个临时变量。
我们将堆栈中下一个元素的最高引用更改为
一旦更改了顶部，我们就可以将上一个顶部（存储在临时变量中）重置为null。
最后，我们减少了堆栈的计数（高度）。

从上到下，当我们单击“返回”按钮时，我们访问了以前的网站，这些网站彼此之间是“堆叠”的。

public function pop()
{
    if ($this->height == 0) {
        return null;
    }
    $temp = $this->top;
    $this->top = $this->top->next;
    $temp->next = null;
    $this->height--;
    return $temp;
}

// $s = new Stack('youtube.com'); 
// $s->push('google.com');
// $s->push('gmail.com');
// $s->pop(); // removes top
// $s->printStack();
// 
// google.com
// youtube.com

在数组中堆叠

在PHP中，诸如Array_push和Array_pop之类的内置函数可用于使用数组数据结构实现堆栈。

$stack = [];
array_push($stack, 'youtube.com');
array_push($stack, 'google.com');
array_push($stack, 'gmail.com');
array_pop($stack);

// $stack = [
//   "youtube.com",
//   "google.com",
// ]

使用array_push和array_pop函数实现阵列推动和弹出操作的时间复杂性，平均为o（1）。

注意： 当您使用array_unshift和array_shift函数实现时，您可以在数组中预处和弹出第一个元素时也可以实现堆栈原理，但是是o（n）在最坏的情况下。

堆栈中的时间复杂性

push：o（1） - 此操作需要持续的时间，因为它仅涉及在堆栈顶部添加一个元素。
POP：O（1） - 此操作也需要持续的时间，因为它仅涉及从堆栈中删除顶部元素。

注意： 这些复杂性用于使用数组或链接列表的堆栈和队列的基本实现。

队列

队列是线性数据结构，其中添加的第一个元素是第一个要删除的元素。该订单被称为首先出局（FIFO）。

队列的一个普遍例子是等待命令的人，首先到达的人将首先提供。队列和堆栈之间的主要区别在于如何去除元素。在堆栈中，最近添加的元素首先被删除，而在队列中，最近添加的元素首先被删除。

完整脚本：
https://gist.github.com/matusstafura/4bd1beeba61f1995b3fcd18a77bf87c6

队列中的节点

我们使用与堆栈相同的定义。

class Node
{
    public $value;
    public $next;

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

队列中的构造函数

让我们创建一个代表队列数据结构的类。

此LinkedList类有三个实例变量：

$first：对列表中的第一个节点的引用，
$last：对列表中的最后一个节点的引用，
$length：一个数量计算列表中节点数量的整数。

class Queue
{
    public $first;
    public $last;
    public $length;

    public function __construct(public $value)
    {
        $newNode = new Node($value);
        $this->first = $newNode;
        $this->last = $newNode;
        $this->length = 1;
    }
}

用于打印我们使用与堆栈中的回声值相同的逻辑。

public function printQueue()
{
    $temp = $this->first;
    while ($temp != null) {
        echo $temp->value."\n";
        $temp = $temp->next;
    }
}

入住

进入Queue意味着将新节点添加到队列（也称为推送，添加或插入操作）。

从上到下，我们正在为队列添加值。

说明：

我们创建一个新节点。
如果队列为空，则将新节点分配为第一个和最后一个节点。
如果队列不是空的，则最后一个节点的下一个引用已连接到新节点。
最后一个引用已更新为新节点。
我们增加了队列的长度。

public function enqueue($value)
{
    $newNode = new Node($value);
    if ($this->length == 0) {
        $this->first = $newNode;
        $this->last = $newNode;
    } else {
        $this->last->next = $newNode;
        $this->last = $newNode;
    }
    $this->length++;
}

// $q = new Queue("first customer");
// $q->enqueue("second customer");
// $q->enqueue("third customer");
// 
// $q->printQueue();
// first customer
// second customer
// third customer

Dequeue

到“ Dequeue”（也称为pop，删除或删除）是指删除队列前部元素的操作。

从上到下，我们将值删除到队列

队列遵循第一个第一（FIFO）排序原则，因此我们需要删除第一个。

说明：

如果队列为空，我们返回null。
如果队列只有一个节点，我们将其第一个也是最后一个引用。
否则，我们将第一个引用分配给下一个节点。
我们通过将其重置为null。
最后，我们降低了队列的长度。

public function dequeue()
{
    if ($this->length == 0) {
        return null;
    }
    $temp = $this->first;
    if ($this->length == 1) {
        $this->first = null;
        $this->last = null;
    } else {
        $this->first = $this->first->next;
        $temp->next = null;
    }
    $this->length--;
    return $temp;
}

// $q = new Queue("first customer");
// $q->enqueue("second customer");
// $q->enqueue("third customer");
// $q->dequeue();
// 
// $q->printQueue();
// second customer
// third customer

阵列中的队列

$stack = [];
array_push($stack, 'youtube.com');
array_push($stack, 'google.com');
array_push($stack, 'gmail.com');
array_shift($queue);

// $stack = [
//   "google.com",
//   "gmail.com",
// ]

在此示例中，array_push函数的时间复杂性为o（1），对于php中的array_shift函数为o（n），其中n是输入数组的大小。

队列中的时间复杂性

在我们的链接列表示例中：

顾问：o（1） - 此操作需要恒定时间，因为它仅涉及在队列的背面添加一个元素。
Dequeue：O（1） - 此操作需要恒定时间，因为它仅涉及从队列中删除前元素。

完整脚本：
https://gist.github.com/matusstafura/e70b13f3cbf38a3efc00b3dcb561bb59

目录

堆

堆栈中的节点

堆栈中的构造函数

推

流行音乐

在数组中堆叠

堆栈中的时间复杂性

队列

队列中的节点

队列中的构造函数

入住

Dequeue

阵列中的队列

队列中的时间复杂性