数据结构，有恒定的时间插入，包含，删除和获取索引的元素

Question

我有一个大型的数据集Person列表中排队的对象。我希望数据结构能够有效地执行以下操作。

1. 在队列末尾添加一个Person。
2. 删除第一个Person。
3. 查找是否存在特定的Person，如果存在，请将其删除并将其放在队列末尾。
4. 以其位置获取特定的Person。

对于所有这些操作，是否可能有O（1）次？ 到目前为止，我已经提出了两种方法，但它们并不是最优的。

1. ArrayList<Person> + HashMap<Person, Integer>

   的HashMap存储Person对象的索引。这给出O（n）的时间进行操作2和3（除去元件在ArrayList）

2. ArrayDeque<Person>/LinkedList<Person>

   他们给O代表第一2点的操作（1），但为O（n）的最后二。

在我的情况下，空间复杂度不能大于O（n）。操作4不太密集，所以我可以容忍一个稍微低效的方法来做到这一点。

任何建议，将不胜感激。提前致谢！

Answer 1

我假设条件3的意思是“通过某个键找人”（例如，它的姓氏）？我有一种强烈的感觉，你不能在O（1）中拥有所有这些要求，甚至没有摊销时间（这种事情会是众所周知的）。但是你可以把它们全部放在O（log N）中。你必须从红黑树（C++中的std :: map，我相信这是Java中的SortedMap）的实现开始，并修改节点结构以保持其子树中所有节点的计数。这会给你索引O（log N）的访问权限，以及O（log N）插入和删除树中的任何地方。在O（1）中通过外部散列表（红黑树节点）可以完成某个键的查找。

如果你对O（N）满足要求4，那么我会建议在Java中使用类似LinkedHashMap的东西，它在O（1）中给你需求1到3，而请求。 4可以通过在O（N）中迭代完成。

Answer 2

如果问题还没有被标记java，但c++的std::deque和std::unordered_map会几乎足矣组合。我说几乎是因为第三次请求是相当复杂的，我不知道如何在O(1)与其他三个结合。

std::unordered_map有它在Java中，HashMap相当，但什么std::deque提供和ArrayDeque不，是O(1)随机存取 - >您的申请排名第四。尽管它has already been discussed，这个功能仍然在ArrayDeque中缺失，但我认为手动添加它并不那么困难。毕竟，std::deque只是一个指向固定大小缓冲区的向量。

前两个操作是O(1)在任何体面deque执行。根据第三个请求，HashMap（或std::unordered_map）会告诉您一个特定的Person是否存在于O(1)时间中，并且您可以将它放在最后，具有相同的复杂性。移除是一个问题，因为其他元素必须移位，并且不能通过使用此策略在O(1)中获得。