Queue and Stack Collections in Rust

1. Rust Collection
2. Rust Queue
3. Stack in Rust

This article is about the presence of queue and stack collections in Rust.

Rust Collection

Rust’s standard collection library includes efficient implementations of the most frequently used data structures in general-purpose programming. As a result, two libraries should be able to communicate without requiring much data conversion if they use the standard implementations.

To begin, we should probably use Vec. These two collections cover most storage and processing scenarios for generic data.

They excel at what they do. All of the other collections in the standard library have specific use cases for which they are the optimum choice, but these use cases are instead niche.

Even if Vec and HashMap are technically poor, they are probably a sufficient starting point.

The collections available in Rust can be grouped into four major categories as below.

1. Sequences: Vec, VecDeque, LinkedList
2. Maps: HashMap, BTreeMap
3. Sets: HashSet, BTreeSet
4. Misc: BinaryHeap

Rust Queue

The queue data structure in Rust is used to store the elements. The queue in Rust operates in an FIO fashion, which implies first in, first out.

This is a standard queue that is included with the Rust collection library. It is a linear data structure.

Queue offers us several operations that may be used to manipulate it. It can contain any number of elements; the entire implementation is based on Rust’s vector data structure.

Syntax:

let mut variable_name : Queue<queue_size> = queue![];

Stack in Rust

A stack is a collection of items that can be added to and removed from, but only in the following order: last in - first out (LIFO). For example, if you board an overcrowded train, you will be the first to need to exit for other passengers to do so as well.

Adding objects is typically called push while removing goods is typically called pop because these functions are implemented in Rust using the Vec (vector) data structure.

To create a new stack, we can use the following syntax.

let s = Stack { stack: Vec::new() };

Rust’ does not provide any library with guaranteed latency for adding elements to the standard library. When adding additional elements to Rust collections, memory may be allocated.

In the worst-case scenario, memory allocation may take infinite time.

There are two possible candidates in each case.

1. A stack can be implemented on top of either a Vec or a LinkedList as both support pop back and push back.
2. A queue can be implemented on top of either a VecDeque or a LinkedList as both support pop front and push back.

There is some difference between Vec and LinkedList. The latter is more simplistic: memory is allocated for each call to push back.

On one side, this is favorable because the cost of push back is independent of the number of objects already in the collection. Still, on the other hand, memory allocation can take a long time.

The former is a little more involved because:

1. it has a higher throughput due to its cache-friendly nature
2. it has additional capacity, ensuring that push back is not allocated as long as there is excess capacity; it still maintains amortized O(1) push back even when excess capacity is not reserved in advance

It would be better to use Vec for stacks and VecDeque for queues.