Pythonでスタックやキューの操作列が有効かどうかを判定する方法

2値からなるリストを考えます。「1」はスタックまたはキューへのプッシュ(push)操作、「0」はポップ(pop)操作を表します。このとき、与えられた操作の列が実際に実行可能(有効)であるかどうかを判定する必要があります。

例えば、入力が nums = [1,0,1,1,0,1] の場合、操作列は [Push, Pop, Push, Push, Pop, Push] となります。この順序では空のスタックから要素を取り出す(ポップする)場面がないため、出力は True となり、この操作列は有効であると判断できます。

解法のアプローチ

この問題は、カウンターを使ったシンプルなシミュレーションで解けます。手順は以下の通りです。

• push_count を 0 で初期化します
• リスト nums の各要素に対して以下を繰り返します
  • nums[i] が 1(プッシュ)なら、push_count を 1 増やします
  • それ以外(ポップ)なら、push_count を 1 減らします
  • その時点で push_count が 0 未満になった場合は、空のスタックからポップしようとしていることを意味するため、False を返します
• ループが最後まで完了すれば、すべての操作が有効だったことになるので True を返します

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(nums):
    push_count = 0
    for i in range(len(nums)):
        if nums[i]:
            push_count += 1
        else:
            push_count -= 1
        if push_count < 0:
            return False
    return True

nums = [1,0,1,1,0,1]
print(solve(nums))

入力

[1,0,1,1,0,1]

出力

True

計算量の考察

時間計算量は O(n)(n はリストの長さ)、空間計算量は O(1) です。実際にスタックやキューのデータ構造を構築する必要はなく、単一のカウンターだけで判定できる点がこのアルゴリズムの大きな利点です。また、途中でカウンターが負になれば即座に False を返せるため、無駄な処理も発生しません。