946. Validate Stack Sequences

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

 

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

 

Constraints:

  • 0 <= pushed.length == popped.length <= 1000
  • 0 <= pushed[i], popped[i] < 1000
  • pushed is a permutation of popped.
  • pushed and popped have distinct values.

Rust Solution

struct Solution;

impl Solution {
    fn validate_stack_sequences(pushed: Vec<i32>, popped: Vec<i32>) -> bool {
        let mut stack = vec![];
        let mut it = popped.iter().peekable();
        for x in pushed {
            stack.push(x);
            while let (Some(&a), Some(&&b)) = (stack.last(), it.peek()) {
                if a == b {
                    stack.pop();
                    it.next();
                } else {
                    break;
                }
            }
        }
        stack.is_empty()
    }
}

#[test]
fn test() {
    let pushed = vec![1, 2, 3, 4, 5];
    let popped = vec![4, 5, 3, 2, 1];
    let res = true;
    assert_eq!(Solution::validate_stack_sequences(pushed, popped), res);
    let pushed = vec![1, 2, 3, 4, 5];
    let popped = vec![4, 3, 5, 1, 2];
    let res = false;
    assert_eq!(Solution::validate_stack_sequences(pushed, popped), res);
}

Having problems with this solution? Click here to submit an issue on github.