重複する要素を許可しないキューを作成したいのですが、インデックスに基づいてこのキューの要素にアクセスできる必要があります。これをどのように実装すればよいか教えてください。
4 に答える
Javaには、仕様や要件に一致する正確なデータ構造がないことは明らかです。要件に一致する可能性のある最も近いものは、おそらくLinkedHashSetです。これは基本的に(キューのように)要素が挿入順序で保持されるセット(一意のアイテムの要件に一致)であり、インデックスによって要素をset.toArray()
取得するには、配列を取得したり、セットからリストを作成したりするために使用できます(ただし、追加のメモリが必要になります)。
問題にConcurrentLinkedQueueを使用することを計画しています。これがサンプルコードです
import java.util.concurrent.ConcurrentLinkedQueue;
public class FinalQueue {
private ConcurrentLinkedQueue<String> queue;
public FinalQueue()
{
queue = new ConcurrentLinkedQueue<String>();
}
public synchronized void enqueue(String ipAddress)
{
if(!queue.contains(ipAddress))
queue.add(ipAddress);
}
public String dequeue()
{
return queue.poll();
}
public String toString()
{
return "" + queue;
}
/**
* @param args
*/
public static void main(String[] args) {
FinalQueue queue = new FinalQueue();
queue.enqueue("1.2.3.4");
queue.enqueue("2.3.4.5");
queue.enqueue("1.1.1.1");
queue.enqueue("1.2.3.4");
System.out.println(queue.toString());
System.out.println("Dequeue..." + queue.dequeue());
System.out.println("Dequeue..." + queue.dequeue());
System.out.println(queue.toString());
}
}
いつでもArrayListを使用できます。インデックスに基づいて要素にアクセスするのに適しています。要素を追加するときは、ArrayListに追加する要素が含まれているかどうかをいつでも確認できます。私の最初の本能は、重複を禁止するためにセットを使用することでしたが、要素はセットにインデックスが付けられていません。セット内の要素にインデックスを付ける方法を見つけることができれば、それが私の推奨事項です。
定義上、キューは先入れ先出しのデータ構造であるため、これをキューとは呼ばないでください。
入力値にもよりますが、配列とハッシュ関数を使用する必要があると思います。ハッシュは、その値を使用して要素が配置されているインデックスを決定します。その逆も同様です。つまり、インデックスが指定されると、要素に含まれる値が返されます。
ハッシュを使用しているため、衝突が発生したときに繰り返しが回避されます。つまり、値が以前にインデックスに存在していたかどうか、および同じ値であるかどうかを確認できます。
C ++ stlにはsetに適したクラスがありますが、javaにはクラスがないと思います。ただし、ポイントが設定されているため、インデックスベースの取得は提供されません。