algorithms_rs/
stack.rs

1use alloc::vec::Vec;
2
3/// # stack data structure
4/// 在栈中，被删除的是最近插入的元素： 栈的实现是一种后进先出策略。
5/// 这里采用数组实现栈，还有别的方式也是可以实现栈的。
6///
7/// ## 栈的操作
8/// 栈的操作有，栈上的INSERT操作称为压入PUSH,而无元素参数的DELETE操作称为弹出POP。
9#[derive(Debug)]
10pub struct Stack<T> {
11    // data
12    data: Vec<T>,
13    // the stack top pointer, just the vector dynomic length
14    top: usize,
15}
16
17impl<T: Clone> Default for Stack<T> {
18    fn default() -> Self {
19        Self::new()
20    }
21}
22
23impl<T: Clone> Stack<T> {
24    /// Creating an empty stack
25    ///
26    /// ```rust
27    /// use algorithms_rs::Stack;
28    ///
29    /// let stack = Stack::<i32>::new();
30    ///
31    /// assert_eq!(stack.is_empty(), true);
32    /// ```
33    pub fn new() -> Stack<T> {
34        Self {
35            data: Vec::new(),
36            top: 0,
37        }
38    }
39
40    /// Determine if stack is empty
41    ///
42    /// ```rust
43    /// use algorithms_rs::Stack;
44    ///
45    /// let mut stack = Stack::<i32>::new();
46    ///
47    /// assert_eq!(stack.is_empty(), true);
48    ///
49    /// stack.push(2);
50    ///
51    /// assert_eq!(stack.is_empty(), false);
52    /// ```
53    /// ```no
54    /// STACK-EMPTY(S)
55    /// if S.top == 0
56    ///     return true
57    /// else return false
58    /// ```
59    pub fn is_empty(&self) -> bool {
60        self.top == 0
61    }
62
63    /// Put an element into the top of the stack of stack
64    ///
65    /// ```rust
66    /// use algorithms_rs::Stack;
67    ///
68    /// let mut stack = Stack::<i32>::new();
69    ///
70    /// stack.push(1);
71    ///
72    /// assert_eq!(stack.is_empty(), false);
73    /// ```
74    /// ```no
75    /// PUSH(S, x)
76    ///     S.top = S.top + 1
77    ///     S[S.top] = x
78    /// ```
79    pub fn push(&mut self, element: T) {
80        self.top += 1;
81        self.data.push(element);
82    }
83
84    /// Remove an element from the top of the stack of stack
85    ///
86    /// ```rust
87    /// use algorithms_rs::Stack;
88    ///
89    /// let mut stack = Stack::<i32>::new();
90    ///
91    /// stack.push(1);
92    ///
93    /// let element = stack.pop().unwrap();
94    ///
95    /// assert_eq!(element, 1);
96    /// assert_eq!(stack.is_empty(), true);
97    ///
98    /// if let Err(err) = stack.pop() {
99    ///  assert_eq!(err.to_string(), "underflow".to_string())
100    /// }
101    ///
102    /// ```
103    /// ```no
104    /// POP(S)
105    ///     if STACK-EMPTY(S)
106    ///         error "underflow"
107    ///     else
108    ///         S.top = S.top - 1
109    ///         return S[S.top + 1]
110    /// ```
111    pub fn pop(&mut self) -> anyhow::Result<T> {
112        if self.is_empty() {
113            Err(anyhow::anyhow!("underflow"))
114        } else {
115            self.top -= 1;
116            Ok(self.data.remove(self.top))
117        }
118    }
119
120    /// Return the top element of the stack
121    ///
122    /// ```rust
123    /// use algorithms_rs::Stack;
124    ///
125    /// let mut stack = Stack::<i32>::new();
126    ///
127    /// assert_eq!(stack.peek(), None);
128    ///
129    /// stack.push(1);
130    /// stack.push(2);
131    ///
132    /// assert_eq!(stack.peek(), Some(&2));
133    /// assert_eq!(stack.is_empty(), false);
134    /// ```
135    pub fn peek(&self) -> Option<&T> {
136        if self.is_empty() {
137            return None;
138        }
139        self.data.get(self.top - 1)
140    }
141
142    /// the stack size
143    /// ```rust
144    /// use algorithms_rs::Stack;
145    ///
146    /// let stack = Stack::<i32>::new();
147    ///
148    /// assert_eq!(0, stack.size());
149    /// ```
150    pub fn size(&self) -> usize {
151        self.top
152    }
153}
algorithms_rs/stack.rs

algorithms_rs/
stack.rs
