56 lines
1.3 KiB
Rust
56 lines
1.3 KiB
Rust
struct Solution {}
|
|
impl Solution {
|
|
pub fn validate_stack_sequences(pushed: Vec<i32>, popped: Vec<i32>) -> bool {
|
|
let mut stack: Vec<i32> = vec![];
|
|
|
|
let mut i = 0;
|
|
let mut j = 0;
|
|
|
|
loop {
|
|
// If the top is to be popped, pop it
|
|
if let Some(&top) = stack.last() {
|
|
if j < popped.len() && top == popped[j] {
|
|
stack.pop();
|
|
j += 1;
|
|
continue;
|
|
}
|
|
}
|
|
|
|
// If I have an element that can be pushed, push it
|
|
if i < pushed.len() {
|
|
stack.push(pushed[i]);
|
|
i += 1;
|
|
continue;
|
|
}
|
|
|
|
// If I can't pop nor push, it's done or screwed up
|
|
break;
|
|
}
|
|
|
|
// If it's correct simulation, stack must be empty
|
|
stack.is_empty()
|
|
}
|
|
}
|
|
|
|
fn main() {}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
|
|
#[test]
|
|
fn success() {
|
|
assert!(Solution::validate_stack_sequences(
|
|
vec![1, 2, 3, 4, 5],
|
|
vec![4, 5, 3, 2, 1]
|
|
));
|
|
}
|
|
|
|
#[test]
|
|
fn fail() {
|
|
assert!(!Solution::validate_stack_sequences(
|
|
vec![1, 2, 3, 4, 5],
|
|
vec![4, 3, 5, 1, 2]
|
|
));
|
|
}
|
|
}
|