JavaScriptでスタックのプッシュ・ポップ操作シーケンスを検証する方法

問題

2つの配列 pushed と popped を第1引数と第2引数として受け取るJavaScript関数を作成します。どちらの配列にも、重複しない一意な要素のみが含まれることが保証されています。

この関数は、最初に空のスタックに対して一連のpush(プッシュ)とpop(ポップ)操作を実行した結果として、この2つの配列が実現可能である場合に限り true を返し、そうでなければ false を返す必要があります。

例えば、関数への入力が以下の場合を考えてみましょう。

const pushed = [1, 2, 3, 4, 5];
const popped = [4, 5, 3, 2, 1];

このとき、期待される出力は次のとおりです。

const output = true;

出力の解説

この出力が true になるのは、以下のような操作シーケンスが存在するからです。

push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

つまり、pushed の要素を順番にスタックへ積みながら、適切なタイミングでpopすることで、popped の順序通りに要素を取り出せるためです。

アプローチ

この問題は、シミュレーションによって効率的に解くことができます。

• pushed の要素を先頭から順にスタックへプッシュしていきます。
• 各ステップで、スタックの先頭(トップ)にある要素が popped の現在の要素と一致していれば、その都度ポップします。
• すべてのプッシュが完了した後もスタックに残っている要素は、popped の残りの要素と順番に一致するかどうかを確認します。1つでも不一致があれば、そのシーケンスは無効です。

時間計算量はO(n)、空間計算量もO(n)であり、非常に効率的です。

コード例

上記のアプローチを実装すると、コードは次のようになります。

const pushed = [1, 2, 3, 4, 5];
const popped = [4, 5, 3, 2, 1];

const validateSequence = (pushed = [], popped = []) => {
    let pushedIndex = 0;
    let poppedIndex = 0;
    const stack = [];

    // pushed の要素を順にスタックへプッシュし、
    // スタックのトップが popped の現在の要素と一致すればポップ
    while (pushedIndex < pushed.length) {
        if (stack[stack.length - 1] !== popped[poppedIndex]) {
            stack.push(pushed[pushedIndex++]);
        } else {
            stack.pop();
            poppedIndex += 1;
        }
    }

    // 残ったスタックの中身が popped の順序と一致するか確認
    while (stack.length) {
        if (stack.pop() !== popped[poppedIndex++]) {
            return false;
        }
    }

    return true;
};

console.log(validateSequence(pushed, popped));

出力

コンソールに出力される結果は以下のとおりです。

true

このように、スタックを使ったシミュレーションを行うことで、与えられたプッシュ・ポップのシーケンスが実際に実現可能なものかどうかを簡単に検証できます。