3

キュー タイプのラッパーを作成していますが、要素を追加するたびに、内部のすべてを並べ替えたいと考えています。ほとんどの場合、 Integerになります。コレクションフレームワークにあまり詳しくありません。簡単な解決策はありますか?

public class Round<Type> {

    private Queue<Type> qe;

    public Round(){
        this.qe = new LinkedList<Type>();
    }


    public void push(Type p){
        this.qe.offer(p);
        //Collections.sort(this.qe); Here I want to sort this
    }


    public Type pop(){
        return this.qe.poll();
    }
}
4

3 に答える 3

10

それがあなたが望むものだと確信していますか？

要素を追加するたびにすべてを並べ替えるのは賢明ではないようです。

おそらく、実際にはPriorityQueueが必要ですか?

要素を追加するたびに全体を並べ替えると、O(n.log(n))挿入時に複雑にならないように実装に細心の注意を払う必要があります...これは非常に悪いことです。

Queue をサポートするために使用される実際のデータ構造によっては、これよりもうまくいく可能性がありますが、基本的な実装に依存しているため、お勧めしません。

プライオリティ キューを使用すると、時間内にキューイングとデキューを行うことができますO(log(n))。これは、ランダムな挿入で順番に維持する必要がある構造にとって非常に効率的です。

于 2013-01-18T11:11:31.723 に答える
9

独自の Comparator インターフェイスを実装し、PriorityQueue を使用する必要があります。

要素を追加するたびに、キューは常にソートされます。

何かのようなもの ：

private Queue<Type> qe = new PriorityQueue<Type>(20, new MyComparator<Type>())
于 2013-01-18T11:19:19.120 に答える
5

キューはソートされているとは想定されていません。LinkedList または ArrayList を使用することをお勧めします。次に、並べ替えの後、前からデキューし、後ろでエンキューすることにより、キューのような動作をシミュレートできます。

または、コンポジションを利用して、リストを基になる構造として使用し、ソート動作を追加するだけの SortableQueue を作成することもできます。

ただし、むしろ PriorityQueue を利用したいようです。プライオリティ キューは、ある順序に基づいて内容を並べ替え、キューをその順序に保ちます。また、サポートするデータ構造としてヒープを使用するため、リストを使用して毎回ソートするよりもはるかに高速です。

何かのようなもの：

PriorityQueue<Integer> q = new PriorityQueue<Integer>();
q.add(6);
q.add(2);
q.add(9);

上記をデキューすると、2 6 9 になります。それがあなたの望みだと思います。独自の Comparator を追加して、特定の方法でオブジェクトをソートすることもできます。

于 2013-01-18T11:16:57.737 に答える