PriorityQueue and PriorityBlockingQueue

Question

which one should I choose over another among these programs and why? Generally the question is why should I choose to use PriorityBlockingQueue over PriorityQueue.

PriorityBlockingQueue

import java.util.concurrent.PriorityBlockingQueue;

public class PriorityBlockingQueueExample {

    static PriorityBlockingQueue<String> priorityQueue = new PriorityBlockingQueue<String>();
    public static void main(String[] args) {

        new Thread(){
            public void run(){
                try {
                System.out.println(priorityQueue.take() +" is removed from priorityQueue object");
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }    
            }
        }.start();
        new Thread(){
            public void run(){
                priorityQueue.add("string variable");
                System.out.println("Added an element to the queue");
            }
        }.start();
    }
}

which one should I choose over another among these programs and why? Generally the question is why should I choose to use PriorityBlockingQueue over PriorityQueue. PriorityQueue

import java.util.PriorityQueue;

public class PriorityQueueTest {

    static PriorityQueue<String> priorityQueue = new PriorityQueue<String>();
    private static Object lock = new Object();
    public static void main(String[] args) {

        new Thread(){
            public void run(){
                synchronized(lock){     
                    try {
                        while(priorityQueue.isEmpty()){lock.wait();}
                            System.out.println(priorityQueue.remove() +" is removed from priorityQueue object");
                            lock.notify();
                    } catch (InterruptedException e) {
                            //  TODO Auto-generated catch block
                            e.printStackTrace();
                    }
                }
            }
        }.start();
        new Thread(){
            public void run(){
                synchronized(lock){
                    priorityQueue.add("string variable");
                    System.out.println("Added an element to the queue");
                    lock.notify();
                }
            }
        }.start();
    }
}

Answer 1

I know that this is an old topic but I saw that you didnt consider a concurrent implementation of a priority queue.

Although java's collections framework does not have one, it does have enough building blocks to create one:

public class ConcurrentSkipListPriorityQueue<T> implements Queue<T> {

    private ConcurrentSkipListMap<T, Boolean> values;

    public ConcurrentSkipListPriorityQueue(Comparator<? super T> comparator) {
        values = new ConcurrentSkipListMap<>(comparator);
    }

    public ConcurrentSkipListPriorityQueue() {
        values = new ConcurrentSkipListMap<>();
    }

    @Override
    public boolean add(T e) {
        values.put(e, Boolean.TRUE);
        return true;
    }

    @Override
    public boolean offer(T e) {
        return add(e);
    }

    @Override
    public T remove() {
        while (true) {
            final T v = values.firstKey();
            if (values.remove(v)) {
                return v;
            }
        }
    }

    @Override
    public T poll() {

        try {
            while (true) {
                if (values.isEmpty()) {
                    return null;
                }
                final T v = values.firstKey();
                if (values.remove(v)) {
                    return v;
                }
            }
        } catch (NoSuchElementException ex) {
            return null; // poll should not throw an exception.. 
        }
    }

    @Override
    public T element() {
        return values.firstKey();
    }

    @Override
    public T peek() {
        if (values.isEmpty()) {
            return null;
        }

        try {
            return element();
        } catch (NoSuchElementException ex) {
            return null;
        }
    }

    @Override
    public int size() {
        return values.size();
    }

    @Override
    public boolean isEmpty() {
        return values.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        return values.containsKey(o);
    }

    @Override
    public Iterator<T> iterator() {
        return values.keySet().iterator();
    }

    @Override
    public Object[] toArray() {
        return values.keySet().toArray();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return values.keySet().toArray(a);
    }

    @Override
    public boolean remove(Object o) {
        return values.remove(o);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return values.keySet().containsAll(c);
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {

        boolean changed = false;

        for (T i : c) {
            changed |= add(i);
        }

        return changed;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return values.keySet().removeAll(c);
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return values.keySet().retainAll(c);
    }

    @Override
    public void clear() {
        values.clear();
    }

}

This queue is based on skip list by delegating all of its operations to the ConcurrentSkipListMap class. It allows non-blocking concurrent access from multiple threads.

Answer 2

A normal Queue will return null when accessed if it is empty, while a BlockingQueue blocks if the queue is empty until a value is available.

The priority part in the queues you are using simply means the items are read from the queue in a specific order (either natural if they implement Comparable or according to a Comparator).

Typically you could should depend on the abstract type, either PriorityQueue or BlockingQueue. If your code requires knowledge of both these concepts a re-think may be needed.

There's numerous reasons why you might need a PriorityQueue that boil down to message ordering. For example on a queue of jobs, you might want to be able to give those jobs priority. That said typically the code processing the jobs should be agnostic to the order.

With a BlockingQueue you're typically in the realm of worker threads picking up queued work and when there's no work to do, those threads can be blocked until work becomes available. Like the example of a PriorityQueue, the calling code could be agnostic to this, though as you may want to use some sort of wait timeout that's not always case.

Answer 3

PriorityBlockingQueue was added with the concurrent package in JDK 5 see: http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/package-summary.html

It's basically under the hood doing the extra code you wrote for PriorityQueue of adding the commonly necessary synchronize/wait/notify around your queue. Thus the "Blocking" part of the name is added to imply the thread will block waiting until there's an item available on the queue.

If your app can run on JDK 5 or newer, I'd use PriorityBlockingQueue.