class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:

        stack = []
        while popped:
            if pushed and pushed[0] == popped[0]:
                pushed.pop(0)
                popped.pop(0)
            elif stack and stack[-1] == popped[0]:
                stack.pop()
                popped.pop(0)
            elif pushed:
                stack.append(pushed.pop(0))
            else:
                return False
        return True