判断出栈结果是否正确

问题描述：对于进栈为顺序为1、2、3、4、5、6 ··· ，下列哪些不可能是栈的弹出顺序？

例如：

判断出栈结果的合法性

解题思路：利用栈和队列模拟入栈、出栈顺序即可解决此问题

1、将待处理的出栈结果存入order队列中
2、按元素顺序，将元素push进栈
3、每push一个元素，检查是否与队列首元素相同，若相同则弹出队列首元素，弹出栈顶元素，知道两个元素 不同
4、若最重栈为空，说明序列合法，否则不合法

入栈元素为1、2、3、4、5，序列为3、2、5、4、1，判断其合法性：

元素 1 入栈并判断

元素 2 入栈并判断、元素 3 入栈并弹出

元素 4 入栈并判断

代码：

n = order.size() + 1
    for x in range(1, n):  
        self.stack.push(x)
        while self.stack.empty != None and order.front() == self.stack.top:
            self.stack.pop()
            self.order.pop()

    if self.stack.empty():
        return False
    else:
        return True

算法复杂度分析:

• 算法的复杂度为O(n)！！！不是O(n^2)！！！因为所有的元素只入栈出栈一次！