在python中编写一个检查给定推入弹出序列是否正确的程序

在python中编写一个检查给定推入弹出序列是否正确的程序

假设我们有一个名为pushes的数字列表,另一个名为pops的数字列表,我们必须检查这是否是一个有效的堆栈推入和弹出操作序列。

因此,如果输入为pushes = [1, 2, 5, 7, 9] pops = [2, 1, 9, 7, 5],那么输出将为True,因为我们可以先推[1, 2],然后将它们弹出。然后推[5、7、9]并将它们全部弹出。

为解决这个问题,我们将按照以下步骤操作:

  • s:一个新栈
  • i:0
  • 对于每个ele中的元素进行操作,执行以下操作
    • 将ele推入s
    • 当s的大小> 0且pops[i]等于s的顶部元素时,执行以下操作:
      • 从s中删除顶部元素
      • i := i + 1
  • 当s的大小与0相同时,返回true,否则返回false

稍后将呈现以下内容,以更好地理解实现方式。

更多Python相关文章,请阅读:Python 教程

例子

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程