Explication détaillée de la pile en php

Pour la structure logique, on part également de la plus simple. Pile et file d’attente sont des mots familiers à la plupart des gens, mais tas et pile sont en réalité deux choses différentes. Ne soyez pas dérouté par l'intervieweur pendant l'entretien. Le tas est une structure arborescente ou une structure arborescente binaire complète. Aujourd’hui, nous parlons principalement de l’application de cette stack.

Qu'est-ce qu'une pile ?

La pile est généralement une structure de données séquentielle. Sa plus grande caractéristique est le dernier entré, premier sorti (LIFO) ou, à l'inverse, le premier entré, dernier sorti (FILO). Que signifient ces deux phrases ? L’exemple le plus typique est quelque chose que tout le monde verra certainement en regardant des séries télévisées, en particulier des films sur les fusillades : les magazines.

Lors du chargement du chargeur, les balles sont pressées dans le chargeur une par une. En d'autres termes, la première balle est enfoncée en bas, et lors du tir, les balles sont enfoncées dans l'ordre inverse. est éjectée, et la première balle introduite est la dernière à être tirée.

Cet exemple est en fait très frappant, unifions la terminologie. Appuyer sur la balle dans le chargeur s'appelle "empilage", la première balle est en bas, cette position est appelée "bas de la pile", la dernière balle est en haut, cette position est appelée "haut de la pile", la balle tiré C'est la balle qui se trouve au "haut de la pile". Cette opération est appelée "popping".

Grâce aux définitions des termes ci-dessus, nous pouvons voir que les opérations logiques de la pile sont principalement "dans la pile" et "hors de la pile", et la chose la plus importante à prendre en compte dans la structure logique est le " haut de la pile" et "bas de la pile". L'état lors de l'éclatement et de l'éclatement de la pile. Bien sûr, il n'y a aucun problème à utiliser la structure d'ordre ou de chaîne de la structure logique de la pile. Examinons-les un par un.

Pile séquentielle

Tout d'abord, il s'agit d'une implémentation relativement simple de la pile séquentielle. Puisqu’il s’agit d’une structure séquentielle, un tableau est utilisé. Cependant, nous devons également enregistrer la situation « haut de la pile » ou « bas de la pile », nous encapsulons donc le tableau de la pile séquentielle dans une classe.

En même temps, définissez un attribut dans cette classe pour indiquer le pointeur "haut" ou "bas" de la pile actuelle, qui est en fait la position en indice du "haut" ou "bas" actuel dans le tableau. D'une manière générale, il suffit d'enregistrer la position du "haut de la pile" et de définir le "bas de la pile" sur -1 par défaut. Étant donné que l'indice du tableau lui-même commence à 0, lorsque l'attribut "haut de la pile" est -1, la pile est une pile vide, car son "haut" et son "bas" sont ensemble et ne contiennent aucun élément.

class SqStack
{
    public $data;
    public $top;
}

L'initialisation de la pile séquentielle est simple, avec un tableau vide et en définissant $top sur -1 .

function InitSqStack()
{
    $stack = new SqStack();
    $stack->data = [];
    $stack->top = -1;
    return $stack;
}

La prochaine étape concerne les opérations "push" et "pop". Regardons d'abord le code.

function PushSqStack(SqStack &$stack, $x){
    $stack->top ++;
    $stack->data[$stack->top] = $x;
}

function PopSqStack(SqStack &$stack){
    // 栈空
    if($stack->top == -1){
        return false;
    }

    $v = $stack->data[$stack->top];
    $stack->top--;
    return $v;
}

Pousser sur la pile est très simple, il suffit d'ajouter du contenu aux éléments du tableau, puis de $top++. Cependant, s'il s'agit d'un langage C, car il a une limite de longueur de tableau, lors de la poussée sur la pile, nous devons également déterminer si la pile est pleine. Bien entendu, en PHP nous n’avons pas ce souci.

Icône de poussée de pile séquentielle

Lorsque vous ouvrez la pile, vous devez déterminer si la pile actuelle est vide. Cela ne fait pas de distinction entre les langues, car si elle est inférieure à -1, l'utilisation de cette pile à nouveau entraînera quelque chose. faux. Lorsque vous faites éclater la pile, si la pile est déjà vide, ne donnez pas $top--, récupérez simplement l'élément supérieur de la pile et renvoyez-le.

Icône d'éclatement de la pile séquentielle

Jetons un coup d'œil aux résultats des tests de cette pile séquentielle.

$stack = InitSqStack();

PushSqStack($stack, 'a');
PushSqStack($stack, 'b');
PushSqStack($stack, 'c');

var_dump($stack);
// object(SqStack)#1 (2) {
//     ["data"]=>
//     array(3) {
//       [0]=>
//       string(1) "a"
//       [1]=>
//       string(1) "b"
//       [2]=>
//       string(1) "c"
//     }
//     ["top"]=>
//     int(2)
//   }

echo PopSqStack($stack), PHP_EOL; // c
echo PopSqStack($stack), PHP_EOL; // b
echo PopSqStack($stack), PHP_EOL; // a

var_dump($stack);
// object(SqStack)#1 (2) {
//     ["data"]=>
//     array(3) {
//       [0]=>
//       string(1) "a"
//       [1]=>
//       string(1) "b"
//       [2]=>
//       string(1) "c"
//     }
//     ["top"]=>
//     int(-1)
//   }

N'est-il pas très simple de faire fonctionner la pile via des tableaux ? Après avoir lu et appris la pile de chaînes, nous parlerons également des fonctions d'opération de pile de tableaux que PHP a préparées pour nous, qui seront plus pratiques à utiliser.

Chain Stack

En fait, pour la structure de stockage en chaîne, le contenu de base est toujours le même. Nous devons également nous soucier du haut de notre pile, et nous devons également nous soucier des opérations dans et hors de la pile. . Cependant, dans la chaîne, nous pouvons utiliser l'insertion de tête, c'est-à-dire conserver les données insérées en haut de la chaîne pour obtenir l'effet « haut de pile ». De cette façon, nous n'avons pas besoin d'un attribut spécial pour enregistrer la première position actuelle de la pile. Il sera plus clair de comprendre directement à travers un schéma.

class LinkStack{
    public $data;
    public $next;
}

La structure des données n'est qu'une structure de chaîne typique. L'essentiel est de voir comment l'opération push est effectuée.

function InitLinkStack(){
    return null;
}

function PushLinkStack(?LinkStack &$stack, $x){
    $s = new LinkStack();
    $s->data = $x;
    $s->next = $stack;
    $stack = $s;
}

function PopLinkStack(?LinkStack &$stack){
    if($stack == NULL){
        return false;
    }
    $v = $stack->data;
    $stack = $stack->next;
    return $v;
}

En fait, l'opération d'initialisation de la pile vide dans la pile de chaîne n'a pas beaucoup de sens. Nous pouvons définir directement une variable nulle et effectuer des opérations en chaîne dessus, mais ici nous restons toujours unifiés avec la pile séquentielle. Tout comme le bas de la pile dans la pile séquentielle est -1, dans la pile chaîne, nous convenons également que le bas de la pile est un nœud d'objet nul.

接下来就是入栈操作了。这里我们使用的是头插法，其实就是将新元素放到链表的顶端。先实例化一个节点，然后将这个节点的 next 指向链表的头节点。接着再让当前这个节点成为链表的新的头节点，就像下图所示的那样。

同理，出栈的操作其实也是类似的，将头节点变成当前头节点的 next 节点，直到当前节点变成 null ，也就是栈已经空了，如图所示：

最后，我们同样的测试一下这一套链式栈的代码运行情况如何。

$stack = InitLinkStack();

PushLinkStack($stack, 'a');
PushLinkStack($stack, 'b');
PushLinkStack($stack, 'c');

var_dump($stack);
// object(LinkStack)#3 (2) {
//     ["data"]=>
//     string(1) "c"
//     ["next"]=>
//     object(LinkStack)#2 (2) {
//       ["data"]=>
//       string(1) "b"
//       ["next"]=>
//       object(LinkStack)#1 (2) {
//         ["data"]=>
//         string(1) "a"
//         ["next"]=>
//         NULL
//       }
//     }
//   }

echo PopLinkStack($stack), PHP_EOL; // c
echo PopLinkStack($stack), PHP_EOL; // b
echo PopLinkStack($stack), PHP_EOL; // a

var_dump($stack);
// NULL

是不是很多小伙伴已经看出之前我们花费了 4 篇文章的时间来讲述线性结构中的顺序表和链表的重要作用了吧。它们真的是一切其它逻辑结构的基础。不光是栈，在队列、树、图中我们都会有不同结构的线性和链式的实现。当然，更重要的是能体会它们之间的区别，在不同的业务场景中，两种不同的存储结构可能真的会带来完全不一样的体验。

PHP 为我们提供的数组栈操作

最后，我们简单的看一下在 PHP 中已经为我们准备好的两个数组操作函数。有了它们，对于顺序栈来说，我们的操作可以简化到非常傻瓜智能的效果。

$sqStackList = [];

array_push($sqStackList, 'a');
array_push($sqStackList, 'b');
array_push($sqStackList, 'c');

print_r($sqStackList);
// Array
// (
//     [0] => a
//     [1] => b
//     [2] => c
// )

array_pop($sqStackList);
print_r($sqStackList);
// Array
// (
//     [0] => a
//     [1] => b
// )

echo count($sqStackList) > 0 ? $sqStackList[count($sqStackList) - 1] : false, PHP_EOL;
// b

array_pop($sqStackList);

echo count($sqStackList) > 0 ? $sqStackList[count($sqStackList) - 1] : false, PHP_EOL;
// c

array_pop($sqStackList);

print_r($sqStackList);
// Array
// (
// )

估计不少同学早就用过这两个函数了。array_push() 就是向数组中压入一个数据，其实说白了，增加一个数据到数组中而已，没什么特别稀罕的功能。而 array_pop() 则是将数组最后一个位置的数据弹出。是不是和我们上面自己实现的那个顺序栈是完全相同的概念。没错，既然语言环境已经为我们准备好了，那么除了在某些场景下需要链式结构的话，大部分情况下我们直接使用这两个函数就可以方便地实现 PHP 中的栈操作了。

总结

栈这个逻辑结构是不是非常的简单清晰呀，在日常应用中其实栈的使用非常广泛。比如算式中的前缀算式、中缀算式、后缀算式的转化，比如我们后面学习树、图时要接触到了BFS（深度搜索），再根据BFS引出递归这个概念。另外，在解析字符时的一些对称匹配、回文算法的判断等等，这些都是栈的典型应用。可以说，栈这个东西撑起了计算机算法的半壁江山。而另外半壁呢？当然就是我们下回要讲的：队列。

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.栈和队列/source/3.1栈的相关逻辑操作.php

推荐学习：php视频教程

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!