ホームページ > 記事 > バックエンド開発 > PHP はスタックプッシュおよびポップシーケンスを実装します

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

不言オリジナル: 2018-05-08 09:25:071433ブラウズ

この記事では主に 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

5

1、2、3

3

5

3

2

1

1 code> になり、スタックの最上位要素をポップします 🎜🎜🎜🎜 この時点では補助スタックが空であるため、ジャンプしますそのうち🎜🎜🎜🎜 なぜなら、この時点でスタックにプッシュされたすべての要素が補助スタックから飛び出すためです🎜🎜🎜🎜 補助スタックは最終的に空になり、プログラムは終了します🎜 🎜🎜🎜関連する推奨事項: 🎜🎜🎜 ThinkPHP に添付ファイルアップロード機能が実装されました🎜🎜🎜

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

声明：

この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

前の記事：PHPフィルター（フィルター）の関連知識次の記事：PHPフィルター（フィルター）の関連知識

続きを見る

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

関連記事

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