Simulate Stack

Problem Statement

You are given two sequences of integers: pushed and popped. The pushed sequence lists the order in which elements are added to a stack, and the popped sequence lists the order in which they are removed. Determine whether the popped sequence could have been produced by a series of valid stack operations (push and pop) applied to the pushed sequence.

Function Signature

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

Examples

Example 1

Input:  pushed = [1, 2, 3, 4, 5], popped = [4, 5, 3, 2, 1]
Output: True

Explanation:
Push 1, 2, 3, 4 → pop 4 → push 5 → pop 5 → pop 3 → pop 2 → pop 1. The popped order matches.

pushed = [1, 2, 3, 4, 5]
popped = [4, 5, 3, 2, 1]

true

Example 2

Input:  pushed = [1, 2, 3, 4, 5], popped = [4, 3, 5, 1, 2]
Output: False

Explanation:
Push 1, 2, 3, 4 → pop 4 → pop 3 → push 5 → pop 5. At this point the stack contains [1, 2] with 2 on top. The next expected pop is 1, but 2 must be popped first. The sequence cannot be realized.

Example 3

Input:  pushed = [1, 0], popped = [1, 0]
Output: True

Explanation:
Push 1 → pop 1 → push 0 → pop 0. The operations are straightforward.

Constraints

• The lengths of pushed and popped are equal and at most 1000.
• The sequences contain integers.