Pythonでスタックのプッシュ・ポップシーケンスが有効かどうかを判定するプログラム

問題の概要

数値のリスト「pushes」と、別の数値リスト「pops」が与えられたとき、これがスタックに対するプッシュ(push)とポップ(pop)操作の正当なシーケンスであるかどうかを判定する必要があります。

たとえば、入力が pushes = [1, 2, 5, 7, 9]、pops = [2, 1, 9, 7, 5] の場合、出力は True になります。これは、最初に [1, 2] をプッシュしてから両方をポップし、続いて [5, 7, 9] をプッシュしてすべてをポップできるためです。

解法のアプローチ

この問題は、実際にスタックをシミュレートすることで解決できます。以下の手順に従います。

• s := 新しいスタックを作成する
• i := 0(ポップシーケンスのインデックス)
• pushes の各要素 ele について:
  • ele をスタック s にプッシュする
  • スタック s が空でなく、かつ pops[i] が s のトップ要素と一致する間、次を繰り返す:
    • スタック s からトップ要素を削除する
    • i := i + 1
• 最後に、s のサイズが 0 であれば true を返し、そうでなければ false を返す

実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution:
   def solve(self, pushes, pops):
      s = []
      i = 0

      for ele in pushes:
         s.append(ele)

         while len(s) > 0 and pops[i] == s[-1]:
            s.pop()
            i += 1

      return len(s) == 0

ob = Solution()
pushes = [1, 2, 5, 7, 9]
pops = [2, 1, 9, 7, 5]
print(ob.solve(pushes, pops))

入力

[1, 2, 5, 7, 9], [2, 1, 9, 7, 5]

出力

True

アルゴリズムのポイント

このアプローチのポイントは、各要素をプッシュした直後にポップできるだけポップすることです。これにより、pops シーケンスの順序どおりに要素を取り出せるかを常に検証できます。時間計算量は O(n)、空間計算量も O(n) であり、n はプッシュされる要素の総数です。すべてのプッシュ処理が終わった後にスタックが空になっていれば、与えられたシーケンスは有効であると判断できます。