确保元素唯一性的队列？

Question

我正在寻找 java.util.Queue 的实现或 Google 集合中行为类似于队列的东西，但还要确保队列的每个元素都是唯一的。 （所有进一步的插入都将无效）

这是可能的，还是我必须手工完成？

现在我正在使用一个带有 LinkedList 实现的队列，并且我在插入之前检查唯一性。 （我使用侧地图来执行此操作，在队列之前/之后从侧地图添加/删除元素）。我不太喜欢它。

欢迎任何意见。如果它不在 java.util 包中，那么这可能是个坏主意？

原文由 Antoine Claval 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

怎么样 LinkedHashSet ？它的迭代器保留插入顺序，但因为它是 Set ，所以它的元素是唯一的。

正如其文档所说，

请注意，如果将元素 重新插入 到集合中，插入顺序 不会 受到影响。

为了有效地从这个“队列”的头部移除元素，通过它的迭代器：

 Iterator<?> i = queue.iterator();
...
Object next = i.next();
i.remove();

原文由 erickson 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

据我所知，这并不存在，但使用 LinkedList 结合 Set 来实现相当简单：

 /**
 * Thread unsafe implementation of UniqueQueue.
 */
public class UniqueQueue<T> implements Queue<T> {
  private final Queue<T> queue = new LinkedList<T>();
  private final Set<T> set = new HashSet<T>();

  public boolean add(T t) {
    // Only add element to queue if the set does not contain the specified element.
    if (set.add(t)) {
      queue.add(t);
    }

    return true; // Must always return true as per API def.
  }

  public T remove() throws NoSuchElementException {
    T ret = queue.remove();
    set.remove(ret);
    return ret;
  }

  // TODO: Implement other Queue methods.
}

原文由 Adamski 发布，翻译遵循 CC BY-SA 2.5 许可协议