栈

From Wikipedia, a stack is an abstract data type that serves as a collection of elements, with two main principal operations, Push and Pop.

Properties

  • Push O(1)
  • Pop head.data O(1) tail.data O(n)
  • Peek O(1)
  1. // the public struct can hide the implementation detail
  2. pub struct Stack<T> {
  3.     head: Link<T>,
  4. }
  6. type Link<T> = Option<Box<Node<T>>>;
  8. struct Node<T> {
  9.     elem: T,
  10.     next: Link<T>,
  11. }
  13. impl<T> Stack<T> {
  14.     // Self is an alias for Stack
  15.     // We implement associated function name new for single-linked-list
  16.     pub fn new() -> Self {
  17.         // for new function we need to return a new instance
  18.         Self {
  19.             // we refer to variants of an enum using :: the namespacing operator
  20.             head: None,
  21.         } // we need to return the variant, so there without the ;
  22.     }
  24.     // As we know the primary forms that self can take: self, &mut self and &self, push will change the linked list
  25.     // so we need &mut
  26.     // The push method which the signature's first parameter is self
  27.     pub fn push(&mut self, elem: T) {
  28.         let new_node = Box::new(Node {
  29.             elem,
  30.             next: self.head.take(),
  31.         });
  32.         // don't forget replace the head with new node for stack
  33.         self.head = Some(new_node);
  34.     }
  35.     ///
  36.     /// In pop function, we trying to:
  37.     /// * check if the list is empty, so we use enum Option<T>, it can either be Some(T) or None
  38.     ///   * if it's empty, return None
  39.     ///   * if it's not empty
  40.     ///     * remove the head of the list
  41.     ///     * remove its elem
  42.     ///     * replace the list's head with its next
  43.     ///     * return Some(elem), as the situation if need
  44.     ///
  45.     /// so, we need to remove the head, and return the value of the head
  46.     pub fn pop(&mut self) -> Result<T, &str> {
  47.         match self.head.take() {
  48.             None => Err("Stack is empty"),
  49.             Some(node) => {
  50.                 self.head = node.next;
  51.                 Ok(node.elem)
  52.             }
  53.         }
  54.     }
  56.     pub fn is_empty(&self) -> bool {
  57.         // Returns true if the option is a [None] value.
  58.         self.head.is_none()
  59.     }
  61.     pub fn peek(&self) -> Option<&T> {
  62.         // Converts from &Option<T> to Option<&T>.
  63.         match self.head.as_ref() {
  64.             None => None,
  65.             Some(node) => Some(&node.elem),
  66.         }
  67.     }
  69.     pub fn peek_mut(&mut self) -> Option<&mut T> {
  70.         match self.head.as_mut() {
  71.             None => None,
  72.             Some(node) => Some(&mut node.elem),
  73.         }
  74.     }
  76.     pub fn into_iter_for_stack(self) -> IntoIter<T> {
  77.         IntoIter(self)
  78.     }
  79.     pub fn iter(&self) -> Iter<'_, T> {
  80.         Iter {
  81.             next: self.head.as_deref(),
  82.         }
  83.     }
  84.     // '_ is the "explicitly elided lifetime" syntax of Rust
  85.     pub fn iter_mut(&mut self) -> IterMut<'_, T> {
  86.         IterMut {
  87.             next: self.head.as_deref_mut(),
  88.         }
  89.     }
  90. }
  92. impl<T> Default for Stack<T> {
  93.     fn default() -> Self {
  94.         Self::new()
  95.     }
  96. }
  98. /// The drop method of singly linked list. There's a question that do we need to worry about cleaning up our list?
  99. /// As we all know the ownership and borrow mechanism, so we know the type will clean automatically after it goes out the scope,
  100. /// this implement by the Rust compiler automatically did which mean add trait `drop` for the automatically.
  101. ///
  102. /// So, the complier will implements Drop for `List->Link->Box<Node> ->Node` automatically and tail recursive to clean the elements
  103. /// one by one. And we know the recursive will stop at Box<Node>
  104. /// https://rust-unofficial.github.io/too-many-lists/first-drop.html
  105. ///
  106. /// As we know we can't drop the contents of the Box after deallocating, so we need to manually write the iterative drop
  108. impl<T> Drop for Stack<T> {
  109.     fn drop(&mut self) {
  110.         let mut cur_link = self.head.take();
  111.         while let Some(mut boxed_node) = cur_link {
  112.             cur_link = boxed_node.next.take();
  113.             // boxed_node goes out of scope and gets dropped here;
  114.             // but its Node's `next` field has been set to None
  115.             // so no unbound recursion occurs.
  116.         }
  117.     }
  118. }
  120. /// Rust has nothing like a yield statement, and there's actually 3 different kinds of iterator should to implement
  122. // Collections are iterated in Rust using the Iterator trait, we define a struct implement Iterator
  123. pub struct IntoIter<T>(Stack<T>);
  125. impl<T> Iterator for IntoIter<T> {
  126.     // This is declaring that every implementation of iterator has an associated type called Item
  127.     type Item = T;
  128.     // the reason iterator yield Option<self::Item> is because the interface coalesces the `has_next` and `get_next` concepts
  129.     fn next(&mut self) -> Option<Self::Item> {
  130.         self.0.pop().ok()
  131.     }
  132. }
  134. pub struct Iter<'a, T> {
  135.     next: Option<&'a Node<T>>,
  136. }
  138. impl<'a, T> Iterator for Iter<'a, T> {
  139.     type Item = &'a T;
  140.     fn next(&mut self) -> Option<Self::Item> {
  141.         self.next.map(|node| {
  142.             // as_deref: Converts from Option<T> (or &Option<T>) to Option<&T::Target>.
  143.             self.next = node.next.as_deref();
  144.             &node.elem
  145.         })
  146.     }
  147. }
  149. pub struct IterMut<'a, T> {
  150.     next: Option<&'a mut Node<T>>,
  151. }
  153. impl<'a, T> Iterator for IterMut<'a, T> {
  154.     type Item = &'a mut T;
  155.     fn next(&mut self) -> Option<Self::Item> {
  156.         // we add take() here due to &mut self isn't Copy(& and Option<&> is Copy)
  157.         self.next.take().map(|node| {
  158.             self.next = node.next.as_deref_mut();
  159.             &mut node.elem
  160.         })
  161.     }
  162. }
  164. #[cfg(test)]
  165. mod test_stack {
  167.     use super::*;
  169.     #[test]
  170.     fn basics() {
  171.         let mut list = Stack::new();
  172.         assert_eq!(list.pop(), Err("Stack is empty"));
  174.         list.push(1);
  175.         list.push(2);
  176.         list.push(3);
  178.         assert_eq!(list.pop(), Ok(3));
  179.         assert_eq!(list.pop(), Ok(2));
  181.         list.push(4);
  182.         list.push(5);
  184.         assert_eq!(list.is_empty(), false);
  186.         assert_eq!(list.pop(), Ok(5));
  187.         assert_eq!(list.pop(), Ok(4));
  189.         assert_eq!(list.pop(), Ok(1));
  190.         assert_eq!(list.pop(), Err("Stack is empty"));
  192.         assert_eq!(list.is_empty(), true);
  193.     }
  195.     #[test]
  196.     fn peek() {
  197.         let mut list = Stack::new();
  198.         assert_eq!(list.peek(), None);
  199.         list.push(1);
  200.         list.push(2);
  201.         list.push(3);
  203.         assert_eq!(list.peek(), Some(&3));
  204.         assert_eq!(list.peek_mut(), Some(&mut 3));
  206.         match list.peek_mut() {
  207.             None => None,
  208.             Some(value) => Some(*value = 42),
  209.         };
  211.         assert_eq!(list.peek(), Some(&42));
  212.         assert_eq!(list.pop(), Ok(42));
  213.     }
  215.     #[test]
  216.     fn into_iter() {
  217.         let mut list = Stack::new();
  218.         list.push(1);
  219.         list.push(2);
  220.         list.push(3);
  222.         let mut iter = list.into_iter_for_stack();
  223.         assert_eq!(iter.next(), Some(3));
  224.         assert_eq!(iter.next(), Some(2));
  225.         assert_eq!(iter.next(), Some(1));
  226.         assert_eq!(iter.next(), None);
  227.     }
  229.     #[test]
  230.     fn iter() {
  231.         let mut list = Stack::new();
  232.         list.push(1);
  233.         list.push(2);
  234.         list.push(3);
  236.         let mut iter = list.iter();
  237.         assert_eq!(iter.next(), Some(&3));
  238.         assert_eq!(iter.next(), Some(&2));
  239.         assert_eq!(iter.next(), Some(&1));
  240.     }
  242.     #[test]
  243.     fn iter_mut() {
  244.         let mut list = Stack::new();
  245.         list.push(1);
  246.         list.push(2);
  247.         list.push(3);
  249.         let mut iter = list.iter_mut();
  250.         assert_eq!(iter.next(), Some(&mut 3));
  251.         assert_eq!(iter.next(), Some(&mut 2));
  252.         assert_eq!(iter.next(), Some(&mut 1));
  253.     }
  254. }