Are there queue and stack collections in Rust?

Question

If we need FIFO or LIFO collections (with basically push, pop and front/back) what should we use in Rust? Something like std::queue or std::stack from C++.

Answer 1

First of all, Rust does not offer (in the Standard library) any library with guaranteed latency for adding elements: Rust collections may generally allocate memory when adding new elements, and allocating memory may take an unbounded amount of time in the worst case.

That being said, there are two contenders for each case:

• a stack may be implemented either on top of Vec or LinkedList (both feature pop_back and push_back)
• a queue may be implemented either on top of VecDeque or LinkedList (both feature pop_front and push_back)

The difference between Vec* and LinkedList is that the latter is simplistic: for each call to push_back a memory allocation is made. On the one hand, this is great because it means that the cost of push_back is independent of the number of elements already in the collection, on the other hand... well, a memory allocation may take a really long time.

The former is a bit more complicated:

• it has better throughput, thanks to being more cache-friendly
• it has additional capacity, guaranteeing non-allocating push_back as long as there is excess capacity
• it still maintains amortized O(1) push_back even when not reserving excess capacity ahead of time

In general, I would advise to use Vec for a stack and VecDeque for a queue.

Answer 2

Both VecDeque and LinkedList have push/pop_front/back.

Answer 3

Matthieu M. has it just about perfect. Vec is your stack (LIFO) and VecDeque is a double ended queue that supports all 4 variants (FIFO, FILO, LIFO, and LILO) using:

.push_front(x) | .front() | .pop_front()
.push_back(x)  | .back()  | .pop_back()

If you're looking to maximize your efficiency, I recommend checking out "Unterstanding Rust’s Vec and its capacity for fast and efficient programs". It goes into a lot more detail about how allocation and reallocation occurs in Vec and VecDeque, but the biggest take away is that if you can predict the maximum number of elements you're going to need in the queue you can use VecDeque::with_capacity(x) if you know when you initialize it, or .reserve_exact(x) if at some point you know exactly how many more slots you're going to need

I strongly recommend checking out the Rust docs on std::collections, it has an excellent list of the most common collections used in Rust, along with suggestions on when to pick each

One last thing, VecDeque isn't part of the default prelude in Rust so if you want to use it you need to include this:

use std::collections::VecDeque;