22、栈的压入、弹出序列

剑指offer中的解释，没有什么所谓的辅助栈，就只有一个栈。
如果当前栈顶元素不是想要弹出的元素，那么就接着把压栈序列中还没有入栈的数字压入栈中，直到把下一个需要弹出的数字压入栈顶为止。

比如，对于1,2,3,4,5,6，想要判断弹出序列4,6,5,3,2,1是不是正确的。
那么，在一开始想要弹出4，而此时栈顶元素不是4，那么就一直压入，压入1,2,3,4，以后，发现栈顶元素是4，那么就直接弹出4。
接下来，想要弹出6，而此时栈顶元素是3，不是想要弹出的元素，因此，需要接着压入压栈序列中余下的元素5,6，当栈顶元素是6时，此时栈自顶向下是6,5,3,2,1，因此，弹出6以后，压栈序列为空，那么就只能按照5,3,2,1弹出剩下元素了。

再比如，如下图，对于1,2,3,4,5，判断4,3,5,1,2是不是正确的出栈序列。

整理好上面三个步骤，即可写代码了。
代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        #题目未说栈为空的情况，因此这里不予考虑

        #先为栈，添加进一个元素，方便下面操作
        S = []
        S.append(pushV.pop(0))
        done = True
        for pop_num in popV:
            if done == False:
                break
            while done:
                #若弹出元素等于栈顶元素，那么就弹出该元素，执行下一个出栈元素的判断
                if pop_num == S[-1]:
                    S.pop()
                    break
                else:
                    #若弹出元素不等于栈顶元素，并且入栈序列不为空，
                    #则把入栈序列中还没入栈的元素继续压入
                    if len(pushV) != 0:
                        S.append(pushV.pop(0))
                    #如果弹出元素不等于栈顶元素，并且此时入栈序列已经为空，说明遍历完了
                    #那么此时说明这个序列不可能是一个弹出序列
                    else:
                        done = False
        return done