Java队列 - Queue

Queue具有集合的基本特性,还拥有插入(insertion)、提取(extraction)和检查(inspection )等操作。

Queue特点

Queue具有集合(java.util.Collection Collection)的基本特性。

Queue接口分两种:

一种操作失败抛出异常。

另一种测返回特殊值(null或false)。

后者用于对容量有限制的场景,大多数队列实现中,插入操作不会失败。

队列中元素通常按 FIFO(先进先出)方式排序。

优先级队列根据比较器对元素执行排序,其他LIFO 队列(或堆栈) 按LIFO(后进先出)方式对元素排序。

队列"头部"元素通过调用remove()或poll()进行删除。

在FIFO队列中,新元素插入到队列"尾部"。

不同类型的队列可能会有不同放置规则,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中定义。

具体实现

ArrayBlockingQueue

基于数组容量有限的队列,一旦创建,大小不能改变。

队列元素按FIFO排序。队列“头部”元素为队列中时间最长的元素。

新元素被放入队列“尾部”,“头部”获取元素的操作会被恢复。

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

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

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

ArrayBlockingQueue支持可选的公平策略,控制唤醒生产者和消费者的顺序,默认无序。

通过将构造参数设置为true,允许线程以FIFO顺序公平访问,公平会影响吞吐量,也降低了易变性。

ConcurrentLinkedQueue

基于链表线程安全容量无限的队列,队列以FIFO(先进先出)排序。

适用于多个线程共享一个集合的场景。和大多并发集合一样,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的行为是一致的。