java并发包简述之BlockingDeque

发表于 | 评论数： | 阅读次数：

BlockingDeque

java并发包下提供的双端阻塞队列

BlockingDeque同时支持两个特性：

1.取数据的时候如果发现队列没有数据，则等待双端队列变成非空；

2.存数据的时候，如果发现队列已满，则等待双端队列有空闲空间；

BlockingQueue和BlockingDeque差异

BlockingQueue是单向的堵塞队列，而BlockingDeque是双端堵塞队列。

在BlockingQueue的实现中也有一个双栈/双队列的实现SynchronousQueue，
BlockingDeque实际上是支持单个队列双端操作，区分好这两个区别就好。

BlockingQueue和BlockingDeque相同处

如果想自定义实现BlockingDeque，可以直接使用一个BlockingQueue的实现作为类变量，
并直接通过操作类变量的API来自定义实现。

这是因为，BlockingQueue和BlockingDeque之间的部分API含义是完全相同的，
下面是部分等价API的说明

插入

BlockingQueue 方法 等效BlockingDeque方法
add(e) addLast(e)
offer(e) offerLast(e)
put(e) putLast(e)
offer(e, time, unit) offerLast(e, time, unit)

删除

BlockingQueue 方法 等效BlockingDeque方法
remove() removeFirst()
poll() pollFirst()
take() takeFirst()
poll(time, unit) pollFirst(time, unit)

检查元素

BlockingQueue 方法 等效BlockingDeque方法
element() getFirst()
peek() peekFirst()

BlockingDeque实现的约定

如果要实现BlockingDeque，在处理无法即使处理的操作时（如立刻想获取数据但是队列里没有数据），
可以选择以下四种方式:

  1. 抛出异常；
  2. 返回特殊值（null或者false,取决于调用的方法）；
  3. 无限制堵塞，直到操作成功或失败；
  4. 堵塞指定时间，超时放弃操作；

方法实现的约定

针对链表头的操作

插入

方法名 约定返回
addFirst(e) 引发异常
offerFirst(e) 返回特殊值
putFirst(e) 无限制堵塞
offerFirst(e, time, unit) 堵塞指定时间

删除

方法名 约定返回
removeFirst() 引发异常
pollFirst() 返回特殊值
takeFirst() 无限制堵塞
pollFirst(time, unit) 堵塞指定时间

检查元素

方法名 约定返回
getFirst() 引发异常
peekFirst() 返回特殊值
无对应方法 无限制堵塞
无对应方法 堵塞指定时间
针对链表尾的操作

插入

方法名 约定返回
addLast(e) 引发异常
offerLast(e) 返回特殊值
putLast(e) 无限制堵塞
offerLast(e, time, unit) 堵塞指定时间

删除

方法名 约定返回
removeLast() 引发异常
pollLast() 返回特殊值
takeLast() 无限制堵塞
pollLast(time, unit) 堵塞指定时间

检查元素

方法名 约定返回
getLast() 引发异常
peekLast() 返回特殊值
无对应方法 无限制堵塞
无对应方法 堵塞指定时间

部分方法描述

  1. element:检索但不删除此双端队列代表的队列的头
  2. push:在不违反容量限制的情况下立即进行操作，则将一个元素推入此双端队列的头部，如果当前没有可用空间，则抛出异常。
  3. removeFirstOccurrence(Object o):移除队列中相匹配的第一个元素
  4. removeLastOccurrence(Object o):移除队列中相匹配的最后一个元素

具体实现

LinkedBlockingDeque

让人感动的想哭的是，这个接口目前只有一个实现，从命名我们可推断，这是一个使用链表作为数据结构的实现，
默认是无界的(容量默认大小Integer.MAX_VALUE)，也可以在构造器里指定为有界的链表。

Node

链表节点的实现非常简单，Node的代码如下，链表节点prev为自己意味着本身是头节点，
链表节点next为自己意味着本身是尾节点。

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
static final class Node<E> {
    /**
     * The item, or null if this node has been removed.
     */
    E item;

    /**
     * One of:
     * - the real predecessor Node
     * - this Node, meaning the predecessor is tail
     * - null, meaning there is no predecessor
     */
    Node<E> prev;

    /**
     * One of:
     * - the real successor Node
     * - this Node, meaning the successor is head
     * - null, meaning there is no successor
     */
    Node<E> next;

    Node(E x) {
        item = x;
    }
}
Lock实现

LinkedBlockingDeque只持有一把ReentrantLock锁，并从中获取两个Condition作为空队列和满队列的
判定条件，