42. 栈的压入、弹出序列python

栈是一种具有后进先出(LIFO)特性的数据结构，压入即将元素放入栈顶，弹出即从栈顶取出元素。给定一个原始序列，判断另一个序列是否为该栈的合法弹出序列是一个常见的问题。

下面是一个用Python实现栈的压入、弹出序列的例子：

def validate_stack_sequences(pushed, popped):
    stack = []
    i = 0  # 用于遍历弹出序列的指针

    for num in pushed:
        stack.append(num)  # 元素入栈

        # 当栈不为空且栈顶元素等于当前弹出序列的元素时，执行弹出操作
        while stack and stack[-1] == popped[i]:
            stack.pop()
            i += 1

    # 如果所有元素都已经入栈但是还有未弹出的元素，说明不是合法的弹出序列
    if i == len(popped):
        return True
    else:
        return False

# 示例测试
pushed = [1, 2, 3, 4, 5]
popped = [4, 5, 3, 2, 1]
print(validate_stack_sequences(pushed, popped))  # 输出 True

pushed = [1, 2, 3, 4, 5]
popped = [4, 3, 5, 1, 2]
print(validate_stack_sequences(pushed, popped))  # 输出 False

以上是一个简单的栈的压入、弹出序列的实现，通过遍历压入序列并模拟栈的压入和弹出操作，最后判断是否所有元素都已经弹出。在示例测试中，第一个弹出序列是合法的，第二个弹出序列是非法的。