栈的压入&弹出顺序.md

栈的压入&弹出顺序

知识点：栈

题目描述

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

解题思路

对照popV，依次遍历pushV，如果当前待压栈的数与当前可能弹栈的元素相等，则跳过该元素的压栈，否则正常压栈，调到下一个待验证的可能弹栈元素，到最后如果压入栈中的元素个数为0或者压好的栈与剩余的可能弹出栈的元素刚好是相反的则返回True，否则返回False。

代码

    
    def IsPopOrder(self, pushV, popV):
        # write code here
        size = len(pushV)
        popIndex = 0
        a = []
        for i in range(size):
            if pushV[i] == popV[popIndex]:
                popIndex += 1
            else:
                a.append(pushV[i])
        
        if len(a)==0:
            return True

        if popIndex >= size:
            return False
        else:
            size2 = len(a)
            if size2 != size - popIndex:
                return False
            else:
                flag = True
                for i in range(size2):
                    if a[i] != popV[- (i+1)]:
                        flag = False
                        break
                    else:
                        popIndex += 1
                return flag

这里