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

Question

精简版:我怎样才能最好地在 Java 中实现一个阻塞 FIFO 队列，如果队列中的项目在它们不符合特定条件时能够暂时跳过或跳过它们从队列中弹出？

长版:

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

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

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

在研究过程中，我想到的唯一一件事就是使用双端队列 (deque) 并从前面取出元素，直到找到符合条件的元素。然后按照我取下它们的相反顺序将元件放回前面。

有人推荐吗？

Answer 1

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

• 如果元素可以在准备就绪时通知您，那么只需在它们到达时给它们编号，然后将它们移到 PriorityQueue 中。一旦他们准备好了。然后只从 PriorityQueue 中拉出第一个项目，如果它为空则阻塞。

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

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

(如果我坚持实现第二个，我会倾向于根据等待就绪的累积时间总量和至少一个的预期概率来动态调整重启前等待时间下次我开始走 list 时完成。)