1 题目
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回false 。
例子
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
2 解析
pushed的元素依次进栈，每次进栈后，先对比栈顶和poped的值，如果相同，就出栈，poped指向第二个元素，直到对比完poped；不相同，pushed进栈下一个元素。最后进栈完毕并对比完poped，如果最后栈为空则返回True，否则返回False
3 Python实现
class Solution: def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool: # 利用栈来模拟入栈和出栈操作 stack = [] # index 表示 popped 数组中元素的下标 # 比如 popped 是 [4,5,3,2,1] # 那么第 0 个下标元素是 4 这个数字 # 先去判断这个数字能否正常的出栈 index = 0 # 遍历 pushed 数组中的每个元素 for item in pushed: # 在遍历 pushed 数组时，把当前遍历的元素加入到栈中 stack.append(item) # 加入完之后，不断的执行以下的判断 # 1、栈中是否有元素 # 2、栈顶元素是否和 popped 当前下标的元素相同 # 如果同时满足这两个条件 # 说明这个元素可以满足要求，即可以在最初空栈上进行推入 push 和弹出 pop 操作 while stack and stack[-1] == popped[index] : # 那么就把栈顶元素弹出 stack.pop() # 同时 index++，观察 popped 下一个元素 index += 1 return len(stack) ==0
