Lib.rs

一个用Rust编写的替代Deque实现。

AltDeque是标准库中VecDeque的替代品。它公开了大多数相同的方法，并且具有相同的性能特性。但它不是使用环形缓冲区在两端实现高效的插入，而是使用两个栈。一个栈用于deque每端的push和pop元素。如果在一端调用pop，但其栈为空，则从另一栈中删除所有元素，反转并放入其中。这个操作需要O(n)时间（其中n是deque的长度），但之后可以以常数时间弹出n个元素，从而实现弹出操作的摊销运行时间为O(1)。

为了更有效地使用内存，两个栈都位于一个分配的缓冲区的两端

        growth ->               <- growth
+- back stack --+               +- front stack -+
|               |               |               |
v               v               v               v
+---+---+---+---+---+---+---+---+---+---+---+---+
| 4 | 5 | 6 | 7 |   |   |   |   | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+---+---+---+
                  |               |
            head -+               +- tail

这种基于栈的方法与环形缓冲区相比有一些优点

• 不需要掩码或模运算来访问元素
• 不需要2的幂次方容量
• 不需要始终留一个元素为空

但它也有一些缺点

• 访问元素需要额外的分支来检查它们在哪个栈中
• 弹出元素仅是摊销常数时间，如果对应的栈为空，单个弹出调用将需要线性时间
• 从两端交替弹出元素非常低效，因为每次改变方向时都需要将所有元素从一侧移动到另一侧

在我的简单测试中，AltDeque和VecDeque对于简单的push_back和pop_front工作负载速度几乎相同。

一些代码和大量文档及示例来自rust仓库中的代码，因此归功于其贡献者。