【集合】Queue

Myth丶恋晨 2022-11-26 08:55 216阅读 0赞

**目录**

一、Queue 概念

二、常见的Queue 解析

2.2 ArrayBlockingQueue

2.2.1 概念

2.2.2 特点

2.2.3 常用方法

2.2.4 结构和源码分析

2.3 LinkedBlockingQueue

2.3.1 概念

2.3.2 常用方法

2.3.3 关键点

2.4 ArrayBlockingQueue 和 LinkedBlockingQueue 对比

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

# 一、Queue 概念 #

Queue 是一种先进先出的结构，是线程安全的

# 二、常见的Queue 解析 #

## 2.2 ArrayBlockingQueue ##

### 2.2.1 概念 ###

ArrayBlockingQueue 是一个数组结构的有界阻塞队列

### 2.2.2 特点 ###

*  线程安全
 *  初始化时必须指定大小

### 2.2.3 常用方法 ###

<table> 
 <tbody> 
  <tr> 
   <td><strong>方法名</strong></td> 
   <td><strong>描述</strong></td> 
   <td><strong>临界行为</strong></td> 
  </tr> 
  <tr> 
   <td colspan="3"><strong>队列尾部添加元素</strong></td> 
  </tr> 
  <tr> 
   <td>add</td> 
   <td>添加一个元素</td> 
   <td>若队列已满，抛出&nbsp;IIIegaISlabEepeplian 异常</td> 
  </tr> 
  <tr> 
   <td>offer</td> 
   <td>添加一个元素</td> 
   <td>若队列已满，返回 false。添加成功则返回 true</td> 
  </tr> 
  <tr> 
   <td>put</td> 
   <td>添加一个元素</td> 
   <td>若队列已满，则阻塞，等待有空闲位置</td> 
  </tr> 
  <tr> 
   <td colspan="3"><strong>队列头部弹出元素</strong></td> 
  </tr> 
  <tr> 
   <td>remove&nbsp;&nbsp;&nbsp;</td> 
   <td>移除并返回头部元素</td> 
   <td>若队列为空，则抛出&nbsp;NoSuchElementException 异常</td> 
  </tr> 
  <tr> 
   <td>poll</td> 
   <td>移除并返回头部元素</td> 
   <td>若队列为空，返回 null</td> 
  </tr> 
  <tr> 
   <td>take</td> 
   <td>移除并返回头部元素</td> 
   <td>若队列为空，则阻塞</td> 
  </tr> 
  <tr> 
   <td colspan="3"><strong>获取队列头部元素(不移除)</strong></td> 
  </tr> 
  <tr> 
   <td>element&nbsp;&nbsp;</td> 
   <td>返回头部元素(不移除)</td> 
   <td>若队列为空，则抛出&nbsp;NoSuchElementException 异常</td> 
  </tr> 
  <tr> 
   <td>peek&nbsp;</td> 
   <td>返回头部元素(不移除)</td> 
   <td>若队列为空，返回 null</td> 
  </tr> 
 </tbody> 
</table>

### 2.2.4 结构和源码分析 ###

查看 ArrayBlockingQueue 的源码，可以发现他的设计关键点：

*  使用一个锁，写入和弹出都需要操作锁对象
 *  数组的容量有限，故内部节点会循环使用，使用一个写指针，和一个存指针，通过不断移动指针来实现存取

**● 结构分析**

**当队列的数组没有满：**

取指针始终指向第一个节点，即arr\[0\]，取指针 takeIndex = 0。

而随着元素被推入队列，存指针始终是下一个要存入数据的数组索引，图中 putIndex = 5。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDE2MzMx_size_16_color_FFFFFF_t_70][]

**当数组被填满时：**

存指针重新移动到了数组第一位，putIndex = 0。

若此时有新元素要入队，根据调用的方法，可能被拒绝或阻塞。阻塞则是使用了 Condition 的方式等待

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDE2MzMx_size_16_color_FFFFFF_t_70 1][]

**此时取走了三个节点：**

当头部元素被弹出后，取指针也会不断后移，始终保存入对时间最长的元素的索引

如图中，数组中的 0 ,1,2 都被弹出了，取指针索引指向了3

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDE2MzMx_size_16_color_FFFFFF_t_70 2][]

**若原本有要入队的元素被阻塞，或是有新元素要入队：**

由于存指针已经到了数组末尾，为了循环利用，则重新指向函数头。如插入了一个元素，则重新插入到 arr\[0\]的位置，且

修改存指针 putIndex = 1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDE2MzMx_size_16_color_FFFFFF_t_70 3][]

● **查看源码，列出关键属性**

![20200811155841817.png][]

![20200811160631680.png][]

![20200811160707980.png][]

![20200811160756770.png][]

![20200811160844760.png][]

## 2.3 LinkedBlockingQueue ##

### 2.3.1 概念 ###

LinkedBlockingQueue 是一种链表结构的阻塞队列，若在初始化时定义了容量，则为有界阻塞队列，反之则为无界阻塞队列。

### 2.3.2 常用方法 ###

<table> 
 <tbody> 
  <tr> 
   <td><strong>方法名</strong></td> 
   <td><strong>描述</strong></td> 
   <td><strong>临界行为</strong></td> 
  </tr> 
  <tr> 
   <td colspan="3"><strong>队列尾部添加元素</strong></td> 
  </tr> 
  <tr> 
   <td>add</td> 
   <td>添加一个元素</td> 
   <td>若队列已满，抛出&nbsp;IIIegaISlabEepeplian 异常</td> 
  </tr> 
  <tr> 
   <td>offer</td> 
   <td>添加一个元素</td> 
   <td>若队列已满，返回 false。添加成功则返回 true</td> 
  </tr> 
  <tr> 
   <td>put</td> 
   <td>添加一个元素</td> 
   <td>若队列已满，则阻塞，等待有空闲位置</td> 
  </tr> 
  <tr> 
   <td colspan="3"><strong>队列头部弹出元素</strong></td> 
  </tr> 
  <tr> 
   <td>remove&nbsp;&nbsp;&nbsp;</td> 
   <td>移除并返回头部元素</td> 
   <td>若队列为空，则抛出&nbsp;NoSuchElementException 异常</td> 
  </tr> 
  <tr> 
   <td>remove(Object o)</td> 
   <td>移除指定元素</td> 
   <td>若队列为空，则抛出&nbsp;NoSuchElementException 异常</td> 
  </tr> 
  <tr> 
   <td>poll</td> 
   <td>移除并返回头部元素</td> 
   <td>若队列为空，返回 null</td> 
  </tr> 
  <tr> 
   <td>take</td> 
   <td>移除并返回头部元素</td> 
   <td>若队列为空，则阻塞</td> 
  </tr> 
  <tr> 
   <td colspan="3"><strong>获取队列头部元素(不移除)</strong></td> 
  </tr> 
  <tr> 
   <td>element&nbsp;&nbsp;</td> 
   <td>返回头部元素(不移除)</td> 
   <td>若队列为空，则抛出&nbsp;NoSuchElementException 异常</td> 
  </tr> 
  <tr> 
   <td>peek&nbsp;</td> 
   <td>返回头部元素(不移除)</td> 
   <td>若队列为空，返回 null</td> 
  </tr> 
 </tbody> 
</table>

### 2.3.3 关键点 ###

查看 LinkedBlockingQueue 的源码，发现设计关键点有：

*  使用了两个锁，分别为入队锁和出队锁，这使得其并发效率高于 ArrayBlockingQueue
 *  若是不指定队列容量，则会变成无界队列(即Integet,MAX\_VALUE)，当出队速度小于入队速度时可能造成内存溢出(OOM)
 *  节点是在添加节点时动态分配的，后期需要GC回收
 *  在入队时使用入队锁，在出队时使用出队锁，但是在删除节点等操作时，同时会锁定出队锁和入队锁

## 2.4 ArrayBlockingQueue 和 LinkedBlockingQueue 对比 ##

● **底层实现不同**

ArrayBlockingQueue 内部是用数组实现的

LinkedBlockingQueue 内部是用链表实现的

**● 锁机制不同**

ArrayBlockingQueue 只有一个锁，出队和入队都要操作这个锁

而 LinkedBlockingQueue 有入队锁和出队锁，实现了锁分离，入队操作和出队操作互不影响，并发性更高

● **队列大小不同**

ArrayBlockingQueue 是有界队列，初始化时必须指定容量，内部通过循环使用数组节点的方式

而 LinkedBlockingQueue 若是在初始化时指定了容量，则是有界队列，若不指定，则是无界队列(size = Integet.MAX\_VALUE)

● **并发性能不同**

LinkedBlockingQueue 实现了入队锁、出队锁分离，而ArrayBlockingQueue 入队出队都竞争同一把锁，故 LinkedBlockingQueue 并发效率更高

● **内存消耗不同**

ArrayBlockingQueue 在初始化时已经开辟好了内存空间，使用过程中无需再动态申请存储空间

而 LinkedBlockingQueue 的节点的存储空间都是动态分配的，会增加 gc 回收的负担

● **吞吐量**

由于 LinkedBlockingQueue 是无界队列，在大流量到来时能够存储更多的节点，且实现了锁分离，入队出队互不影响，故吞吐量高于ArrayBlockingQueue

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDE2MzMx_size_16_color_FFFFFF_t_70]: /images/20221124/93693eac62824200a610671129c1bb15.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDE2MzMx_size_16_color_FFFFFF_t_70 1]: /images/20221124/8d0018de095e40ca9e8432f620754535.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDE2MzMx_size_16_color_FFFFFF_t_70 2]: /images/20221124/d89cac25a62d43b18852501792f2577d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDE2MzMx_size_16_color_FFFFFF_t_70 3]: /images/20221124/0322caa852dd49df9b6ff7957ea46d32.png
[20200811155841817.png]: /images/20221124/8ab0e036a8624de58a87775cd413b09e.png
[20200811160631680.png]: /images/20221124/ece716ce97434c94b9d7db4cc821bf0d.png
[20200811160707980.png]: /images/20221124/968c1f1582be4f3bbf9956fee7465590.png
[20200811160756770.png]: /images/20221124/28b2da41814d478ca349501d2ca4fc26.png
[20200811160844760.png]: /images/20221124/788edb6ba6c546ce8b1670cdf16d37e5.png