72

キューのように動作するが、キューの各要素が一意であることを確認するjava.util.QueueまたはGoogleコレクション内の何かの実装を探しています。（それ以上挿入しても効果はありません）

それは可能ですか、それとも私は手でそれをしなければなりませんか？

今のところ、LinkedList実装のキューを使用しており、挿入する前に一意性を確認します。（これを行うためにサイドマップを使用します。キューの前後にサイドマップから要素を追加/削除します）。あまり好きではありません。

どんな入力でも大歓迎です。java.utilパッケージに含まれていない場合は、それは悪い考えですか？

4

8 に答える 8

56

どうLinkedHashSetですか？そのイテレータは挿入順序を保持しますが、それはであるためSet、その要素は一意です。

そのドキュメントが言うように、

要素がセットに再挿入されても、挿入順序は影響を受けないことに注意してください。

この「キュー」の先頭から要素を効率的に削除するには、そのイテレータを実行します。

Iterator<?> i = queue.iterator();
...
Object next = i.next();
i.remove();
于 2010-02-23T15:05:44.860 に答える
25

これは私が知る限り存在しませんが、 ：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.
}
于 2010-02-23T15:08:31.307 に答える
5

キュー内のアイテムを並べて一意に識別するキーを含むHashSetを維持したいと思います。次に、HashSetをチェックして、アイテムを追加する前にアイテムがキューにあるかどうかを確認します。キューからアイテムを削除するときは、HashSetからもキーを削除するだけです。

于 2010-02-23T15:05:11.550 に答える
5

アダムスキの答えを完成させるためだけに：

/**
 * 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();
}
}
于 2013-03-05T10:24:03.903 に答える
4

もちろん、一意性をチェックすることにはコストがかかります（空間または時間のいずれかで）。要素のコンパレータによってソートされたヒープを維持するPriorityQueueのようなものから作業するのは興味深いようです。これを利用して、サイドマップを維持せずに存在をより効率的に（O（log n））チェックできる場合があります。

キューを一意性チェッカーでラップしたい場合は、GoogleコレクションのForwardingQueueを使用してそのようなものを構築することを強くお勧めします。

于 2010-02-23T15:12:28.590 に答える
2

残念ながらそれは存在しません。そのようなキューが必要だったので、 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>
于 2016-11-09T20:33:35.003 に答える
2

答えるのが少し遅れましたが、ArrayDequeを使用して同様の問題を解決し、必要なaddメソッドをオーバーライドすることになりました。

    Deque<Long> myQueue = new ArrayDeque<Long>() {
        @Override
        public boolean add(Long e) { return !this.contains(e) && super.add(e);}
    };
于 2019-06-22T11:02:49.160 に答える
0

これはとても良い質問です。既存の簡単な解決策はありません。しばらく前に書いた、これを行おうとしたコードを掘り下げて、戻ってきてこの答えを編集します。

編集：私は戻ってきました。確かに、並行性が必要ない場合は、キューとセットを別々に維持することをお勧めします。私がやっていたことでは、並行性が目標でしたが、その制約を考えると、私が思いつくことができる最善の解決策には問題がありました。基本的に、ConcurrentHashMapを使用しているため、キューから「head」要素を削除するほど（キューで行う基本的なこと）、時間の経過とともにハッシュテーブルのバランスが崩れます。私はまだこのコードをあなたと共有することができますが、あなたが本当にそれを望んでいるとは思えません。

編集：並行性が必要な場合、私はこの答えを出しました： 並行セットキュー

于 2010-02-23T15:54:29.327 に答える