保证元素唯一性的队列？

Question

我正在寻找 java.util.Queue 的实现或 Google 集合中的某些东西，它们的行为类似于队列，但也确保队列的每个元素都是唯一的。（所有进一步的插入将不起作用）

有可能吗，还是我必须手动完成？

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

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

Answer 1

LinkedHashSet

怎么样？它的迭代器保留插入顺序，但因为它是一个

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

只是为了完成 Adamski 的答案：

/**
 * 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();
}
}

Answer 5

检查唯一性当然是有成本的（空间或时间）。看起来使用像 PriorityQueue 这样的东西可能会很有趣，它将维护一个按元素比较器排序的堆。您也许可以利用它来更有效地 (O(log n)) 检查存在性，而无需维护侧图。

如果您确实想用唯一性检查器包装队列，我强烈建议使用 Google Collections ForwardingQueue 来构建这样的东西。

Answer 6

不幸的是它不存在。由于我需要这样的队列，我开发了一个由一组支持的阻塞队列，灵感来自于java.util.concurrent.LinkedBlockingQueue。

你可以在这里找到它：

https://github.com/bvanalderweireldt/concurrent-unique-queue

示例：

final BlockingQueue<Integer> queue = new ConcurrentSetBlockingQueue<>(1);
queue.offer(new Integer(1)); //True
queue.offer(new Integer(1)); //False

您可以将它与 Maven 一起使用:

<dependency>
  <groupId>com.hybhub</groupId>
  <artifactId>concurrent-util</artifactId>
  <version>0.1</version>
</dependency>

Answer 7

我回答有点晚了，但我最终使用 ArrayDeque 解决了类似的问题并覆盖了我需要的 add 方法。

    Deque<Long> myQueue = new ArrayDeque<Long>() {
        @Override
        public boolean add(Long e) { return !this.contains(e) && super.add(e);}
    };

Answer 8

这是一个非常好的问题。目前还没有直接的解决方案。我将挖掘我不久前编写的一些尝试执行此操作的代码，然后回来编辑此答案。

编辑：我回来了。确实，如果不需要并发性，最好分别维护 Queue 和 Set。对于我正在做的事情，并发是一个目标，但鉴于该约束是有问题的，我能想出的最佳解决方案是：基本上，由于它使用 ConcurrentHashMap，从队列中删除“头”元素越多（队列的基本操作），随着时间的推移，哈希表就会变得越不平衡。我仍然可以与您分享此代码，但我怀疑您是否真的想要它。

编辑：对于需要并发的情况，我给出了这个答案：并发设置队列

Answer 9

您可以在初始化队列变量时重写 add 方法。

Queue<T> queue = new PriorityQueue<>() {
  @Override
  public boolean add(T t) {
    return !this.contains(t) && super.add(t);
  }
};

...或者您可以实现 Queue 接口。

Answer 10

我用了

LinkedHashSet

：

public class UniqueQueue<T> {

    private final LinkedHashSet<T> queue;

    public UniqueQueue() {
        queue = new LinkedHashSet<>();
    }

    public void enqueue(T item) {
        synchronized (UniqueQueue.class) {
            queue.add(item);
        }
    }

    public T dequeue() {
        synchronized (UniqueQueue.class) {
            Iterator<T> i = queue.iterator();

            T next = i.next();
            i.remove();

            return next;
        }
    }
}

保证元素唯一性的队列？

问题描述投票：0回答：10

10个回答

最新问题

保证元素唯一性的队列？

问题描述 投票：0回答：10

10个回答

最新问题

问题描述投票：0回答：10