Heim  >  Artikel  >  Backend-Entwicklung  >  PHP implementiert Stack-Push- und Pop-Sequenzen

PHP implementiert Stack-Push- und Pop-Sequenzen

不言
不言Original
2018-05-08 09:25:071442Durchsuche

Dieser Artikel stellt hauptsächlich die Push- und Popup-Sequenz des PHP-Implementierungsstapels vor. Jetzt kann ich ihn mit Ihnen teilen.

Problembeschreibung >
Geben Sie zwei ganzzahlige Sequenzen ein. Die erste Sequenz stellt die Push-Sequenz des Stapels dar. Bitte bestimmen Sie, ob die zweite Sequenz die Pop-Sequenz des Stapels ist. Gehen Sie davon aus, dass nicht alle auf den Stapel gelegten Zahlen gleich sind. Beispielsweise ist die Sequenz

die Push-Sequenz eines bestimmten Stapels, und die Sequenz 1,2,3,4,5 ist eine Pop-Sequenz, die der Push-Sequenz entspricht, aber 4,5,3,2,1 kann nicht die Pop-Sequenz der Push-Sequenz sein. (Hinweis: Die Längen dieser beiden Sequenzen sind gleich) 4,3,5,1,2Zeitlimit: 1 Sekunde Platzlimit: 32768K


  • Ideen zur Problemlösung

    • Übergeben Sie die Push-Sequenz und die Pop-Sequenz. Wir verwenden einen Stapel als Hilfsstapel und schieben die Push-Sequenz während des Durchlaufens in den Hilfsstapel oberstes Element des Stapels. Wenn es dem aktuell entfernten Element entspricht, wird das Hilfsstapelelement entfernt. Wenn der Hilfsstapel nach dem Durchlaufen leer ist, bedeutet dies, dass die zweite Sequenz die Popup-Sequenz des Stapels ist

  • Der Code lautet wie folgt

  • <?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]));

  • Erklärung der Beispiele


    • Die Push-Sequenz ist

      und die Pop-Sequenz ist 1,2,3,4,54,5,3,2,1

    • wird zum ersten Mal durchlaufen. Es ist offensichtlich, dass

      nicht gleich 1 ist Das Stapelelement ist 4 und das oberste Element des Stapels ist 1,2,3,4, 4

    • Öffnen Sie das oberste Element des Hilfsstapels und ändern Sie das einzufügende Element in

      5

    • Zu diesem Zeitpunkt ist das Element im Hilfsstapel der

      -Stapel. Das oberste Element ist 1,2,3. Offensichtlich ist 3 nicht gleich dem zu entfernenden Element aus dem Stapel 3. Wir bewegen uns weiter und schieben 5 in den Hilfsstapel 5, der gerade herausspringt ist das gleiche wie das oberste Element des Stapels. Wenn das Element herausspringt, wird es zu

    • 5, bevor wir fortfahren Element des Stapels ist jetzt 3 Dasselbe wie das zu entfernende Element, das oberste Element des Stapels wird entfernt

    • Zu diesem Zeitpunkt wird das oberste Element des Stapels 3, und das zu entfernende Element wird zu

      , und das oberste Element des Stapels wird weiterhin entfernt. Element
    • 2Zu diesem Zeitpunkt wird das oberste Element des Stapels zu 2, das zu entfernende Element wird zu

      und das oberste Element des Stapels wird entfernt
    • 1 Da der Hilfsstapel zu diesem Zeitpunkt leer ist, springen Sie aus while1

    • Da alle zu diesem Zeitpunkt in den Stapel geschobenen Elemente in den Hilfsstapel gelangt sind, springen Sie heraus für

    • Der Hilfsstapel ist schließlich leer, Programm endet

    • Verwandte Empfehlungen:

    • ThinkPHP implementiert die Funktion zum Hochladen von Anhängen

Das obige ist der detaillierte Inhalt vonPHP implementiert Stack-Push- und Pop-Sequenzen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn