一个确保元素唯一性的队列？

Question

我正在寻找java.util.Queue的实现或Google集合中表现得像Queue的东西,但也要确保队列中的每个元素都是唯一的.(所有进一步插入都没有效果)

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

现在我正在使用一个带有LinkedList实现的Queue,并在插入之前检查唯一性.(我使用侧面Map来执行此操作,在队列之前/之后添加/删除侧面图中的元素).我不太喜欢它.

欢迎任何输入.如果它不在java.util包中,那么也许这是一个坏主意？

Answer 1

怎么样LinkedHashSet？它的迭代器保留了插入顺序,但因为它是a Set,它的元素是唯一的.

正如其文件所述,

请注意,如果将元素重新插入到集合中,则不会影响插入顺序.

为了有效地从这个"队列"的头部删除元素,请通过它的迭代器:

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

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

Answer 3

我很想维护一个包含一个键的HashSet，该键与它并排唯一地标识队列中的项目。然后只需检查 HashSet 以查看该项目是否在队列中，然后再添加它。当您从队列中删除一个项目时，只需从 HashSet 中删除该键即可。

Answer 4

只是为了完成亚当斯基的回答：

/**
 * A queue that keeps each element only once. 
 * If you try to add an element that already exists - nothing will happen.
 * 
 * @author Adamski http://stackoverflow.com/a/2319156/827927
 * @NotThreadSafe
 */
public class UniqueQueue<T> implements Queue<T> {

private final Queue<T> queue = new LinkedList<T>();
private final Set<T> set = new HashSet<T>();

@Override 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.
}

@Override public boolean addAll(Collection<? extends T> arg0) {
    boolean ret = false;
    for (T t: arg0)
        if (set.add(t)) {
            queue.add(t);
            ret = true;
        }
    return ret;
}

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

@Override public boolean remove(Object arg0) {
    boolean ret = queue.remove(arg0);
    set.remove(arg0);
    return ret;
}

@Override public boolean removeAll(Collection<?> arg0) {
    boolean ret = queue.removeAll(arg0);
    set.removeAll(arg0);
    return ret;
}

@Override public void clear() {
    set.clear();
    queue.clear();
}

@Override public boolean contains(Object arg0) {
    return set.contains(arg0);
}

@Override public boolean containsAll(Collection<?> arg0) {
    return set.containsAll(arg0);
}

@Override public boolean isEmpty() {
    return set.isEmpty();
}

@Override public Iterator<T> iterator() {
    return queue.iterator();
}

@Override public boolean retainAll(Collection<?> arg0) {
    throw new UnsupportedOperationException();
}

@Override public int size() {
    return queue.size();
}

@Override public Object[] toArray() {
    return queue.toArray();
}

@Override public <T> T[] toArray(T[] arg0) {
    return queue.toArray(arg0);
}

@Override public T element() {
    return queue.element();
}

@Override public boolean offer(T e) {
    return queue.offer(e);
}

@Override public T peek() {
    return queue.peek();
}

@Override public T poll() {
    return queue.poll();
}
}