Java1.8-DelayQueue源码学习（上）（四）

一、前言

在学习DelayQueue之前，我们先来熟悉下Queue相关的一些基础接口。

1. Queue接口

  Queue(队列)，前面学习集合框架的时候已经了解过，是一种先进先出的数据结构(FIFO, First In First Out)，同样继承自Collection集合，队列有头指针head和尾指针tail，数据从队尾入队，从对头出队。简单介绍了队列的概念，我们来看下Queue接口中的通用方法。

  Queue接口提供了插入，获取，移除三个方法，每个方法都以两种形式存在：一种在操作失败时抛出异常，另一种在操作失败时返回特殊值（null或false，具体取决于操作），后一种形式的插入操作是专门用于有容量限制的队列的；

	抛出异常	返回特殊值
添加	add(e)	offer(e)
删除	remove()	poll()
获取	element()	peek()

Queue接口中，共有以上6个方法：

• add, 常规的添加元素的方法，如果添加元素的时候由于容量的限制添加失败，则会抛出异常；
• offer, 添加元素，当队列有容量限制并且队列已满(没有可用空间)的时候，该方法会返回false，而对应的add方法则是抛出异常；所以在使用有容量限制的队列时，建议使用offer方法；
• remove, 删除方法，删除并返回队列的头部元素，如果队列为空，抛出异常；
• poll, 删除方法， 删除并返回队列的头部元素，和remove方法的不同之处在于，队列为空时，remove方法抛出异常，而poll方法返回null；
• element, 返回队列的头部元素，但不删除；
• peek, 返回队列的头部元素，但不删除，和element方法的不同在于，队列为空时，element会抛出异常，而peek则会返回null；

从上面的介绍可以看出，poll和remove，element和peek方法的不同就在于当队列为空时的处理情况。

队列实现通常不允许插入null元素，虽然某些实现（如LinkedList）允许插入null。即便在允许它的实现中，也不应将null插入到Queue中，因为null会被poll等方法用作特殊返回值，用来表示队列不包含任何元素。

2. Deque接口

  Deque，被称为双端队列，队列的原则是只能一头入队，一头出队，而双端队列则是两端都可以入队和出队的队列。Deque扩展自Queue，并且Deque也可以用作LIFO(后进先出)，也就是栈的操作，所以官方建议我们应该优先使用该接口而不是Stack来进行栈的操作。由于前面已经学习过，这里不多讲了，我们还是来看下它的方法。

	Head	Head	Tail	Tail
	抛出异常	返回特殊值	抛出异常	返回特殊值
添加	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
删除	removeFirst()	pollFirst()	removeLast()	pollLast()
获取	getFirst()	peekFirst()	getLast()	peekLast()

由于双端队列可以操作对头和队尾，所以针对添加、删除、获取这三种情况，除了Queue接口中继承的三个方法，还有分别针对队头和队尾进行操作的特殊方法。而从Queue接口继承的方法与Deque中的一些方法是完全等效的，对应关系如下表所示：

Queue方法	等效Deque方法
add(e)	addLast(e)
offer(e)	offerLast(e)
remove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()

上述这些方法一般用于队列（FIFO）操作，而该接口中还提供了一些用于栈（LIFO）操作的方法， 当Deque用作栈时，元素将从双端队列的头部进行操作元素。 同样，Stack中对栈操作的一些常规方法与Deque中一些方法是完全等效的，我们来看下对应关系：

Stack方法	等效Deque方法
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()

需要注意，peek方法，无论Deque是用作队列或时栈，该方法都是有效的。另外，该接口提供了两种方法来删除内部元素：

• removeFirstOccurrence，从双端队列中删除第一次出现的指定元素；
• removeLastOccurrence，从双端队列中删除最后一次出现的指定元素；

此外，Deque针对栈的使用还提供了两个方法：

• pop，返回栈顶的元素，也就是从双端队列中删除并返回第一个元素（头部），该方法等同于 removeFirst 方法；
• push，往栈里添加元素，也就是在双端队列的头部添加元素，如果没有可用空间导致添加失败时会抛出异常；该方法等同于addFirst方法；

还有，Deque针对Collection 的常规操作，还实现或者提供了一些方法：

• remove(Object)，从此双端队列中删除第一次出现的指定元素,等同于removeFirstOccurrence方法；
• iterator，以适当的顺序返回此双端队列中元素的迭代器，遍历顺序是从头部到尾部；
• descendingIterator，以相反的顺序返回此双端队列中元素的迭代器，顺序为从尾部到头部；

最后需要注意的是，与List接口不同，此接口不支持对元素的索引访问；虽然Deque实现并不严格要求禁止插入null元素，但官方强烈建议我们在使用Deque时禁止插入null元素。

3. BlockingQueue接口

  BlockingQueue表示阻塞队列，该接口扩展了Queue接口，并提供了几个阻塞方法，用于实现：当生产者向队列添加元素但队列已满时，生产者会被阻塞；当消费者从队列移除元素但队列为空时，消费者会被阻塞。而相对Queue接口，该接口的方法有四种表示形式：

	抛出异常	返回特殊值	阻塞	超时
添加	add(e)	offer(e)	put(e)	offer(e, time, unit)
删除	remove()	poll()	take()	poll(time, unit)
获取	element()	peek()

当然，BlockingQueue不支持null值，null是用作标记的值。

BlockingQueue可以有容量大小限制，超过容量大小的时候，不能在没有阻塞的情况下插入元素，BlockingQueue的实现主要用于生产者-消费者队列，并且，BlockingQueue可以安全地与多个生产者和多个消费者一起使用。

BlockingQueue是线程安全的，所有的方法都使用内部锁或者其他形式的并发控制以原子方式实现其效果，但是，除非在实现中另有说明，否则批量操作addAll，containsAll，retainAll和removeAll不一定以原子方式执行。

下面对该接口的其他方法简介再介绍下：

• put(E)，添加元素，该方法是阻塞方法，必要时会阻塞直到队列的容量空间可用；
• take()，删除并返回头部元素，该方法是阻塞方法，必要时会阻塞，直到队列中的元素可用；
• remainingCapacity()，- 返回理想情况下（没有内存和资源约束的情况下）此队列剩余可以无阻塞添加元素的数量，但是，我们不能总是通过检查remainingCapacity来判断插入元素的尝试是否成功，因为可能有另一个线程即将插入或删除元素的情况。
• drainTo(Collection)，- 删除此队列中所有元素，并将这些元素添加到给定集合中；另一个两个参数的重载方法，则表示，从该队列中删除最多给定数量的元素，并将这些元素添加到给定集合中；
• poll(long, TimeUnit)，获取并删除队列的头部元素，超时方法，在必要时会等待指定的时间以使元素可用；
• offer(E, long, TimeUnit)，添加元素，超时方法，在必要时会等待指定的时间以使队列空间可用；

4. BlockingDeque接口

  BlockingDeque，阻塞双端队列，扩展自BlockingQueue与Deque，由于是双端队列，所以它的方法针对头部和尾部操作，各有四种形式，我们首先来看下针对头部进行操作的：

	抛出异常	返回特殊值	阻塞	超时
添加	addFirst(e)	offerFirst(e)	putFirst(e)	offerFirst(e, time, unit)
删除	removeFirst()	pollFirst()	takeFirst()	pollFirst(time, unit)
获取	getFirst()	peekFirst()

同样，针对尾部的操作，就是将对应的First修改为Last：

	抛出异常	返回特殊值	阻塞	超时
添加	addLast(e)	offerLast(e)	putLast(e)	offerLast(e, time, unit)
删除	removeLast()	pollLast()	takeLast()	pollLast(time, unit)
获取	getLast()	peekLast()

与BlockingQueue一样，BlockingDeque也是线程安全的，不允许存储null元素，可以有容量限制。一些从BlockingQueue接口继承的方法与BlockingDeque方法是完全等效的，我们来看下这些方法：

图片来自JDK8-api官网.png

5. TransferQueue接口

  TransferQueue扩展自BlockingQueue，是一个特殊的阻塞队列。当我们使用BlockingQueue时，我们只需要关注的是将元素放进队列（如果队列已满，则进行阻塞）即可，而TransferQueue则是对BlockingQueue进行了增强，借助该接口我们可以实现：生产者会一直阻塞直到所添加到队列的元素被某一个消费者所消费（不仅仅是添加到队列里就完事）。

另外，该接口截止到JDK8，只有一个实现类LinkedTransferQueue，这是个无界的阻塞队列，后面我们会介绍到这个类。我们先来看下他提供的方法：

• transfer(E)，阻塞方法，在必要的情况下会阻塞，直到元素被消费者消费；
  • 当有消费者线程阻塞等待时，调用transfer方法的生产者线程不会将元素存入队列，而是直接将元素传递给消费者；
  • 如果调用transfer方法的生产者线程发现没有正在等待的消费者线程，则会将元素入队，然后会阻塞等待，直到有一个消费者线程来获取该元素；
  • 在队列中已有元素的情况下，调用transfer方法，还可以确保队列中被传递元素之前的所有元素都能被处理；
• tryTransfer(E)，当调用tryTransfer方法时，如果有消费者正在等待接收元素，直接将元素传送给消费者；如果没有，则会立即返回false。该方法和transfer方法的区别在于tryTransfer方法无论消费者是否接收，方法立即返回，元素不会入队；而transfer方法必须等到消费者消费后才返回；
• tryTransfer(E, long, TimeUnit)，超时方法，如果有消费者正在等待接收元素，则理解将元素给消费者；如果在这一段超时时间内还没有消费者消费元素，则返回false；如果在超时时间内消费了元素，则返回true；
• hasWaitingConsumer()，判断是否有消费者正在等待接收元素，如果至少有一个消费者正在等待通过BlockingQueue.take()或定时轮询接收元素，则返回true；
• getWaitingConsumerCount()，返回通过BlockingQueue.take()或定时轮询等待接收元素的消费者数量的估计值，该值是一个瞬时值，可能不准确，该值可用于监控使用，但不适合用于程序中同步控制；

最后，我们简单看一个小例子：

public static void testTransferQueue() throws InterruptedException {
    TransferQueue<String> transferQueue = new LinkedTransferQueue<>();
    transferQueue.add("hello");
    new Thread(() -> {
        try {
            transferQueue.transfer("world");
            System.out.println("new Thread ->> ");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }).start();

    String str = transferQueue.take();
    // output hello
    System.out.println("finish ->> " + str);
    // 以下代码可以先注释掉，看一下运行情况，再去掉注释运行
    // str = transferQueue.take();
    // System.out.println("finish ->> " + str);
}

本文主要参考自：
JDK8官方API：https://docs.oracle.com/javase/8/docs/api/
Java 7中的TransferQueue - 并发编程网
Java多线程进阶（三八）—— J.U.C之collections框架：LinkedTransferQueue