JUC之BlockingDeque双端队列

痛定思痛。 2022-09-01 14:56 189阅读 0赞

> **关键词：**Queue    Deque    [BlockingQueue][]    BlockingDeque

--------------------

# **█**** **Deque #

deque，**double ended queue**。双端队列，即从队列的两端都可以对元素进行插入（入队）、移出（出队）等操作。不同的是**Queue**，Queue是单端队列，只能从队列的一端对元素进行入队、出队操作*。（关于Queue的相关介绍，请戳《[JUC之BlockingQueue初识][BlockingQueue]》）*因为双端队列可以从队列的两端进行元素的操作，因此结合该特点，可以使用双端队列来实现**队列**（**先进先出FIFO**）和**栈**（**后进先出LIFO**）。

![20210728212024813.png][]

Deque继承了Queue，因此其在Queue中定义的相关方法和功能的基础上定义了相关双端操作的方法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70][]

### 方法： ###

在Deque中定义了如下的方法，并对方法的行为进行定义和约束，子类在实现这些方法的时候要满足其中的定义和约束行为。（只介绍在Deque中定义的方法）

**（1）**向队列中添加元素（不具有阻塞等待功能）

*  **addFirst**

void addFirst(E e);

** **向队首（队列的头部）添加元素。不管是双端队列Deque还是单端队列Queue，都是有队首和队尾的。队列的开头就是队首，队列的末尾就是队尾（可以想象在实际生活中排队的情形）。如果队列满了没有足够的空间继续添加元素了，元素添加失败，抛出**IllegalStateException**异常。

*  **addLast**

void addLast(E e);

与addFirst相反，addLast是向队尾添加元素。同样，当队列满了没有足够的空间继续添加元素，元素添加失败，抛出IllegalStateException异常。

*  **offerFirst**

boolean offerFirst(E e);

向队首添加元素，当队列满了没有足够空间继续添加元素时，元素添加失败，返回false。

*  **offerLast**

boolean offerLast(E e);

向队尾添加元素，当队列满了没有足够空间继续添加元素时，元素添加失败，返回false。

*  **add**

boolean add(E e);

父类Queue中也定义了此方法。向队尾添加元素，该方法等价于addLast方法。当队列满了没有足够的空间可以添加元素，元素添加失败，抛出IllegalStateException异常。

*  **offer**

boolean offer(E e);

父类Queue中也定义了此方法。向队尾添加元素，该方法等价于offerLast方法。当队列满了没有足够的空间可以添加元素，元素添加失败，返回false。

*  **push**

void push(E e);

向队首添加元素。该方法等价于addFirst方法。

*  **pop**

E pop();

移出队首的第一个元素。该方法等价于removeFirst方法。

**（2）**从队列中移出元素（不具有阻塞等待功能）

*  **removeFirst**

E removeFirst();

移出队首的第一个元素，即队列的第一个元素。如果队列为空没有元素可以移出时，抛出**NoSuchElementException**异常。

*  **removeLast**

E removeLast();

移出队尾的第一个元素，即队列的最后一个元素。如果队列为空没有元素可以移出时，抛出NoSuchElementException异常。

*  **pollFirst**

E pollFirst();

移出队首的第一个元素，当队列为空没有元素可以移出的时候，返回null。

*  **pollLast**

E pollLast();

移出队尾的第一个元素，当队列为空没有元素可以移出的时候，返回null。

*  **remove**

E remove();

移出队首的第一个元素，如果队列为空，则抛出NoSuchElementException。该方法等价于removeFirst。

*  **poll**

E poll();

移出队首的第一个元素，如果队列为空，返回null，该方法等价于pollFirst方法。

*  **removeFirstOccurrence**

boolean removeFirstOccurrence(Object o);

指定一个元素o，如果该元素o存在于队列中，则从队首开始，移出第一个与元素o匹配的元素，并返回true。如果队列中不存在该元素o，则不做操作，返回false。通过调用equals查看是否匹配。

*  **removeLastOccurrence**

boolean removeLastOccurrence(Object o);

与removeFirstOccurrence相似，不过该方法是从队尾开始的。

*  **remove(Object o)**

boolean remove(Object o);

该方法等价于removeFirstOccurrence。

**（3）**查看队首、队尾元素

*  **getFirst**

E getFirst();

查看队首的第一个元素，该操作只查看，但不会移出元素。如果队列为空，则抛出NoSuchElementException

*  **getLast**

E getLast();

查看队尾的第一个元素，该操作只查看，但不会移出元素。如果队列为空，则抛出NoSuchElementException

*  **peekFirst**

E peekFirst();

查看队首的第一个元素。如果队列为空，则返回null。

*  **peekLast**

E peekLast();

查看队尾的第一个元素。如果队列为空，则返回null。

*  **element**

E element();

查看队首的第一个元素，如果队列为空，抛出NoSuchElementException异常。该方法等价于getFirst方法。

*  **peek**

E peek();

查看队首的第一个元素，如果队列为空，返回null。该方法等价于peekFirst。

*  **contains**

boolean contains(Object o);

查看队列中是否存在指定的元素。如果存在，则返回true。

**（4）**其他方法

*  **size**

public int size();

查看队列中元素的个数。

*  **iterator**

Iterator<E> iterator();

队列的迭代器。迭代顺序为从队首到队尾。

*  **descendingIterator**

Iterator<E> descendingIterator();

队列的迭代器。迭代顺序为从队尾到队首。

--------------------

Deque继承了Queue，而Queue这种数据结构具有先进先出（FIFO）的特点，因此Deque在实现继承自Queue的这些方法的时候也要兼顾队列先进先出的特点。所以向队列中添加元素的方法（如**add**、**offer**等）都是向Deque的队尾添加元素，而从队列中移出元素的方法（如**remove**、**poll**等）都是移出Deque的队首的元素。向这样向队尾添加元素，从队首移出元素就保证了队列的先进先出的特点。

--------------------

# **█ **BlockingDeque #

阻塞双端队列。在双端队列的基础上，添加了具有阻塞功能的方法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 1][]

**BlockingDeque**不仅继承了Deque，而且还继承了BlockingQueue，其具有BlockingQueue的相关功能。*（关于BlockingQueue的相关介绍，请戳《[BlockingQueue初识][BlockingQueue]》）*

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 2][]

### 方法： ###

在BlockingDeque中一些方法是复制自父类Deque中定义的方法，该部分的方法在前面介绍Deque的时候已经介绍过了。这里只介绍在BlockingDeque中扩展出来的方法。

**（1）**向队列中添加元素（具有阻塞等待功能）

*  **putFirst**

void putFirst(E e) throws InterruptedException;

向队首添加元素，当队列满了没有足够的空间可以继续添加元素的时候，该方法会一直阻塞等待，直到队列中有空间可以添加该元素了。

*  **putLast**

void putLast(E e) throws InterruptedException;

与putFirst相似，不同在于其向队尾添加元素。当队列满了时的行为与putFirst相同。

*  **offerFirst**

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

向队首添加元素。当队列满了无法继续添加元素时，该方法可以定义超时等待时间。在超过了定义的超时等待时长，如果队列还没有足够的空间来插入该元素，元素入队失败，返回false。

*  **offerLast**

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

向队尾添加元素。当队列满了时，行为与offerFirst相同。

**（2）**从队列中移出元素（具有阻塞等待功能）

*  **takeFirst**

E takeFirst() throws InterruptedException;

移出队首的第一个元素。当队列为空没有元素可以移出的时候，该方法会一直阻塞等待，直到可以有元素可以移出。

*  **takeLast**

E takeLast() throws InterruptedException;

与takeFirst相似，不同在于其是移出队尾的第一个元素。

*  **pollFirst**

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

具有超时等待功能的移出队首第一个元素。在超过定义的超时等待时长，如果还没有元素可以，则返回null。

*  **pollLast**

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

与pollFirst相似，不同在于其移出队尾的第一个元素。

--------------------

# **█ 补充** #

**1、**元素存放方式?

BlockingDeque与Deque定义了相关功能的方法行为约束，子类在实现BlockingDeque接口的时候，要遵循约束去实现。在关于入队、出队有以下几个需要思考的地方，也就是实现方式不同。（以数组为例的存放方式）

**（1）**以队列中间为分界线，队首和队尾两端都存放元素。

虚线为分界线，分别向队首添加A、B，向队尾添加Z、Y。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 3][]

**（2）**以队首为一端存放元素，从队首添加和从队尾添加只是入队的方向不同。

从队首添加A、B，从队尾添加Z、Y

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 4][]

关于JDK中实现的BlockingDeque子类是如何存放元素的，我们将在BlockingDeque的实现类**LinkedBlockingDeque**中查看。

**2、**队列和栈

**（1）**在前面介绍Deque的时候已经说过，因为Deque继承了Queue，所以在使用继承自Queue的方法的时候去向队列中添加元素、从队列中移除元素，这些方法是满足队列的先进先出的特点的，因此Deque也是一种队列。

**（2）**使用Deque自定义实现队列

队列的特点是先进先出，所以可以使用具有添加元素功能的xxLast等方法向队尾添加元素，使用具有移出元素功能的xxFirst等方法从队首移出元素。（出队和入队的方向相反，即从不同的方法入队、出队）

**（3）**使用deque自定义实现栈

栈的特点是后进先出（LIFO），所以可以使用具有添加元素功能的xxFirst等方法向队首添加元素，使用具有移出元素功能的xxFirst等方法从队首移出元素。（出队和入队的方向相同，即从同一个方法入队、出队）

[BlockingQueue]: https://blog.csdn.net/weixin_50518271/article/details/117789512?spm=1001.2014.3001.5501
[20210728212024813.png]: /images/20220829/c4a210bad5d547c7923e0fcf043791fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70]: /images/20220829/94328e2e7a594822a9488e09943a6635.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/3d264e81d2944e78a805c0eb2c2f7988.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 2]: /images/20220829/e06851af9f0c4bfda923ddcfcbbf8bd5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 3]: /images/20220829/15ffff38fa0b4b108b8e2b4df0dbcd3a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 4]: /images/20220829/b1401be5c55d48dda0115d4bc5eba56d.png