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>>,
}