Java Queues

Queue

A collection designed for holding elements prior to processing. Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations. Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value (either null or false, depending on the operation). The latter form of the insert operation is designed specifically for use with capacity-restricted Queue implementations; in most implementations, insert operations cannot fail.

队列是一种设计为有操作优先级的集合,是集合框架的成员之一。除了基本的集合操作外,还额外提供特有的插入、提取和查看操作,每个操作都提供两种方式:一种是失败会抛出异常,一种则是返回特定值(根据不同的操作返回null或false)。在大部分队列实现中,插入操作一般都不会失败。 返回特定值方式的操作是特别为有容量限制的队列实现类而设计的。 队列通常(非必须)都是提供一种先进先出(FIFO:first-in-first-out)的元素管理操作方式。调用remove()和poll()方法会移除队列头部元素并返回该元素,element()和peek()方法则是仅返回头部元素;在一个先进先出队列中,新的元素总是插入到队列的尾部。

队列的实现通常不允许插入null元素,但有一些例外例如LinkedList则是允许插入null元素;虽然有些队列实现允许插入null值,但作为队列来使用的话,还是不应当这么做,因为队列的poll和peek操作如果失败会返回null,这样会造成混乱,不确定是操作失败,还是操作的元素是null值。

BlockingQueue

Queue that additionally supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element.

阻塞队列是提供阻塞操作的队列:当获取元素时队列为空,则会等待直到队列有元素时才操作;当存入一个元素值队列已满的话,会等待直到有空间才进行操作。

BlockingQueue methods come in four forms, with different ways of handling operations that cannot be satisfied immediately, but may be satisfied at some point in the future: one throws an exception, the second returns a special value (either null or false, depending on the operation), the third blocks the current thread indefinitely until the operation can succeed, and the fourth blocks for only a given maximum time limit before giving up. These methods are summarized in the following table:

阻塞队列的方法有4种形式,除了队列本身的抛出异常,返回特定值两种外,还提供另外两种:一种是阻塞操作,put(e)和take(),插入和取出,这两种如果空间已满或者无元素则会被阻塞(即等待)直到有空间或者有元素;另一种则在前面方法的基础上增加时间设置,即阻塞一定时间后会放弃,然后根据成功失败返回对应值。

一个阻塞队列有的可能会指定容量。在给定时间点会有一个“剩余容量”的值,当剩余容量值为0时再添加元素则会被阻塞(即需要等待直到有空余空间或者说容量时)才能完成操作。一个没有容量约束的阻塞队列的剩余容量总是为整形整数的最大值(Integer.MAX_VALUE),例如 PriorityBlockingQueue。

阻塞队列的实现一般主要用来作为生产者-消费者队列,但同时也支持集合操作,因此可以通过remove(x)方法来移除指定对象,不过这种操作一般都不是很有效率,只是预计作为偶尔使用,例如取消队列中的某个消息。

阻塞队列的实现类是线程安全的。所有队列操作方法通过内部锁或者其他并发控制方式来实现操作的原子性。但是除非特定的实现,一般队列的批量操作是不需要实现原子性的,因此批量操作是有可能失败(抛出异常)的,例如addAll(c)批量添加元素超过队列容量限制,方法里面调用add(e)方法,失败则抛出异常。

由于阻塞队列实现是线程安全的,因此在多个生产者和多个消费者中使用同个阻塞队列也是安全的。

DelayQueue

PriorityQueue

TransferQueue

ArrayBlockingQueue

ConcurrentLinkedQueue

LinkedBlockingDeque

LinkedTransferQueue

LinkedList

PriorityBlockingQueue

SynchronousQueue

blocking queue in which each insert operation must wait for a corresponding remove operation by another thread, and vice versa. A synchronous queue does not have any internal capacity, not even a capacity of one. You cannot peek at a synchronous queue because an element is only present when you try to remove it; you cannot insert an element (using any method) unless another thread is trying to remove it; you cannot iterate as there is nothing to iterate. The head of the queue is the element that the first queued inserting thread is trying to add to the queue; if there is no such queued thread then no element is available for removal and poll() will return null. For purposes of other Collection methods (for example contains), a SynchronousQueue acts as an empty collection. This queue does not permit null elements.

Synchronous queues are similar to rendezvous channels used in CSP and Ada. They are well suited for handoff designs, in which an object running in one thread must sync up with an object running in another thread in order to hand it some information, event, or task.

This class supports an optional fairness policy for ordering waiting producer and consumer threads. By default, this ordering is not guaranteed. However, a queue constructed with fairness set to true grants threads access in FIFO order.

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces.

Deque

A linear collection that supports element insertion and removal at both ends. The name deque is short for “double ended queue” and is usually pronounced “deck”. Most Deque implementations place no fixed limits on the number of elements they may contain, but this interface supports capacity-restricted deques as well as those with no fixed size limit.

支持两端插入和移除的线性集合。Deque名称是双端队列的简称。大部分Deque的实现不限制容量,但本身是支持容量限制的。

一个双端队列可以作为 FIFO (First-In-First-Out) 先进先出的队列来操作,如:

亦可以做为Stack栈来使用:

另外还提供两个移除内部元素的方法:

  • boolean removeFirstOccurrence​(Object o) :移除第一个出现的指定对象,如果有并成功移除则返回true
  • boolean removeLastOccurrence​(Object o) :移除最后一个出现的指定对象,如果有并成功移除则返回true

双端队列并不严格禁止插入null元素,但与队列类似,强烈建议不要插入null元素。

to be continue…

Leave a Reply

Your email address will not be published. Required fields are marked *