优先队列和优先阻塞队列

Question

在这些程序中，我应该选择哪一个，并且为什么？一般而言，问题是为什么我应该选择使用PriorityBlockingQueue而不是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();
    }
}

在这些程序中，我应该选择哪一个并解释原因？一般而言，问题是为什么我应该选择使用PriorityBlockingQueue而不是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();
    }
}

- LeandreM

Answer 1

普通的Queue在为空时会返回null，而BlockingQueue会在队列为空时阻塞直到有值可用。

你使用的队列中优先级部分指的是按照特定顺序读取队列中的项（如果它们实现了Comparable则为自然顺序，否则根据Comparator指定的顺序）。

通常你可以依赖于抽象类型，即 PriorityQueue 或 BlockingQueue。如果你的代码需要了解这两个概念，可能需要重新思考。

有许多原因你可能需要一个PriorityQueue，这归结于消息排序。例如，在作业队列中，你可能希望能够给这些作业设定优先级。但是，通常处理作业的代码应该对顺序无所谓。

使用BlockingQueue通常涉及到工作线程获取排队的工作，并且当没有工作可做时，这些线程将被阻塞直到有工作可用。与PriorityQueue的例子类似，调用代码可以对此不加关注，尽管你可能想使用某种等待超时机制，这并不总是适用的。

- Nick Holt

Answer 2

PriorityBlockingQueue是在JDK 5中的并发包中添加的，请参见：http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/package-summary.html

它基本上在底层执行了你为PriorityQueue编写的额外代码，添加了通常需要的同步/等待/通知操作来管理你的队列。因此，“Blocking”这个词被添加到名称中，以表示线程将阻塞等待，直到队列中有一个可用的项。

如果你的应用程序可以在JDK 5或更新版本中运行，那么建议使用PriorityBlockingQueue。

- jsurls

Answer 3

我知道这是一个老话题，但我看到你没有考虑到优先队列的并发实现。

尽管Java的集合框架没有提供优先队列的并发实现，但它有足够的构建块可以创建一个。

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

}

这个队列是基于跳表实现的，通过将所有操作委托给ConcurrentSkipListMap类来完成。它允许多线程非阻塞并发访问。

- bennyl

---

这是一个优先队列自从什么时候开始的？按照目前的状态，它是无用的。 - devoured elysium