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}