特殊类型的队列

Question

我正在寻找类似队列的数据结构，它可以让我将元素放在队列的末尾并从开头弹出，就像常规队列一样。不同之处在于，我还需要不时地压缩队列。假设我有以下项目在我的队列中（包括点号在内的每个字符都是队列中的一个项目）：

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个字符，但有时会增加，因此我们不能假设这是一个固定长度的列表。

- devoured elysium

---

你能详细说明一下“压缩队列”的概念吗？在我看来，你可能需要自己实现一个实现Queue接口的队列（它非常小）。 - Graphics Noob

你不能自己设计一个吗？什么??? - SLaks

点与字母之间是否有特定的对应关系？除了最后一个字母外，您需要在字母前面删除点吗？ - Potatoswatter

嗯...我不知道。但也许可以！你有什么想法？创建静态内部类？ - devoured elysium

我认为你需要维护两个队列（作为链表）。看看我的解决方案。 - Vivin Paliath

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

- Vivin Paliath

---

看到您的最后一条评论，我深入研究了您的建议：实际上，它（几乎）将任务转换为O(1)。虽然遍历队列按定义是O(n)，但您的方法根本不需要遍历队列。唯一需要注意的是，它需要在其中一个列表中保存额外的引用以删除链表中的元素，因为要删除链表中的元素，必须先到达前一个元素。 现在，elysium需要在我的平衡效率+简单性和更高速度与额外内存成本之间进行选择。无论如何，赞一个不需要遍历列表;) - Edurne Pascual

谢谢！是的，需要额外的内存来保存那个额外的引用，这是需要注意的地方。我注意到在处理效率的大多数情况下，你必须在内存和效率之间做出选择。但现在内存很便宜（除非你正在处理异常大的数据集），所以我认为在大多数情况下这种权衡是值得的。 - Vivin Paliath

Answer 2

家庭作业练习/学校项目总是棘手的，会在要求中添加微妙的内容，可能会让人脑袋崩溃。您是否有包括空格作为队列一部分的要求？

个人而言，除非明确要求，否则我不会这样做：似乎更简单的方法是将您的汽车表示为Car、Space对（如果允许使用结构，则可以将对定义为结构），其中Space是表示车辆中下一辆车的空间的数值。然后，要压缩，只需要查看列表项：当您找到一个Space > 0的项时，执行Space--; return;，所有其他车辆都已经“前进”，因为它们与前面的车保持距离。为了输出，请确保在（如果红绿灯在右侧且汽车从左侧来）或之前（红绿灯在左侧且汽车从右侧来）每辆汽车后面抛出Space个点，然后就完成了。还要注意，第一辆车的Space表示到红绿灯本身的距离，因为它前面没有车。

如果在结构中添加指向下一辆车的指针（并为最后一辆车添加空指针），则已经有了一个链接列表：保持指向第一辆车的“全局”变量（或为空队列的情况下为null）。由于Java不直接支持指针，因此将结构转换为类并使用“对象引用”（在除C风格指针算术之外的所有目的上与指针相同），然后就完成了：只需从头开始构建一个类。您唯一需要从Java库中更改的是标准IO和可能的字符串操作，这是由于必须进行输入和输出而导致的固有需求（一些大学具有自己的专门课程IO库，但这在这里没有太大的区别）。要循环遍历队列，您可以执行以下操作（假设类名为“Node”，这是非常通用的，并且对字段使用明显的名称）：

for(Node pos = First; pos != null; pos = pos.Next) {
    /* Do your stuff here, knowing that "pos" points to the "current" item on each iteration. */
}

要添加新节点，您可能需要遍历队列以确定新车辆“生成”与上一个节点的距离；在这样做时，请保留对最后一个节点的引用，并使其“下一个”引用指向新节点：

Node last = First;
int distance = 0;
for(Node pos = First; pos != null; pos=pos.Next) {
    distance += pos.Space;
    last = pos;
}
last.Next = new Node(the_letter_for_this_car, MaxDistance-distance, null);

当然，根据您的实际情况调整构造函数。

考虑到这是一个大学项目，让我们来看看一些细节：紧凑的处理时间变为O(n)，它的内存使用量为O(0)（该过程本身不需要任何“本地”变量，除了可能是遍历集合的指针，它独立于队列的长度）。此外，队列本身的内存使用保证要小于或等于将空间表示为项所需的内存使用（在最坏的情况下，即足够多的汽车被困在红灯处时，它只能等于）。因此，除非要求包括与此方法不兼容的内容，否则我希望这就是您的老师想要的：它是有理有据、高效并符合要求的。

希望这可以帮助您。

- Edurne Pascual

---

我说我只能有一个类，因为在Java世界中，普遍认为每个文件应该只有一个类，而且我只能有一个文件。如果我尝试将几个类放在同一个文件中，Eclipse会开始抱怨。 - devoured elysium

在Java中，每个文件必须有一个_public_类，但是您可以拥有任意数量的私有或嵌套类。此外，您继承自所拥有的类以及引用哪些库类都没有限制。实际上，如果您的代码要接受任何输入和/或生成任何输出，它将不得不直接或间接地引用标准IO类。我建议使用“Program”公共类作为入口点，再加上一个实现链表概念的私有“Node”类。 - Edurne Pascual

啊！原来单个文件中的私有类可以起到很大的作用啊！ - devoured elysium

有趣的方法，但仍然是O(n) :) - Vivin Paliath

这是一个很好的观点。我在离线时考虑了这个问题，你对情境语义提出了一个有效的观点。队列操作被定义为在队列的前面和后面进行，而不是其他地方。我想我的尝试是为了使它在所有情况下都是O(1)，但代价是额外的内存。但我想在90%的情况下，当你试图提高效率时，权衡的是内存。 - Vivin Paliath

Answer 3

我认为链表是这里最好的方法... 因为链表允许您从前面/后面推入/弹出，并允许您在列表中间删除项目。

显然，查找时间很慢，但如果您更经常地从列表的前面/后面添加/删除而不是查找，则建议坚持使用LinkedList。

- Polaris878

Answer 4

或许可以使用第二个LinkedList来保存点元素？

- Kartoch

---

但我需要它们按照那个顺序。如果我有第二个LinkedList，那么我必须有一些东西告诉我原始LinkedList中每个点的位置。这会很混乱。 - devoured elysium