PHP implémente des séquences stack push et pop

Cet article présente principalement la séquence push et pop-up de la pile d'implémentation PHP. Il a une certaine valeur de référence. Maintenant, je le partage avec vous. Les amis dans le besoin peuvent s'y référer

Description du problème

est la séquence push d'une certaine pile, et la séquence 1，2，3，4，5 est une séquence pop correspondant à la séquence push, mais 4，5，3，2，1 ne peut pas être la séquence pop de la séquence push. (Remarque : les longueurs de ces deux séquences sont égales) 4，3，5，1，2Durée limite : 1 seconde Limite d'espace : 32768K

• Idées de résolution de problèmes

• Passons la séquence push et la séquence pop. Nous utilisons une pile comme pile auxiliaire et poussons la séquence push dans la pile auxiliaire pendant le parcours si la pile auxiliaire n'est pas vide pendant le parcours, et le. élément supérieur de la pile S'il est égal à l'élément actuellement sauté, l'élément auxiliaire de la pile sera sauté. Si la pile auxiliaire est vide après le parcours, cela signifie que la deuxième séquence est la séquence pop-up de la pile

• Le code est le suivant

<?php

function isPopOrder($pushValue, $popValue){    
$stack = new SplStack;    
$count = count($pushValue);

    for ($i = 0, $j = 0; $i < $count; $i++) {        
    $stack->push($pushValue[$i]);

        while (!$stack->isEmpty() && $stack->top() == $popValue[$j] && $j < $count) {            
        $stack->pop();            
        $j++;
        }
    }
    return $stack->isEmpty();
}

var_dump(isPopOrder([1, 2, 3, 4, 5], [4, 5, 3, 2, 1]));

• Explication des exemples

  
  

• La séquence push est

  et le pop la séquence est 1，2，3，4，54，5，3，2，1

• Pour le premier parcours, il est évident que

  n'est pas égal à 1 Continuez le parcours et traversez 4 fois jusqu'à la station de pile auxiliaire. Lorsque l'élément de la pile est 4 et que l'élément supérieur de la pile est 1，2，3，44

• Faites apparaître l'élément supérieur de la pile auxiliaire et modifiez l'élément à placer dans

  5

• À ce stade, l'élément dans la pile auxiliaire est

  L'élément supérieur de la pile est 1，2，3 Évidemment, 3 n'est pas égal à l'élément à faire apparaître. 3. Nous continuons à parcourir et à pousser 5 dans la pile auxiliaire 5

• à ce moment-là. L'élément à faire apparaître est

  qui est le même que l'élément supérieur de la pile, nous faisons donc apparaître l'élément supérieur de la pile et l'élément à faire apparaître devient 53

• avant de continuer. L'élément supérieur de la pile est maintenant C'est

  . et est le même que l'élément à faire apparaître. L'élément supérieur de la pile est sauté 3

• À ce moment, l'élément supérieur de la pile devient

  , et l'élément. à faire apparaître devient 2, et continue d'apparaître. L'élément supérieur de la pile 2

• À ce moment, l'élément supérieur de la pile se transforme en

  , l'élément en être extrait de la pile devient 1, et l'élément supérieur de la pile est extrait 1

• Puisque la pile auxiliaire est vide à ce moment, sautez de while

• Puisque tous les éléments poussés dans la pile à ce moment sont entrés dans la pile auxiliaire, sautez hors de la pile auxiliaire pour

• Enfin, elle est vide et la le programme se termine

Recommandations associées :

ThinkPHP implémente la fonction de téléchargement de pièces jointes

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!