阻塞 FIFO 队列并能够跳过元素？

Question

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

长版：

我已经在应用程序中使用 ArrayBlockingQueue 多年了，它对于我的目的来说工作得很好。到目前为止我只需要调用 put() 和 take() 。效果很好。

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

想象一下国际机场海关排队的情况。由于某种原因，乘客在登机时只收到了海关申报表。乘客们都在拼命地写字，以便在轮到他们之前完成表格。队伍前面有一名保安。当海关官员准备好接待下一位乘客时，保安人员会检查队伍中的第一位乘客是否填写了海关申报单。如果是这样，他会将乘客送往海关官员。如果没有，他会检查第二名乘客，然后是第三名，依此类推，直到找到完成检查的人。他将该人送往海关官员。每次海关官员有空时都会发生同样的情况，总是先让线路上的第一位乘客开始。

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

有人有推荐吗？

Answer 1

让您的结构创建第二个队列。弹出时获取整个结构的写锁。暂时忽略主队列，先检查辅助队列。如果为空，则进入主队列。从主队列中弹出一个元素。如果准备好了，拿走它并释放锁。如果不是，则将其放入辅助队列中，然后再获取另一个。重复直到你准备好。

如果当您第一次尝试抓取辅助队列时辅助队列不为空，请循环遍历辅助队列以查看是否有任何一个已准备好。

这样做的优点是你总是能找到现在就准备好的人。当然，除非你耗尽了主队列，但是没有人准备好，所以你在那里无能为力。

这样做的缺点是，如果你有一些超级慢的人，辅助队列可能会成为问题。您可以通过提供剩余时间的估计或其他内容来解决此问题。此外，坏人总是有可能撒谎或以其他方式束缚您。但如果你没有办法抢占坏人，那么无论如何你都会在多线程方面遇到麻烦。

这是该算法的非线程安全版本 - 它只是我的想法，所以请持保留态度。

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
        }
    }
}