rust - Rust 中有队列和堆栈集合吗？

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。