Java:对队列进行排序

Question

我正在为队列类型创建一个包装器,但每次添加元素时,我都要对内部的所有内容进行排序.大多数情况下它将是整数.我对Collections框架不太熟悉,有什么简单的解决方案吗？

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

Answer 1

你确定这是你想要的吗？

每次添加元素时对所有内容进行排序似乎并不明智.

也许你真的想要一个PriorityQueue？

如果每次添加一个元素,你重新整理整个东西,你必须非常小心的实现,最终不会导致O(n.log(n))插入的复杂性......这是非常非常糟糕的.

根据用于支持Queue的实际数据结构,您可以做得比这更好,但它依赖于底层实现,我不建议这样做.

优先级队列允许及时排队和出列O(log(n)),这对于您必须按随机插入顺序维护的结构非常有效.

Answer 2

您应该实现自己的Comparator接口并使用PriorityQueue.

每次添加元素时,队列都会保持排序状态.

就像是 :

private Queue<Type> qe = new PriorityQueue<Type>(20, new MyComparator<Type>())

Answer 3

队列不应该被排序。我建议您宁愿使用 LinkedList 或 ArrayList。然后，在排序之后，您可以通过从前面出队并在后面入队来模拟类似队列的行为。

或者，您可以使用组合并创建一个 SortableQueue，您可以在其中使用 List 作为底层结构，然后简单地添加排序行为。

但是，您似乎更想使用 PriorityQueue。优先级队列根据某种顺序对其内容进行排序，并将队列保持在该顺序中。它也比使用列表和每次排序都要快得多，因为它使用堆作为其支持数据结构。

就像是：

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

Dequeing 以上将导致 2 6 9. 我认为这就是你想要的。您还可以添加自己的 Comparator 以特定方式对对象进行排序。