Study Plan For Algorithms - Part25

1. 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
方法一：

def validateStackSequences(pushed, popped):
    stack = []
    len_pushed = len(pushed)
    stack_index = 0
    i = 0
    while i < len_pushed:
        stack.append(pushed[i])
        while stack and stack[-1] == popped[stack_index]:
            stack.pop()
            stack_index += 1
        i += 1
    return not stack

方法二：

def validateStackSequences(pushed, popped):
    stack = []
    i = 0
    j = 0

    while i < len(pushed):
        stack.append(pushed[i])
        i += 1

        while stack and stack[-1] == popped[j]:
            stack.pop()
            j += 1

    return len(stack) == 0

方法三：

def validateStackSequences(pushed, popped):
    stack = []
    j = 0

    for num in pushed:
        stack.append(num)
        while stack and stack[-1] == popped[j]:
            stack.pop()
            j += 1

    return j == len(popped)