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))插入时变得复杂......这是非常非常糟糕的。

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

优先级队列允许及时排队和出队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，在其中使用 List 作为基础结构，然后简单地添加排序行为。

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

就像是：

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

对上述内容进行出队将导致 2 6 9。我认为这就是您想要的。您还可以添加自己的比较器以特定方式对对象进行排序。

于 2013-01-18T11:16:57.737 回答