PHP はスタック プッシュおよびポップ シーケンスを実装します

この記事では主に PHP 実装スタックのプッシュ シーケンスとポップアップ シーケンスを紹介します。必要な友達はそれを参照できるようにします。

最初に 2 つの整数シーケンスを入力します。各シーケンスはスタックのプッシュ シーケンスを表します。2 番目のシーケンスがスタックのポップ シーケンスであるかどうかを判断してください。スタックにプッシュされたすべての数値が等しくないと仮定します。たとえば、シーケンス 1, 2, 3, 4, 5 は特定のスタックのプッシュ シーケンスであり、シーケンス 4, 5, 3, 2, 1 は次のようになります。スタックに対応するプッシュ シーケンス。ポップ シーケンスですが、4, 3, 5, 1, 2 をプッシュ シーケンスのポップ シーケンスにすることはできません。 (注: これら 2 つのシーケンスの長さは等しい)
制限時間: 1 秒 スペース制限: 32768K

1，2，3，4，5是某栈的压入顺序，序列4，5，3，2，1是该压栈序列对应的一个弹出序列，但4，3，5，1，2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
时间限制：1秒    空间限制：32768K

---

• 解题思路

• 传入入栈序列，和出栈序列，我们使用一个栈作为辅助栈，遍历将入栈序列压入辅助栈，如果遍历时辅助栈不为空，且栈顶元素等于当前出栈元素 ，则弹出辅助栈元素。遍历结束后如果辅助栈为空则说明第二个序列是该栈的弹出顺序

• 代码如下

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

ログイン後にコピー

---

• 实例解说
  

• 进栈序列为 1，2，3，4，5 出栈序列为  4，5，3，2，1

• 第一次遍历，明显 1 不等于 4 继续遍历，遍历 4 次到辅助栈站的栈内元素为1，2，3，4   栈顶元素为4 时

• 把辅助栈栈顶元素弹出，将待出栈元素变为5

• 这时辅助栈的栈内元素为1，2，3 栈顶元素为3，很明显3不等于待出栈元素5 ，我们继续遍历把 5 压入辅助栈

• 正好这时待出栈元素为5 与栈顶元素相同，于是我们弹出栈顶元素，待出栈元素变为3

• 再继续，栈顶元素此时为3 与待出栈元素相同，弹出栈顶元素

• 此时栈顶元素变为2，待出栈元素变为2，继续弹出栈顶元素

• 此时栈顶元素变为1，待出栈元素变为1問題解決のアイデア

• プッシュ シーケンスとポップ シーケンスを渡します。プッシュ シーケンスをトラバースするための補助スタックとしてスタックを使用します。補助スタック。走査中に補助スタックが空ではなく、スタックの最上位要素が現在のポップされた要素と等しい場合、補助スタック要素はポップされます。走査後に補助スタックが空の場合、2 番目のシーケンスがスタックのポップアップ シーケンスであることを意味します

• コードは次のとおりです

• rrreee

  ---
例の説明


スタッキングシーケンスは 1、 2, 3, 4, 5 ポップ シーケンスは 4, 5, 3, 2, 1 です

最初のトラバーサル、明らかに 1 はそうではありません4 に等しい スタックの最上位要素が 1、2、3、4 のとき、補助スタックまで 4 回トラバースします。 4, 🎜🎜🎜🎜 補助スタックを置く スタックの先頭要素がポップされ、ポップされる要素は 5 になります🎜🎜🎜🎜 このとき、補助スタックの要素は 1、2、3 で、スタックの最上位要素は 3 です。明らかに 3 は、要素がスタック 5 からポップされる場合、引き続きトラバースして 5 を補助スタックにプッシュします🎜 🎜🎜🎜この時点で、ポップされる要素は 5 はスタックの先頭要素と同じなので、スタックの先頭要素をポップすると、ポップされる要素は 3 になります🎜🎜🎜🎜 続き、スタックの最上位要素はポップされる要素と同じ 3 になりました 🎜🎜🎜🎜このとき、スタックの最上位要素はポップされます。スタックは 2 となり、スタック要素は 2 となり、スタックの先頭要素がポップされ続けます。スタックは 1 になり、ポップされる要素は 1 code> になり、スタックの最上位要素をポップします 🎜🎜🎜🎜 この時点では補​​助スタックが空であるため、ジャンプしますそのうち🎜🎜🎜🎜 なぜなら、この時点でスタックにプッシュされたすべての要素が補助スタックから飛び出すためです🎜🎜🎜🎜 補助スタックは最終的に空になり、プログラムは終了します🎜 🎜🎜🎜関連する推奨事項: 🎜🎜🎜 ThinkPHP に添付ファイルアップロード機能が実装されました🎜🎜🎜

以上がPHP はスタック プッシュおよびポップ シーケンスを実装しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。