是否有队列和堆栈集合？

Question

如果我们需要FIFO或LIFO集合(与基本push,pop和front/ back)我们应该在锈使用？像std::queue或std::stack从C++.

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()

如果您希望最大限度地提高效率，我建议您查看“了解 Rust 的 Vec 及其快速高效程序的能力”。它详细介绍了如何在Vecand 中进行分配和重新分配VecDeque，但最大的收获是，如果您可以预测队列中需要的最大元素数，则可以使用，VecDeque::with_capacity(x)如果您知道何时初始化它，或者.reserve_exact(x)如果在某个时候您确切地知道您将需要多少个插槽

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

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

use std::collections::VecDeque;