Thread safe Queue in Rust 🦀

Photo by Mae Mu on Unsplash

I started my rust journey 1 year ago and I feel like it helped me a lot to become a better developer, even if I primarily work with React and Typescript.

Today I’d like to share with you what I learned about thread safety in rust, by implementing a simple data structure such as a FIFO queue.

Let’s get started by declaring a trait to describe our queues:

trait Queue<T> {
 /// Creates a new, empty queue
 fn new() -> Self;
 
 /// Enqueue a new value
 fn push(&self, value: T);
 
 /// Dequeue a value 
 /// Returns None if the queue is empty
 fn pop(&self) -> Option<T>;
 
 /// Returns the number of elements enqueued
 fn len(&self) -> usize;
 
 /// Checks if the `size()` is 0
 fn is_empty(&self) -> bool;
}

This trait can then be implemented by a struct or data type to create a queue. The actual implementation of the methods will depend on the type of queue that you want to create.

Implementation

Ok, now that we have our generic trait we can start writing some code for our first queue, the FIFO (*First In, First Out*)

///! queue/mod.rs
use std::collections::VecDeque;

/// A FIFO queue implemented using a VecDeque
struct FifoQueue<T> {
 /// The underlying data structure of the queue
 data: VecDeque<T>
}

It’s a simple generic struct with a `data` parameter holding the enqueued values. We use `VecDeque` over `Vec` for some convenience methods that we’ll see later on.

Now let’s implement our `Queue<T>` trait for `FifoQueue<T>`

///! queue/prelude.rs
impl<T> Queue<T> for FifoQueue<T> {
 fn new() -> Self {
  Self {
   data: VecDeque::new()
  }
 }

 /// Adds an element to the back of the queue
 fn push(&self, value: T) {
  self.data.push_back(value)
 }

 /// Removes an element from the front of the queue
 fn pop(&self) -> Option<T> {
  self.data.pop_front()
 }
 
 fn len(&self) -> usize {
  self.data.len()
 }

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

The reason why we choose to use `VecDeque` over a simple `Vec` is the ability to use the `pop_frop` / `push_back` and later on `pop_back` / `push_front` methods

Thread Safe? How?