剑指Offer编程题-栈的压入、弹出序列 | 我的个人生活记录

题目：栈的压入、弹出序列

题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

解题思路

pushV、popV分别是压入顺序、弹出顺序，将pushV中的元素按从前往后的顺序与popV中的元素按从后往前的顺序比较，如果两个元素相同，则将popV中这个元素pop掉，如果不相同，则popV不变，将pushV中这个元素push到另一个辅助列表中，然后剩下的继续与popV中元素比较，相当于将pushV中与popV对应不上的元素逆序存储到另一个列表中。当pushV中的元素比较完，如果辅助列表是空的，则说明pushV中所有元素都对应上了，直接返回True，否则将辅助列表与popV剩下的元素比较，一旦出现不相等的元素就返回False。

实现

python

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        li = []
        for v in pushV:
            if v == popV[len(popV)-1]:
                popV.pop()
            else:
                li.append(v)
        if len(li) == 0:
            return True
        for v in li:
            if v == popV[len(popV)-1]:
                popV.pop()
            else:
                return False
        return True