C++でスタックのpush/popシーケンスを検証する方法

ここでは、2つの整数列 pushed と popped（すべての値は重複なし）が与えられたとき、popped が「初期状態で空のスタック」に対する一連の push・pop 操作の結果として実現可能かどうかを判定する問題を扱います。

例として、pushed = [1,2,3,4,5]、popped = [4,5,3,2,1] の場合、答えは true になります。実際、次のような操作列で再現できます。

• push(1), push(2), push(3), push(4)
• pop() → 4 を取り出し
• push(5)
• pop() → 5、pop() → 3、pop() → 2、pop() → 1 を順に取り出し

解法のアプローチ：スタックを用いたシミュレーション

最も直感的な方法は、実際にスタックを操作しながら popped の順序と一致するかを確認することです。手順は以下の通りです。

1. solve(pushed, popped) というメソッドを作成します。
2. 空のスタック st を用意し、popped 配列を参照するためのインデックス index = 0 を初期化します。
3. pushed の各要素について、順番にスタックへ push します。
4. push のたびに、スタックのトップが popped[index] と一致しているかを確認します。一致する限り、pop を繰り返して index を進めます。
5. すべての要素を push し終えた後も、トップが popped[index] と一致していれば pop を続けます。一致しなくなった時点でループを抜けます。
6. 最終的にスタックが空になっていれば true、そうでなければ false を返します。これは「popped の要素をすべて正しい順序で取り出せたか」を意味します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool solve(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int currentIndexOfPopped = 0;

        // pushed の要素を順にスタックへ積む
        for (int i = 0; i < pushed.size(); i++) {
            st.push(pushed[i]);

            // トップが popped の現在の要素と一致する間、pop を続ける
            while (!st.empty() && popped[currentIndexOfPopped] == st.top()) {
                currentIndexOfPopped++;
                st.pop();
            }
        }

        return st.empty();
    }

    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        Solution s;
        return s.solve(pushed, popped);
    }
};

int main() {
    vector<int> v  = {1, 2, 3, 4, 5};
    vector<int> v1 = {4, 5, 3, 2, 1};
    Solution ob;
    cout << ob.validateStackSequences(v, v1);
}

入力

[1,2,3,4,5]
[4,5,3,2,1]

出力

1

出力が 1（true）となるため、[4,5,3,2,1] は有効な pop シーケンスであることが確認できました。

計算量の目安

• 時間計算量： O(n)。各要素は高々1回 push され、高々1回 pop されるためです。
• 空間計算量： O(n)。シミュレーションに使用する補助スタックが最大 n 要素まで増える可能性があるためです。

このように、与えられた操作列をそのまま忠実にシミュレートするだけで、貪欲法のような複雑な工夫を必要とせずに問題を線形時間で解くことができます。スタックの基本的な性質（LIFO：後入れ先出し）を理解していれば、非常にシンプルに実装できる典型問題です。