Implementing a Stack in Rust.

Stacks belong to the commonly used data structures especially when implementing optimized algorithms. There entire philosophy rely on the so called LIFO principle (Last In First Out). This actually already describes most of the mechanism behind a stack.

A stack

1. let’s you put an element to it: push
2. let’s you remove and receive the last put element: pop
3. let’s you view the last put element: peek

In this story, we are going to look at a possible implementation of a stack in Rust. As usually, due to Rust’s ownership model, the realization of such a data structure is not as straightforward as with other reference based languages, but like always, the effort pays out when it comes to performance and stability. If you are new to Rust and still struggle with understanding this ownership model, you may have a look at my Rust tutorial for beginners.

Implementation:

The stack consists of two data types, the nodes that own the hierarchy resp. data

struct Node<T> {
  data: T,
  next: Option<Box<Node<T>>>,
}

and the stack itself that owns the top node

struct Stack<T> {
  top: Option<Node<T>>,
}

next and top possibly can be empty, marking the end of the stack resp. an empty stack. Therefore we have to wrap the type into an Option. Moreover, because the Node is a recursive type we have to wrap its next value with a Box. This ensures only the pointer gets stored in the data structure and hence the size is known to the compiler.

In the following, let us implement all the above mentioned operations for a stack. We start with an utility to create a new Node:

impl<T> Node<T> {
  fn new(data: T) -> Node<T> {
    Node { data, next: None }
  }
}

This allows us to create a new Node simply by

let node = Node::<u32>::new(3);

A similar thing we can do for the Stack:

impl<T> Stack<T> {
  fn new() -> Stack<T> {
    Stack { top: None }
  }
}

A further utility for the Stack could be this

impl<T> Stack<T> {
  fn is_empty(&self) -> bool {…