Java集合Queue

发表于 更新于 分类于 阅读次数： Changyan： 本文字数： 8.8k

Queue

接口，继承自Collection，Java集合框架中的队列实现。

除了基本的Collection操作外，队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是用于专门为有容量限制的 Queue 实现设计的；在大多数实现中，插入操作不会失败。

操作/结果 抛出异常 返回特殊值
插入 add(e) offer(e)
移除 remove() poll()
检查 element() peek()

队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。无论使用哪种排序方式，队列的头 都是调用 remove() 或 poll() 所移除的元素。在 FIFO 队列中，所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个 Queue 实现必须指定其顺序属性。

如果可能，offer 方法可插入一个元素，否则返回 false。这与 Collection.add 方法不同，该方法只能通过抛出未经检查的异常使添加元素失败。offer 方法设计用于正常的失败情况，而不是出现异常的情况，例如在容量固定（有界）的队列中。

remove() 和 poll() 方法可移除和返回队列的头。到底从队列中移除哪个元素是队列排序策略的功能，而该策略在各种实现中是不同的。remove() 和 poll() 方法仅在队列为空时其行为有所不同：remove() 方法抛出一个异常，而 poll() 方法则返回 null。

element() 和 peek() 返回但不移除队列的头。

Queue 接口并未定义并发编程中常见的阻塞队列的方法。BlockingQueue 接口定义了那些等待元素出现或等待队列中有可用空间的方法，这些方法扩展了此接口。

Queue 实现通常不允许插入 null 元素，尽管某些实现（如 LinkedList）并不禁止插入 null。即使在允许 null 的实现中，也不应该将 null 插入到 Queue 中，因为 null 也用作 poll 方法的一个特殊返回值，表明队列不包含元素。

Queue 实现通常未定义 equals 和 hashCode 方法的基于元素的版本，而是从 Object 类继承了基于身份的版本，因为对于具有相同元素但有不同排序属性的队列而言，基于元素的相等性不总是很好定义。

方法

boolean add(E e)

将指定的元素插入此队列，如果队列没满，且可以立即插入，则返回 true。其他异常情况如下：

  • IllegalStateException - 如果由于容量的限制此时不能添加该元素
  • ClassCastException - 如果指定元素的类不允许将其添加到此队列
  • NullPointerException - 如果指定元素为 null 并且此队列不允许 null 元素
  • IllegalArgumentException - 如果此元素的某些属性不允许将其添加到此队列

boolean offer(E e)

将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常要优于 add(E)，后者可能无法插入元素，而只是抛出一个异常。

如果该元素已添加到此队列，则返回 true；否则返回 false

  • ClassCastException - 如果指定元素的类不允许将其添加到此队列
  • NullPointerException - 如果指定元素为 null 并且此队列不允许 null 元素
  • IllegalArgumentException - 如果此元素的某些属性不允许将其添加到此队列

E remove()

获取并移除此队列的头。此方法与 poll 唯一的不同在于：此队列为空时将抛出一个异常。

  • NoSuchElementException - 如果此队列为空

E poll()

获取并移除此队列的头，如果此队列为空，则返回 null。

E element()

获取但是不移除此队列的头。此方法与 peek 唯一的不同在于：此队列为空时将抛出一个异常。

  • NoSuchElementException - 如果此队列为空

E peek()

获取但不移除此队列的头；如果此队列为空，则返回 null。

AbstractQueue

抽象队列类，实现了Queue接口，继承了AbstractCollection。

此类提供某些Queue操作的骨干实现。此类中的实现适用于基本实现不允许包含null元素时。add、remove 和 element 方法分别基于 offer、poll 和 peek 方法，但是它们通过抛出异常而不是返回 false 或 null 来指示失败。

扩展此类的 Queue 实现至少必须定义一个不允许插入 null 元素的 Queue.offer(E) 方法，该方法以及 Queue.peek()、Queue.poll()、Collection.size() 和 Collection.iterator() 都支持 Iterator.remove() 方法。通常还要重写其他方法。如果无法满足这些要求，那么可以转而考虑为 AbstractCollection 创建子类。

方法

boolean add(E e)

1
2
3
4
5
6
public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");
}

基于offer实现，将指定的元素插入到此队列中（如果立即可行且不会违反容量限制），在成功时返回 true，如果当前没有可用空间，则抛出 IllegalStateException。

E remove()

1
2
3
4
5
6
7
public E remove() {
    E x = poll();
    if (x != null)
        return x;
    else
        throw new NoSuchElementException();
}

基于poll实现，获取并移除此队列的头。此方法与 poll 唯一的不同在于：此队列为空时将抛出一个异常NoSuchElementException。

E element()

1
2
3
4
5
6
7
public E element() {
    E x = peek();
    if (x != null)
        return x;
    else
        throw new NoSuchElementException();
}

基于peek实现，获取但不移除此队列的头。此方法与 peek 唯一的不同在于：此队列为空时将抛出一个异常NoSuchElementException。

void clear()

1
2
3
4
public void clear() {
    while (poll() != null)
        ;
}

移除此队列中的所有元素。此调用返回后，队列将为空。

此实现重复调用 poll，直到它返回 null 为止。

boolean addAll(Collection<? extends E> c)

1
2
3
4
5
6
7
8
9
10
11
public boolean addAll(Collection<? extends E> c) {
    if (c == null)
        throw new NullPointerException();
    if (c == this)
        throw new IllegalArgumentException();
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

调用add方法将指定 collection 中的所有元素都添加到此队列中。如果试图将某一队列 addAll 到该队列本身中，则会导致 IllegalArgumentException。此外，如果正在进行此操作时修改指定的 collection，则此操作的行为是不确定的。

此实现在指定的 collection 上进行迭代，并依次将迭代器返回的每一个元素添加到此队列中。在试图添加某一元素（尤其是 null 元素）时如果遇到了运行时异常，则可能导致在抛出相关异常时只成功地添加了某些元素。

  • ClassCastException - 如果指定 collection 元素的类不允许将该元素添加到此队列中
  • NullPointerException - 如果指定 collection 包含一个 null 元素并且此队列不允许 null 元素，或者指定 collection 为 null
  • IllegalArgumentException - 如果指定 collection 元素的某些属性不允许将该元素添加到此队列中，或者指定 collection 是此队列
  • IllegalStateException - 如果此时由于插入限制无法添加所有元素

BlockingQueue

接口，继承自Queue，支持两个附加操作的Queue，这两个操作是：

  • 获取元素时等待队列变为非空
  • 存储元素时等待空间变得可用

BlockingQueue 方法以四种形式出现，对于不能立即满足但可能在将来某一时刻可以满足的操作，这四种形式的处理方式不同：第一种是抛出一个异常，第二种是返回一个特殊值（null 或 false，具体取决于操作），第三种是在操作成功前，无限期地阻塞当前线程，第四种是在给定的最大时间限制内阻塞，超时失败。下表中总结了这些方法：

操作/结果 抛出异常 返回特殊值 阻塞等待 超时等待
插入 add(e) offer(e) put(e) offer(e, time, unit)
移除 remove() poll() take() poll(time, unit)
检索 element() peek() 不可用 不可用

BlockingQueue 不接受 null 元素，试图 add、put 或 offer 一个 null 元素时，某些实现会抛出 NullPointerException。null 被用作指示 poll 操作失败的警戒值。

BlockingQueue可以是限定容量的。它在任意给定时间都可以有一个 remainingCapacity，超出此容量，便无法无阻塞地 put 附加元素。没有任何内部容量约束的 BlockingQueue 总是报告 Integer.MAX_VALUE 的剩余容量。

BlockingQueue实现主要用于生产者-使用者队列，但它另外还支持 Collection 接口。因此，举例来说，使用 remove(x) 从队列中移除任意一个元素是有可能的。然而，这种操作通常不会有效执行，只能有计划地偶尔使用，比如在取消排队信息时。

BlockingQueue实现是线程安全的。所有排队方法都可以使用内部锁或其他形式的并发控制来自动达到它们的目的。然而，大量的 Collection 操作（addAll、containsAll、retainAll 和 removeAll）没有必要自动执行，除非在实现中特别说明。因此，举例来说，在只添加了 c 中的一些元素后，addAll(c) 有可能失败（抛出一个异常）。

BlockingQueue 实质上不 支持使用任何一种“close”或“shutdown”操作来指示不再添加任何项。这种功能的需求和使用有依赖于实现的倾向。例如，一种常用的策略是：对于生产者，插入特殊的 end-of-stream 或 poison 对象，并根据使用者获取这些对象的时间来对它们进行解释。

以下是基于典型的生产者-使用者场景的一个用例。注意，BlockingQueue 可以安全地与多个生产者和多个使用者一起使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Producer implements Runnable {
  private final BlockingQueue queue;
  Producer(BlockingQueue q) { queue = q; }
  public void run() {
    try {
      while(true) { queue.put(produce()); }
    } catch (InterruptedException ex) { ... handle ...}
  }
  Object produce() { ... }
}

class Consumer implements Runnable {
  private final BlockingQueue queue;
  Consumer(BlockingQueue q) { queue = q; }
  public void run() {
    try {
      while(true) { consume(queue.take()); }
    } catch (InterruptedException ex) { ... handle ...}
  }
  void consume(Object x) { ... }
}

class Setup {
  void main() {
    BlockingQueue q = new SomeQueueImplementation();
    Producer p = new Producer(q);
    Consumer c1 = new Consumer(q);
    Consumer c2 = new Consumer(q);
    new Thread(p).start();
    new Thread(c1).start();
    new Thread(c2).start();
  }
}

内存一致性效果：当存在其他并发 collection 时，将对象放入 BlockingQueue 之前的线程中的操作 happen-before 随后通过另一线程从 BlockingQueue 中访问或移除该元素的操作。

方法

boolean add(E e)

将指定元素插入此队列中（如果立即可行且不会违反容量限制），成功时返回 true，如果当前没有可用的空间，则抛出 IllegalStateException。当使用有容量限制的队列时，通常首选 offer

boolean offer(E e)

将指定元素插入此队列中（如果立即可行且不会违反容量限制），成功时返回 true，如果当前没有可用的空间，则返回 false。当使用有容量限制的队列时，此方法通常要优于 add(E)，后者可能无法插入元素，而只是抛出一个异常。

void put(E e) throws InterruptedException

将指定元素插入此队列中，将等待可用的空间（如果有必要）。

  • InterruptedException - 如果在等待时被中断
  • ClassCastException - 如果指定元素的类不允许将其添加到此队列
  • NullPointerException - 如果指定元素为 null
  • IllegalArgumentException - 如果指定元素的某些属性不允许将其添加到此队列

boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException

将指定元素插入此队列中，在到达指定的等待时间前等待可用的空间（如果有必要）。

如果成功，则返回 true；如果在空间可用前超过了指定的等待时间，则返回 false。

  • InterruptedException - 如果在等待时被中断
  • ClassCastException - 如果指定元素的类不允许将其添加到此队列
  • NullPointerException - 如果指定元素为 null
  • IllegalArgumentException - 如果指定元素的某些属性不允许将其添加到此队列

E take() throws InterruptedException

获取并移除此队列的头部，在元素变得可用之前一直等待（如果有必要）。

E poll(long timeout, TimeUnit unit) throws InterruptedException;

获取并移除此队列的头部，在指定的等待时间前等待可用的元素（如果有必要）。

int remainingCapacity();

返回在无阻塞的理想情况下（不存在内存或资源约束）此队列能接受的附加元素数量，即剩余容量；如果没有内部限制，则返回 Integer.MAX_VALUE。

注意，不能 总是通过检查 remainingCapacity 来判断尝试插入元素是否成功，因为可能出现这样的情况：其他线程即将插入或移除一个元素。

boolean remove(Object o)

从此队列中移除指定元素的单个实例（如果存在）。更确切地讲，如果此队列包含一个或多个满足 o.equals(e) 的元素 e，则移除该元素。如果此队列包含指定元素（或者此队列由于调用而发生更改），则返回 true。

  • ClassCastException - 如果指定元素的类与此队列不兼容（可选）
  • NullPointerException - 如果指定元素为 null（可选）

boolean contains(Object o)

如果此队列包含指定元素，则返回 true。更确切地讲，当且仅当此队列至少包含一个满足 o.equals(e) 的元素 e时，返回 true。

int drainTo(Collection<? super E> c)

移除此队列中所有可用的元素，并将它们添加到给定 Collection 中。此操作可能比反复轮询此队列更有效。在试图向 Collection c 中添加元素没有成功时，可能导致在抛出相关异常时，元素会同时在两个 Collection 中出现，或者在其中一个 Collection 中出现，也可能在两个 Collection 中都不出现。如果试图将一个队列放入自身队列中，则会导致 IllegalArgumentException 异常。此外，如果正在进行此操作时修改指定的 Collection，则此操作行为是不确定的。

  • UnsupportedOperationException - 如果指定 Collection 不支持添加元素
  • ClassCastException - 如果此队列元素的类不允许将其添加到指定 Collection
  • NullPointerException - 如果指定 Collection 为 null
  • IllegalArgumentException - 如果指定 Collection 是此队列，或者此队列元素的某些属性不允许将其添加到指定 Collection

int drainTo(Collection<? super E> c, int maxElements);

  • maxElements - 传输元素的最大数量

最多从此队列中移除给定数量的可用元素，并将这些元素添加到给定 Collection 中。在试图向 Collection c 中添加元素没有成功时，可能导致在抛出相关异常时，元素会同时在两个 Collection 中出现，或者在其中一个 Collection 中出现，也可能在两个 Collection 中都不出现。如果试图将一个队列放入自身队列中，则会导致 IllegalArgumentException 异常。此外，如果正在进行此操作时修改指定的 Collection，则此操作行为是不确定的。

ArrayBlockingQueue

一个由数组支持的有界阻塞队列。此队列按 FIFO（先进先出）原则对元素进行排序。队列的头部是在队列中存在时间最长的元素。队列的尾部 是在队列中存在时间最短的元素。新元素插入到队列的尾部，队列获取操作则是从队列头部开始获得元素。

这是一个典型的“有界缓存区”，固定大小的数组在其中保持生产者插入的元素和使用者提取的元素。一旦创建了这样的缓存区，就不能再增加其容量。试图向已满队列中放入元素会导致操作受阻塞；试图从空队列中提取元素将导致类似阻塞。

此类支持对等待的生产者线程和消费者线程进行排序的可选公平策略。默认情况下，不保证是这种排序。然而，通过将公平性 (fairness) 设置为 true 而构造的队列允许按照 FIFO 顺序访问线程。公平性通常会降低吞吐量，但也减少了可变性和避免了“不平衡性”。

该队列不允许插入null元素。

源码分析可以参考**http://www.cnblogs.com/leesf456/p/5533770.html**

PriorityQueue

基于优先级堆（二叉堆）的无界优先级队列，优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的Comparator进行排序，具体取决于所使用的构造方法。

优先级队列不允许使用null元素，依靠自然顺序的优先级队列还不允许插入不可比较的对象（避免可能导致的ClassCastException）。

此队列的头* 是按指定排序方式确定的*最小 元素**。如果多个元素都是最小值，则头是其中一个元素——选择方法是任意的。队列获取操作 poll、remove、peek 和 element 访问处于队列头的元素。

优先级队列是无界的，但是有一个内部容量，控制着用于存储队列元素的数组大小。它通常至少等于队列的大小。随着不断向优先级队列添加元素，其容量会自动增加。无需指定容量增加策略的细节。

此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。方法 iterator() 中提供的迭代器不 保证以任何特定的顺序遍历优先级队列中的元素。如果需要按顺序遍历，请考虑用 Arrays.sort(pq.toArray())。

注意，此实现不是同步的。如果多个线程中的任意线程修改了队列，则这些线程不应同时访问 PriorityQueue 实例。相反，请使用线程安全的 PriorityBlockingQueue 类。

PriorityBlockingQueue

无界阻塞队列，线程安全