graph_collections/
stack.rs

1use std::iter::FromIterator;
2
3/// A LIFO stack backed by a [`Vec`].
4///
5/// Elements are pushed and popped from the top of the stack.
6/// All operations are O(1) amortized.
7///
8/// # Examples
9/// ```
10/// use graph_collections::Stack;
11/// let mut s: Stack<i32> = Stack::new();
12/// s.push(1);
13/// s.push(2);
14/// assert_eq!(s.pop(), Some(2));
15/// assert_eq!(s.peek(), Some(&1));
16/// assert_eq!(s.len(), 1);
17/// assert!(!s.is_empty());
18/// ```
19#[derive(Debug, Clone, PartialEq)]
20pub struct Stack<T> {
21    data: Vec<T>,
22}
23
24impl<T> Default for Stack<T> {
25    fn default() -> Self {
26        Self { data: Vec::new() }
27    }
28}
29
30impl<T> From<Vec<T>> for Stack<T> {
31    fn from(data: Vec<T>) -> Self {
32        Self { data }
33    }
34}
35
36impl<T> FromIterator<T> for Stack<T> {
37    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
38        Self {
39            data: Vec::from_iter(iter),
40        }
41    }
42}
43
44/// A consuming iterator over a [`Stack`], yielding elements in LIFO order.
45pub struct IntoIter<T>(Stack<T>);
46
47impl<T> Iterator for IntoIter<T> {
48    type Item = T;
49
50    fn next(&mut self) -> Option<T> {
51        self.0.pop()
52    }
53
54    fn size_hint(&self) -> (usize, Option<usize>) {
55        let len = self.0.len();
56        (len, Some(len))
57    }
58}
59
60impl<T> ExactSizeIterator for IntoIter<T> {}
61
62impl<T> IntoIterator for Stack<T> {
63    type Item = T;
64    type IntoIter = IntoIter<T>;
65
66    fn into_iter(self) -> IntoIter<T> {
67        IntoIter(self)
68    }
69}
70
71impl<T> Stack<T> {
72    /// Creates a new empty stack.
73    ///
74    /// # Examples
75    /// ```
76    /// use graph_collections::Stack;
77    /// let s: Stack<i32> = Stack::new();
78    /// assert!(s.is_empty());
79    /// ```
80    pub fn new() -> Self {
81        Self::default()
82    }
83
84    /// Pushes a value onto the top of the stack.
85    ///
86    /// # Examples
87    /// ```
88    /// use graph_collections::Stack;
89    /// let mut s: Stack<i32> = Stack::new();
90    /// s.push(10);
91    /// assert_eq!(s.peek(), Some(&10));
92    /// ```
93    pub fn push(&mut self, value: T) {
94        self.data.push(value);
95    }
96
97    /// Removes and returns the top value, or `None` if the stack is empty.
98    ///
99    /// # Examples
100    /// ```
101    /// use graph_collections::Stack;
102    /// let mut s: Stack<i32> = Stack::new();
103    /// s.push(1);
104    /// s.push(2);
105    /// assert_eq!(s.pop(), Some(2));
106    /// assert_eq!(s.pop(), Some(1));
107    /// assert_eq!(s.pop(), None);
108    /// ```
109    pub fn pop(&mut self) -> Option<T> {
110        self.data.pop()
111    }
112
113    /// Returns a reference to the top value without removing it,
114    /// or `None` if the stack is empty.
115    ///
116    /// # Examples
117    /// ```
118    /// use graph_collections::Stack;
119    /// let mut s: Stack<i32> = Stack::new();
120    /// s.push(5);
121    /// assert_eq!(s.peek(), Some(&5));
122    /// assert_eq!(s.len(), 1); // peek does not remove
123    /// ```
124    #[must_use]
125    pub fn peek(&self) -> Option<&T> {
126        self.data.last()
127    }
128
129    /// Returns `true` if the stack contains no elements.
130    ///
131    /// # Examples
132    /// ```
133    /// use graph_collections::Stack;
134    /// let mut s: Stack<i32> = Stack::new();
135    /// assert!(s.is_empty());
136    /// s.push(1);
137    /// assert!(!s.is_empty());
138    /// ```
139    #[must_use]
140    pub fn is_empty(&self) -> bool {
141        self.data.is_empty()
142    }
143
144    /// Returns the number of elements in the stack.
145    ///
146    /// # Examples
147    /// ```
148    /// use graph_collections::Stack;
149    /// let mut s: Stack<i32> = Stack::new();
150    /// s.push(1);
151    /// s.push(2);
152    /// assert_eq!(s.len(), 2);
153    /// ```
154    #[must_use]
155    pub fn len(&self) -> usize {
156        self.data.len()
157    }
158}
graph_collections/stack.rs

graph_collections/
stack.rs
