Are there queue and stack collections in Rust?

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++.

First of all, Rust does not offer (in the Standard library) any collection 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.

Stack Overflow Q#40848918, score: 122