Module vec_circ_queue

A circular Vec-based queue

About

This simple, safe, Vec-based circular queue is mostly just a fun experiment, but can be used for situations in which you need a fixed-sized buffer with FIFO logic. The circular queue can be used to provide a solution to the Josephus problem.

Design

Rust takes its types (and its type safety) seriously. Array’s must have a known size at compile time, forcing any array-backed structure’s size hard coded. [T; N]

This example illustrates the circular queue logic. The example provides a queue postcondition for enqueue/dequeue operations to illustrate the state of the list after each operation. Remember that enqueue() adds to the back, and dequeue() removes from the front of the queue.

   use dsa_rust::sequences::queues::vec_circ_queue::CircularQueue;

   // The queue is a fixed size
   let mut q: CircularQueue<char> = CircularQueue::new(3);

   // enqueue/dequeue return Result because adding/removing on a
   // full/empty queue is an error
   // Postcondition
   //
   //  <-> a <-> b <-> c <->
   //      ^           ^
   //   front        back
   q.enqueue('a');
   q.enqueue('b');
   q.enqueue('c');

   // The queue is at capacity, and the queue hasn't shifted
   assert_eq!(q.peek().unwrap(), &'a');
   assert_eq!(q.size(), q.capacity());
   assert_eq!(q.front(), 0);
   assert_eq!(q.back(), 2);

   // The queue cannot take additional elements
   assert!(q.enqueue_with_check('d').is_err());

   // Remove the head node and check changes:
   // Postcondition:
   // - There is only one item in the queue
   // - The front and back of the queue point to the same index
   // Postcondition
   //
   //  <-> None <-> b <-> c <->
   //               ^     ^
   //            front  back
   assert_eq!(q.dequeue().unwrap(), 'a');

   // Postcondition
   //
   //  <-> None <-> Non <-> c <->
   //                       ^
   //                  front/back
   assert_eq!(q.dequeue().unwrap(), 'b'); // queue: 0:None, 1:None, 2:c (fr/ba)
   assert_eq!(2, q.capacity() - q.size()); // Remaining capacity
   assert_eq!(q.front(), 2);
   assert_eq!(q.back(), 2);
   assert_eq!(q.size(), 1);

   // Adding new items wraps the queue, hence circular queue
   // Postcondition
   //
   //  <-> d <-> None <-> c <->
   //      ^              ^
   //    back           front
   q.enqueue('d');

   // Postcondition
   //
   //  <-> d <-> e <-> c <->
   //            ^     ^
   //          back  front
   q.enqueue('e');
   assert_eq!(q.front(), 2);
   assert_eq!(q.back(), 1);
   assert_eq!(q.size(), 3);

   // Removes two more elements and checks that there is just one element left
   // Postcondition
   //
   //  <-> d <-> e <-> None <->
   //      ^     ^
   //    front  back
   assert_eq!(q.dequeue().unwrap(), 'c');

   // Postcondition
   //
   //  <-> None <-> e <-> None <->
   //               ^
   //          front/back
   assert_eq!(q.dequeue().unwrap(), 'd');
   assert_eq!(2, q.capacity() - q.size()); // Remaining capacity
   assert_eq!(q.front(), 1);
   assert_eq!(q.back(), 1);
   assert_eq!(q.size(), 1);
   assert_eq!(q.peek().unwrap(), &'e');

Structs

CircularQueue

About

Functions

empirical_test

Illustrates that the for loop is the most efficient way to initialize an array with None values:

example