java - 获取第 i 个元素时 FIFO 实现的数据结构

Question

我想要一个固定大小且可用作 FIFO 的数据结构。我的意思是，如果大小超过第一个元素将被删除。另外，在每次插入后，我想检查该结构的中间元素(即大小为 21 的第 10 个元素)

我考虑使用ArrayDeque，但Deque接口(interface)不考虑顺序。即获取第 i 个元素)

我将把它用于一个耗时的过程，性能对我来说很重要。适合我的目的的建议数据结构是什么？

Answer 1

假设我们正在讨论一个通常包含大量元素的 FIFO。

• ArrayList 不是一个好的选择，因为删除列表开头的元素是一个 O(N) 操作。 (对于包含 N 个元素的列表)

• LinkedList可能不是一个好的选择，因为获取第 N 个元素是一个 O(N) 操作。

我认为你需要一个由数组支持的循环缓冲区。这将为您提供 O(1) FIFO 插入、O(1) FIFO 删除以及从 FIFO 开始对元素 i 进行 O(1) 索引 get 操作。循环缓冲区行为是使用两个索引来实现的，一个用于队列开头的位置，另一个用于队列末尾的位置。插入和删除只涉及移动一个或另一个索引，而 get(i) 归结为获取 backingArray[(startPos + i) % backingArray.length] 并进行一些错误检查。

如果您需要 FIFO 可扩展，您可以通过将后备数组的大小加倍来实现这一点...并且仍然可以在插入、删除和索引方面获得摊销O(1)。

<小时/>

我认为 Apache Commons CircularFifoQueue类符合您对固定大小 FIFO 情况的要求。它包含一个用于获取第 i 个元素的 get(i) 方法。