《剑指offer》27、合法的pop序列

前言

本来这个应该和之前的26、包含min功能的栈写在一起的，都是辅助栈的应用。不过26的代码比较长，所以还是分开了。
本次题目的要求是：给出入栈序列push和一个出栈序列pop，判断pop序列是否合法。

分析

我们先上图说话

通过图左的合法序列和图右的不合法序列，我们可以得出一个判断依据：

1、如果下一个弹出的数字刚好是栈顶数字，那么直接弹出
2、如果下一个弹出的数字不在栈顶，我们就要把压栈序列中还没有入栈的数字继续压栈，直到下一个弹出的数字刚好是栈顶数字，即回到1
3、如果压栈到穿序列仍然没有回到1，那么pop序列不合法。

对于第二步，我们利用一个辅助栈就可以完成。

代码

# offer27-solution
def IsPopOrder(pushV, popV):
    stack = []
    while popV:
        # 元素进栈后立即出栈
        if pushV and pushV[0] == popV[0]:
            pushV.pop(0)
            popV.pop(0)
        # 如果当前辅助栈中的栈顶元素刚好是要弹出的元素，那么直接弹出
        elif stack and stack[-1] == popV[0]:
            stack.pop()
            popV.pop(0)
        # 不断往辅助栈中压入元素
        elif pushV:
            stack.append(pushV.pop(0))
        else:
            return False
    return True