leetcode_rust/
min_stack.rs

1#![allow(dead_code)]
2
3#[derive(Debug, Clone)]
4pub struct MinStack {
5    top: Option<Box<StackNode>>,
6}
7
8#[derive(Debug, Clone)]
9struct StackNode {
10    val: i32,
11    next: Option<Box<StackNode>>,
12}
13
14impl MinStack {
15    pub fn new() -> Self {
16        Self { top: None }
17    }
18
19    pub fn is_empty(&self) -> bool {
20        match &self.top {
21            None => true,
22            Some(_) => false,
23        }
24    }
25
26    pub fn push(&mut self, x: i32) {
27        match &self.top {
28            None => {
29                self._push(x);
30            }
31
32            Some(_) => {
33                let min = self.get_min();
34                if x < min {
35                    self._push(x);
36                } else {
37                    self._push(min);
38                }
39            }
40        }
41        self._push(x);
42    }
43
44    fn _push(&mut self, x: i32) {
45        let mut node = StackNode { val: x, next: None };
46        let next = self.top.take();
47        node.next = next;
48        self.top = Some(Box::new(node));
49    }
50
51    pub fn pop(&mut self) {
52        if self.is_empty() {
53            return;
54        }
55        self._pop();
56        self._pop();
57    }
58
59    fn _pop(&mut self) {
60        let node = self.top.take();
61        match node {
62            Some(mut x) => self.top = x.next.take(),
63            None => {}
64        };
65    }
66
67    pub fn top(&self) -> i32 {
68        match &self.top {
69            Some(x) => x.val,
70            None => unreachable!(),
71        }
72    }
73
74    pub fn get_min(&self) -> i32 {
75        match &self.top {
76            None => unreachable!(),
77            Some(cur) => match &cur.next {
78                None => unreachable!(),
79                Some(min) => min.val,
80            },
81        }
82    }
83}
84
85#[cfg(test)]
86mod tests {
87    use super::*;
88
89    #[test]
90    fn test1() {
91        let mut stack = MinStack::new();
92        stack.push(-2);
93        stack.push(0);
94        stack.push(-1);
95        assert_eq!(stack.get_min(), -2);
96        assert_eq!(stack.top(), -1);
97        stack.pop();
98        assert_eq!(stack.get_min(), -2);
99    }
100}
leetcode_rust/min_stack.rs

leetcode_rust/
min_stack.rs
