Are there any queue and stack collections?

Question

If we need FIFO or LIFO collections (mainly 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 a guaranteed delay for adding elements: Rust collections can usually allocate memory when new elements are added, and allocating memory can take an unlimited amount of time in the worst case.

Moreover, for each case there are two applicants:

• the stack can be implemented either on top of Vec or LinkedList (both pop_back and push_back functions)
• the queue can be implemented either on top of VecDeque or LinkedList (both pop_front and push_back functions)

The difference between Vec* and LinkedList is that the latter is simplified: memory is allocated for each push_back call. On the one hand, this is great, because it means that the cost of push_back does not depend on the number of elements that are already in the collection, on the other hand ... well, memory allocation can take a very long time.

The first is a bit more complicated:

• it has better throughput due to more convenient caching
• it has extra capacity, ensuring that push_back is not push_back while there is excess capacity.
• it still retains the depreciation of O (1) push_back , even if you do not reserve excess power ahead of time

In general, I would recommend using Vec for the stack and VecDeque for the queue.

Answer 2

Both VecDeque and LinkedList have push / pop _ front / back .

Answer 3

Mathieu M. is almost perfect. Vec is your stack (LIFO), and VecDeque is a two-way queue that supports all 4 options (FIFO, FILO, LIFO and LILO), using:

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

If you want to maximize your efficiency, I recommend that you read the section "Overview of Rusts Vec and its ability to create fast and efficient programs . " It talks in more detail about how distribution and redistribution occurs in Vec and VecDeque , but the biggest VecDeque is that if you can predict the maximum number of elements you 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 will need

I highly recommend that you read the Rust documentation at std::collections , it has an excellent list of the most common collections used in Rust, as well as suggestions on when to choose each one.

Lastly, VecDeque not part of the default foreplay in Rust, so if you want to use it, you need to enable this:

 use std::collections::VecDeque;