与えられたプッシュポップシーケンスがPythonで適切かどうかをチェックするプログラム

プッシュと呼ばれる番号のリストとポップと呼ばれる番号の別のリストがあるとすると、これがスタックプッシュとポップアクションの有効なシーケンスであるかどうかを確認する必要があります。

したがって、入力がpushs =[1、2、5、7、9] pops =[2、1、9、7、5]のようである場合、[1、2]をプッシュできるため、出力はTrueになります。まず、両方をポップします。次に、[5、7、9]を押して、すべてポップします。

これを解決するには、次の手順に従います-

• s：=新しいスタック
• i：=0
• プッシュの各要素について、
  • eleをsにプッシュ
  • s>0および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