时间戳

首页 > 解决方案 > 阻止具有跳过元素的能力的 FIFO 队列？

java - 阻止具有跳过元素的能力的 FIFO 队列？

问题描述

简短版本： 如何在 Java 中最好地实现阻塞 FIFO 队列，如果它们在从队列中弹出时不满足某些条件，则能够暂时跳过或跳过队列中的项目？

长版：

多年来，我一直在应用程序中使用 ArrayBlockingQueue，它对我的​​目的运行良好。到目前为止，我只需要调用 put() 和 take()。它运行良好。

现在需要一个元素在通过 take() 检索时满足某些条件。如果它不符合标准，它应该回到队列中，但在与之前相同的位置。

想象一下国际机场海关的一条线。出于某种原因，乘客在上线时只收到了报关单。乘客们都在疯狂地涂鸦，以在轮到他们之前完成他们的表格。队伍前面有一名保安。当海关官员准备好迎接下一位乘客时，保安检查线路上的第一位乘客是否填写了海关申报单。如果是这样，他会将乘客送到海关官员那里。如果不是，他检查第二个乘客，然后检查第三个，等等，直到他找到完成的人。他把那个人送到海关官员那里。每次海关官员有空时都会发生同样的情况，总是从线路上的第一位乘客出发。

在研究中，我想到的唯一方法是使用双端队列（deque）并将元素从前面取出，直到找到符合标准的元素。然后按照我取下它们的相反顺序将元素放回前面。

有人有推荐吗？

标签： javaqueue

解决方案

2 个可能的建议取决于您是否能够监听项目的状态变化：

  • 如果项目可以在准备好时通知您，那么只需在它们到达时对其进行编号，并在它们准备好后立即将它们移动到PriorityQueue中。然后只需从 PriorityQueue 中拉出第一项，如果它为空则阻塞。

  • 如果您必须检查每个项目以确定其状态是否已更改，那么您别无选择，只能依次访问每个项目，从最旧的开始，直到找到准备好的项目。在这种情况下，您真的不需要 Queue 作为底层数据结构；LinkedList 实际上更合适。

第二种情况不仅速度较慢，而且处理未就绪的完整队列也更糟；要么您在重新启动之前在列表末尾暂停一段时间（同时阻塞），要么您的阻塞行为等同于忙等待，因为它反复循环遍历项目。

（如果我坚持实施第二个，我倾向于尝试根据等待准备就绪的累积时间总量和至少一个完成的预期概率来动态调整重新启动前的等待时间下次我开始遍历列表时。）

推荐阅读