面试题31： 栈的压入和弹出序列

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

解题思路：
这道题需要模拟一下实际情况中压入和弹出的情况，然后总结规律，需要借助一个辅助栈，具体的思路如下：

31 栈的压入 弹出序列（当出栈序列不为空时）.png

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        
        #辅助栈
        stack = []  
        while popV:
            #入栈列的栈顶元素与当前要弹出的元素相同，则直接同时pop
            if pushV and pushV[0]==popV[0]:
                pushV.pop(0)
                popV.pop(0)
            #辅助栈的栈顶元素为当前要弹出的元素，辅助栈和popV同时pop
            elif stack and stack[-1] == popV[0]:
                stack.pop()     #弹出最后压入的元素
                popV.pop(0)     #弹出当前要弹的元素
            #当前要弹出的元素不符合上述两种情况
            elif pushV:
                stack.append(pushV.pop(0))  #把入栈序列的元素依次压入
            #如果入栈序列已经为空，说明该序列不是出栈序列
            else:
                return False
        return True

提交结果：

image.png