是否有队列和堆栈集合？

Question

如果我们需要FIFO或LIFO集合（基本上是push，pop和front / back）我们应该在Rust中使用什么？像C ++中的std::queue或std::stack。

Answer 1

首先，Rust没有（在标准库中）提供任何具有保证的添加元素延迟的库：Rust集合通常可以在添加新元素时分配内存，并且在最坏的情况下分配内存可能需要无限量的时间。

话虽如此，每个案例都有两个竞争者：

• 堆栈可以在Vec或LinkedList（都是pop_back和push_back）之上实现
• 队列可以在VecDeque或LinkedList（都是pop_front和push_back）之上实现

Vec*和LinkedList之间的区别在于后者是简单化的：每次调用push_back都会进行内存分配。一方面，这很好，因为这意味着push_back的成本与集合中已有元素的数量无关，另一方面......内存分配可能需要很长时间。

前者有点复杂：

• 由于更加缓存友好，它具有更好的吞吐量
• 它有额外的容量，只要有过剩的容量，保证不分配push_back
• 它仍然维持摊销的O（1）push_back，即使没有提前保留过剩的产能

一般来说，我建议使用Vec作为堆栈，使用VecDeque作为队列。

Answer 2

VecDeque和LinkedList都有push / pop_front / back。

Answer 3

Matthieu M.说得很完美。 Vec是你的堆栈（LIFO），VecDeque是一个双端队列，支持所有4种变体（FIFO，FILO，LIFO和LILO），使用：

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

如果您希望最大限度地提高效率，我建议您查看"Unterstanding Rust’s Vec and its capacity for fast and efficient programs"。它详细介绍了如何在Vec和VecDeque中进行分配和重新分配，但最大的收获是，如果你能预测队列中你需要的最大元素数，你可以使用VecDeque::with_capacity(x)，如果你知道的话当你初始化它，或者.reserve_exact(x)，如果在某些时候你确切知道你需要多少个插槽

我强烈建议您查看std::collections上的Rust文档，它有一个很好的Rust列表中最常用的集合，以及何时选择每个集合的建议

最后一点，VecDeque不是Rust中默认前奏的一部分，所以如果你想使用它，你需要包含这个：

use std::collections::VecDeque;