具有跳过元素功能的阻塞FIFO队列？

Question

简短概述：如何在Java中最好地实现阻塞FIFO队列，并具备暂时跳过或跳过队列中不符合特定条件的项的功能，如果它们被弹出队列时不符合某些标准？ 详细描述：

我在应用程序中使用ArrayBlockingQueue已经很多年了，对于我的目的来说运行良好。 到目前为止，我只需要调用put()和take()。 这已经足够了。

现在有一个要求，即在通过take()检索元素时，必须满足某些条件。 如果不符合条件，则应将其放回队列，但在先前所在的相同位置。

想象一下在国际机场海关的一条线上。由于某种原因，乘客仅在上车时获得海关申报表。乘客正在疯狂地涂鸦以在轮到他们之前完成表格。 有一个安保人员站在排队的最前面。当海关官员准备就绪迎接下一个乘客时，安保人员会检查排在最前面的第一个乘客是否已填写完海关申报单。 如果是这样，他会将该乘客发送到海关官员那里。 如果没有，他会依次检查第二个乘客，第三个乘客等，直到找到已完成填写的人。他会将该人员发送到海关官员。 每当海关官员空闲时，总是从排在最前面的第一个乘客开始。

在研究中，我唯一想到的是使用双端队列（deque），从队列的前面取出元素，直到找到符合条件的元素。 然后以我取出元素的相反顺序将元素放回到前面。

有没有什么建议？

- John Fitzpatrick

Answer 1

根据你是否能够监听项目状态变化，有两种可能的建议：

• 如果项目可以在准备就绪时通知您，则只需在其到达时对其进行编号，并将其移动到PriorityQueue中。然后，只需从PriorityQueue中取出第一个项目，在空闲时阻塞它。

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

第二种情况不仅较慢，而且处理未准备好的项目的完整队列也更差；要么您在重新启动之前（在阻塞期间）暂停一段时间，要么您的阻塞行为相当于繁忙等待，因为它反复循环遍历项目。

（如果我被迫实现第二种方法，我会倾向于尝试动态调整等待重新启动时间，基于等待准备完成的总累计时间和下一次开始遍历列表时至少完成一个的预期概率。）

- DavidW

Answer 2

让你的数据结构创建第二个队列。在弹出时在整个结构上获取写锁。暂时忽略主要队列，首先检查次要队列。如果它为空，请转到主队列。从主队列中弹出一个元素。如果准备好了，请取出并释放锁。如果不是，请将其放入辅助队列中，然后再取一个。重复此过程直到准备就绪。

如果第二个队列在您第一次尝试抓取它时不为空，请循环遍历第二个队列以查看其中是否有任何已准备就绪的元素。

这样做的好处是您总是可以立即获得已准备好的元素。除非当然您耗尽了主队列，但那时没有人准备好，所以您也无能为力。

这样做的缺点是，如果您有一些超级慢的人，则次要队列可能会成为问题。您可以通过提供剩余时间的估计等方式解决此问题。此外，恶意用户始终可能说谎或以其他方式拖延您的时间。但是，如果您没有预先防范恶意用户的方法，您在多线程方面肯定会遇到麻烦。

以下是算法的非线程安全版本-这只是我脑海中的想法，因此请谨慎对待。

class SnappyQueue<E> {
    Queue<E> main = ... // people waiting in line
    Queue<E> slugs = ... // people at the front but still writing
    void push(E e) { main.addLast(e); }
    E pop() {
        E first = slugs.peek();
        if(first != null) {
            for(E cur = slugs.pop(); cur != first; cur = slugs.pop()) {
                if(cur.isReady()) return cur; // we're done, one of the slugs is ready
                slugs.push(cur); // this slug isn't ready, put it back
            }
        }
        while(true) {
            E cur = main.pop();
            if(cur == null) return null; // nothing left
            if(cur.isReady()) return cur; // we found someone ready
            slugs.push(cur); // not ready, push them into the slug line
        }
    }
}

- corsiKa

---

通过将项目弹出并推送到第二个队列（您确定在谈论队列吗？），您会破坏顺序。考虑您已将3个项目移动到辅助队列[1、2、3]。在poll()上检查1；如果它没有准备好，您就会offer()它。现在您的队列是[2、3、1]。下一个poll()返回2，它已准备好，因此您将其返回。下一次迭代，您有队列[3、1]。如果它们都准备好，您将返回错误的那个。 - DavidW

@DavidW 我没有搞乱顺序。物品本身因为在队列末尾时还没有准备好而导致顺序混乱。此时一切都不确定了。 - corsiKa