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

pcalcao · Accepted Answer · 2013-01-18 11:11:31Z

11

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.

answered Jan 18, 2013 at 11:11

pcalcao

16k1 gold badge49 silver badges65 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Adam Dyga Over a year ago

Exactly. Or insert manually at proper position according to sort order

pcalcao Over a year ago

Yes, I advise a bit against that because it depends on the underlying data structure, and it can change without notice.

ashur Over a year ago

Thank you, I completely forgot about PriorityQueue. This is what I need exactly.

user734613 · Accepted Answer · 2013-01-18 11:19:19Z

9

You should implement your own Comparator interface and use a PriorityQueue.

Everytime you add an element, your queue keeps sorted.

Something like :

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

answered Jan 18, 2013 at 11:19

user734613

Comments

Jaco Van Niekerk · Accepted Answer · 2013-01-18 11:22:54Z

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.

Collectives™ on Stack Overflow

Java: Sorting a queue

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related