Java Queue队列特性

Java Queue的设计目标在于让集合中的元素,在被处理的时候有一种优先级的概念,优先级是Queue的一个基本应用场景。

Queue接口特点

Queue除了具有集合(java.util.Collection Collection)的基本特性外,并额外提供了插入(insertion)、提取(extraction)和检查(inspection )等操作。

Queue接口分两种形式存在:一种操作失败抛出异常,另一种是返回特殊值(null或false),后者专门用于对容量有限制的场景,在大多数的队列实现中,插入操作不会失败。

队列中的元素通常按 FIFO(先进先出)方式排序。优先级队列除外,根据提供的比较器对元素进行排序,其他LIFO 队列(或堆栈) 按LIFO(后进先出)方式对元素排序。

无论队列采用何种排序方式,队列"头部"元素,都是通过调用remove()或poll()进行删除。 在FIFO(先进先出)队列中,新元素插入在队列的"尾部"。 不同类型的队列可能会有不同的放置规则,Queue的具体实现都必须指定其排序属性。

Queue 通用API

每种队列都有自己的具体实现,但都遵循一组通用API。

boolean offer(E e);

如果队列允许放入新元素则插入,否则返回false。与java.util.Collection的add方法不同,后者在添加元素失败时,会抛出一个未经检查的异常。队列API设计认为添加失败的情况实属正常。

E remove();
E poll();

这两个方法用于删除,并返回队列“头部”元素,具体删除队列中的哪个元素,取决于队列的排序策略。这两个方法的差异,在于队列为空时的处理(queue is empty),remove()方法会抛出异常,poll()方法会返回null。

E element();
E peek();

这两个方法都用来返回元素,但不会把元素从队列中删除,二者的区别依然是队列元素为空的处理方式,前者抛出NoSuchElementException,后者返回null。

Queue接口并未定义阻塞队列(blocking queue)的行为(methods),只是定义了并发编程下常用的方法。

那些等待元素出现或空间可用的API在java.util.concurrent.BlockingQueue中定义,用于扩展Queue。

Queue具体实现

ArrayBlockingQueue

一个基于数组的容量有限队列,队列一旦创建,大小就不能被改变。队列的元素按FIFO(先进先出)排序。队列的“头部”元素,为队列中时间最长的元素,“尾部”则为存在间最短的元素。当新元素被放入队列的“尾部”,从“头部”获取元素的操作会被恢复。

这是一个经典的有限缓存,生产者把元素放入一个固定大小的数组中,消费者从中取出元素。

试图通过put(E e)方法往一个容量已满的队列中放入新元素,操作将被阻塞。

试图通过public E take()方法从空的队列中获取元素,操作同样会被阻塞。

ArrayBlockingQueue支持一种可选的公平策略,用于控制唤醒生产者和消费者的线程顺序,默认无序,通过将构造参数设置为true,允许线程以FIFO(先进先出)的顺序公平问,公平性通常会影响吞吐量,同时也降低了易变性,避免了线程饿死,这个类支持Collection的迭代器。

ConcurrentLinkedQueue

一个基于链表线程安全容量无限的队列,队列以FIFO(先进先出)进行排序。当多个线程共享一个集合时,ConcurrentLinkedQueue是个不错的选择。和大多并发集合一样,ConcurrentLinkedQueue不允许null元素。

该实现采用有效的非阻塞算法,算法基于Maged M.Michael和Michael L.Scott,该算法的特点:简单、快速、实用,非阻塞/阻塞。

DelayQueue

一个容量无限的队列,DelayQueue中的元素,只能在延迟到期时才能被获取。队列中的“头部”元素,是已经达到过期时间,并且距离现在时间最远的元素,如果过期时间未到,则没有“头部”元素,poll()方法返回null。

getDelay(TimeUnit.NANOSECONDS)方法会返回一个小于或等于零的值。

take()、poll()无法删除未到期的元素,相反,它们会像正常元素一样被对待。

size()方法会返回已过期和未过期的元素个数,DelayQueue也不允许null元素。

LinkedBlockingQueue

一个基于链表容量可选的FIFO(先进先出)阻塞队列,“头部”元素是队列中排队时间最长的元素。新元素的加入会使获取元素的操作被恢复。此队列通常比基于阵列的队列具有更高的吞吐量,但是,大多数并发应用程序的性能预测性较差。

构造方法的可选参数可设置容量,用于防止元素过多。如果未指定队列的容量等于Integer.MAX_VALUE。队列的新节点在插入元素时动态创建,除非队列已达到最大容量。

LinkedTransferQueue

一个基于链表容量无限的FIFO(先进先出)队列。"头部"元素为队列中存放时间最长的元素,"尾部"则为时间最短的元素。需要注意的是,与大多数集合的size()方法不同,LinkedTransferQueue的size方法操作时间不是恒定的,由于这些队列的异步性质,查询元素数量时,需要遍历元素,因此,如果在遍历期间修改集合,则会导致结果不准确。

批量操作API:addAll、removeAll、retainAll、containsAll、equals和toArray不保证以原子方式执行。

PriorityBlockingQueue

一个容量无限的阻塞队列,与PriorityQueue排序规则相同,并提供阻塞检索操作。PriorityBlockingQueue队列在逻辑上是无限制的,但如果资源耗尽导致OutOfMemoryError,再尝试添加时会失败。此队列不允许null元素。

依赖于Comparable natural ordering的优先级队列,不允许插入不可比较的对象(未实现Comparable接口的对象),否则会导致ClassCastException。

PriorityBlockingQueue的操作,相同优先级的元素之间不保证有序,如果需要强制执行排序,则需定义比较器的辅助键。

SynchronousQueue

每个插入操作,都必须等待一个执行删除线程的,反之亦然,同步队列没不需要容量。不能在同步队列中调用peek()方法,因为,只有在试图删除元素时才会加入新元素。不能使用任何方法插入一个元素,除非,另一个线程试图删除它。不能迭代,因为没有什么可以迭代的。

队列的"头部"是第一个排队插入的线程,尝试添加到队列的元素,如果没有这样排队的线程,则没有可用于删除的元素,poll()将返回null。出于符合Collection方法的目的(例如contains),SynchronousQueue充当空集合。此队列不允许null元素。

同步队列类似于CSP和Ada中使用的集合点通道,它们非常适用于切换设计,在一个线程中运行的对象,必须与在另一个线程中的对象同步,以便用于传递某些信息、事件或任务。

SynchronousQueue支持有序等待的可选公平策略,默认情况下,不保证顺序,如将公平策略设置为true,则队列的以FIFO顺序授予线程访问权限。

TransferQueue

一个生产者等待消费者接收元素的阻塞队列。TransferQueue在消息传递应用程序中很有用,生产者使用transfer方法,等待消费者调用take或poll接收元素。而使用put方法将元素放入队列,则无需等待接收,tryTransfer(Object)方法是非阻塞的。

与其他阻塞队列一样,TransferQueue容量是有限制的,传输操作可能会被阻止而等待可用空间。

在容量为零的队列(如:SynchronousQueue)中,put和transfer的行为是一致的。