java - 特殊队列

Question

我正在寻找类似于 Queue 的东西，它允许我将元素放在队列的末尾并在开头弹出它们，就像常规 Queue 所做的那样。

不同之处在于我还需要不时地压缩队列。也就是说，假设我的队列中有以下项目(每个字符，包括点，都是队列中的一个项目):

e d . c . b . a
(this Queue has 8 items)

然后，例如，我需要删除最后一个点，以便得到:

e d . c . b a

Java Collection 类中有类似的东西吗？我需要将它用于我正在执行的程序，在该程序中我只能使用 Java 的类。我不允许自己设计一个。目前我只是在使用 LinkedList，但我认为这可能更像是一个队列而不是 LinkedList。

谢谢

编辑:

基本上，这是该项目的内容: 交通灯可以是绿色(相关符号是“-”)或红色(“|”)。红绿灯在右边: alt text http://img684.imageshack.us/img684/9602/0xfhiliidyxdy43q5mageu0.png 一开始，你没有车，交通灯是绿色的，所以我们的列表表示为:

.......  -

现在，在下一次迭代中，我有一个随机变量可以告诉我哪里有汽车驶来。如果有汽车驶来，那么我们可以看到它从左侧出现。在每次迭代中，所有汽车都向右移动一步。如果他们的右边有任何汽车，那么他们就不能移动:

a......  -   (iteration 1)
.a.....  -   (iteration 2)
..a....  -   (iteration 3)

等等

现在，有时交通灯会变成红色('-')。在那种情况下，如果你有几辆车，那么即使它们在移动时之间有一定距离，当它们必须停下来等红绿灯时它们也会靠得很近:

...b.a.  -   (iteration n)
....b.a  -   (iteration n+1)
.....ba  -   (iteration n+2) here they got close to each other

现在，这就是为什么它像队列一样工作的原因，但有时当汽车靠近红色交通灯时，我必须记下这些点。 另请记住，此处街道的大小为 7 个字符，但有时会增加，因此我们不能假设这是一个固定长度的列表。

Answer 1

队列基本上是具有定义行为的项目列表，在本例中为 FIFO(先进先出)。您在末尾添加项目，并从开头删除它们。

现在队列可以以您选择的任何方式实现；使用链表或数组。我认为你在正确的道路上。链表肯定会使它更容易。

添加和删除队列的时间复杂度为 O(1)(如果您保持对前端和后端的引用)，但压缩(删除点)的最坏情况是 O (n).

我相信如果您使用辅助数据结构，可能有一种方法可以将 compact 操作减少到 O(1)(如果您一次只删除一个点)。您需要的是另一个队列(使用另一个链表实现)，它维护对第一个链表中的点的引用。

因此，当您插入 (a, ., b, c, ., d) 时，您会得到一个如下所示的列表:

[pointer to rear] -> [d] -> [.] -> [c] -> [b] -> [.] -> [a] <- [pointer to front]

并且您还有一个辅助队列(作为链表实现)维护对点的引用:

[pointer to rear] -> [reference to second dot] -> [reference to first dot] <- [pointer to front]

然后，当您需要执行compact 操作时，您所要做的就是从第二个队列中移除第一个元素并保留引用。所以你现在有一个对第一个链表中间的点的引用。您现在可以轻松地从第一个列表中删除该点。

您在评论中提到您需要跟踪订单。根据定义，队列是一种有序结构(从某种意义上说，事物保持它们被插入的顺序)。因此，您需要做的就是在将点插入第一个队列时将对点的引用插入第二个队列。这样，秩序得以维持。因此，当您从第二个队列中提取对点的引用时，您将获得对第一个队列中实际和对应点的引用。

这里的速度权衡是您需要更多内存，因为您要维护第二个引用列表。最坏情况下的内存需求是您现在使用的内存的 2 倍。但这是获得 O(1) 与 O(n) 的一个不错的权衡。