Check whether a stack can produce a pop order
Your task
A test for a stack class pushes values in a fixed order and pops them at various moments. You have the order in which the values came off, and you want to know whether a real stack could have produced it.
Write validate_stack_sequences(pushed, popped) that returns whether popped is a possible pop order.
Input and output:
pushed: a list of 0 to 1,000 distinct integers, in the order they are pushed.popped: the same values, rearranged, in the order they come off the stack.- Returns true if a stack can produce that order and false if it cannot.
Rules:
- The stack starts empty. Values are pushed in exactly the order of
pushed, each one once. - A pop removes the value on top, the most recently pushed value still on the stack. A pop can happen between any two pushes or after the last push, but never on an empty stack.
- Every value is popped once, and the pops must happen in exactly the order of
popped. - Two empty lists return true.
Examples
validate_stack_sequences(pushed: list[int], popped: list[int]) -> boolExample 1
Input
validate_stack_sequences([1, 2, 3, 4, 5], [4, 5, 3, 2, 1])Output
TrueExample 2
Input
validate_stack_sequences([5, 7, 9], [9, 5, 7])Output
False