Implementing a Stack in Rust: A Simple and Versatile Data Structure

In this article, we will walk through the implementation of a basic stack data structure in Rust, leveraging generics to make it versatile for various types. The stack follows a "Last In, First Out" (LIFO) principle, meaning the last added element is the first to be removed.

This implementation is part of the library available in the crate structo, which can be imported with the following:

use structo::stack::Stack;

The full code is hosted on Gabriel Rufino's GitHub repository.

The Stack Struct

The foundation of this implementation is the Stack struct, which uses a vector (Vec<T>) to store elements. By using generics (T), the stack becomes flexible, allowing you to store any data type.

pub struct Stack<T> {
  elements: Vec<T>,
}

Now, let's dive into each method that makes this stack functional.

1. Creating a new stack with new()

The new() method initializes an empty stack. This is the starting point for using the stack.

impl<T> Stack<T> {
  pub fn new() -> Self {
    Stack {
      elements: Vec::new(),
    }
  }
}

With this, you can create a new stack like this:

let stack: Stack<i32> = Stack::new();

This stack is now ready to accept integers (or any other type) as elements.

2. Adding elements with push()

The push() method adds a new element to the top of the stack. Internally, it uses the vector's push method to append the element.

pub fn push(&mut self, item: T) {
  self.elements.push(item);
}

For example:

stack.push(10);
stack.push(20);

Here, 10 is added first, followed by 20, which becomes the top element of the stack.

3. Checking if the stack is empty with is_empty()

The is_empty() method checks if the stack has no elements and returns a boolean value.

pub fn is_empty(&self) -> bool {
  self.elements.is_empty()
}

This method is handy for determining if it's safe to call pop() without expecting None.

if stack.is_empty() {
  println!("Stack is empty!");
}

4. Removing elements with pop()

The pop() method removes and returns the top element of the stack. If the stack is empty, it returns None. This is how the "Last In, First Out" nature of the stack is implemented.

pub fn pop(&mut self) -> Option<T> {
  if self.is_empty() {
    None
  } else {
    self.elements.pop()
  }
}

Calling pop() on a stack that contains elements will remove the last one:

let top = stack.pop();  // top is Some(20)

5. Getting the size with size()

The size() method returns the number of elements in the stack. It simply returns the length of the internal vector.

pub fn size(&self) -> usize {
  self.elements.len()
}

For example, after pushing two elements, calling size() will return 2.

println!("Stack size: {}", stack.size());  // Output: 2

6. Peeking at the top element with peek()

The peek() method returns a reference to the top element without removing it. If the stack is empty, it returns None.

pub fn peek(&self) -> Option<&T> {
  self.elements.last()
}

This method is useful when you need to inspect the top element without modifying the stack:

if let Some(top) = stack.peek() {
  println!("Top element: {}", top);
}

7. Implementing the Default trait

For convenience, the Default trait is implemented for Stack, allowing you to create a new stack using Default::default(). This calls the new() method internally.

impl<T> Default for Stack<T> {
  fn default() -> Self {
    Self::new()
  }
}

Now, you can create a stack as follows:

let stack: Stack<i32> = Default::default();

This makes instantiating a new stack easier, especially when integrating with other parts of Rust that use the Default trait.

Conclusion

In this article, we've implemented a flexible and powerful stack in Rust using generics. Each method—new, push, pop, is_empty, size, and peek—provides a crucial operation to make the stack functional and versatile for various use cases. The stack can handle any data type, offering a robust tool for your Rust projects.

If you'd like to dive deeper into this implementation or contribute, you can explore the full code in the structo crate on Gabriel Rufino's GitHub repository.