Java: Sorting a queue

Question

I'm making a wrapper to queue type, but each time I add element, I want to sort everything inside. Mostly it will be Integer. I'm not too familiar with Collections framework, is there any simple solution ?

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

Solution 1

Are you sure that is what you want?

Sorting everything every time you add an element doesn't seem wise.

Perhaps you actually want a PriorityQueue?

If every time you add an element, you re-order the whole thing, you'll have to be extremely careful with the implementation not to end up with O(n.log(n)) complexity on insert... which is very very bad.

Depending on the actual data structure used to support the Queue you can do better than this, but it's relying on an underlying implementation, which I wouldn't advise.

A priority queue allows for queing and dequeing in O(log(n)) time, which is quite efficient for a structure you have to maintain in order with random inserts.

Solution 2

A queue is not suppose to be sorted. I would recommend you rather use a LinkedList or an ArrayList. Then, after sorting, you can simulate queue-like behaviour by dequeueing from the front and enqueuing at the back.

Alternatively, you can make use of composition and create a SortableQueue where you use a List as the underlying structure and then simply add sorting behaviour.

However, it rather seems that you want to make use of a PriorityQueue. A priority queue sorts its contents based on some ordering and keeps the queue in a that order. It is also MUCH faster than using a list and sorting it each time as it uses a heap as its supporting data structure.

Something like:

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

Dequeing the above will result in 2 6 9. I think that is what you want. You can also add your own Comparator to sort your objects in a particular way.