从零开始自己动手写阻塞队列

小咪咪 2024-04-08 13:52 82阅读 0赞

![038e1acc0733485a85601975dd73d3c6.png][]

### 前言 ###

在我们平时编程的时候一个很重要的工具就是容器，在本篇文章当中主要给大家介绍阻塞队列的原理，并且在了解原理之后自己动手实现一个低配版的阻塞队列。

### 需求分析 ###

在前面的两篇文章[ArrayDeque（JDK双端队列）源码深度剖析][ArrayDeque_JDK]和[深入剖析（JDK）ArrayQueue源码][JDK_ArrayQueue]当中我们仔细介绍了队列的原理，如果大家感兴趣可以查看一下！

而在本篇文章所谈到的阻塞队列当中，是在并发的情况下使用的，上面所谈到的是队列是**并发不安全**的，但是阻塞队列在并发下情况是安全的。阻塞队列的主要的需求如下：

*  队列基础的功能需要有，往队列当中放数据，从队列当中取数据。
 *  所有的队列操作都要是**并发安全**的。
 *  当队列满了之后再往队列当中放数据的时候，线程需要被挂起，当队列当中的数据被取出，让队列当中有空间的时候线程需要被唤醒。
 *  当队列空了之后再往队列当中取数据的时候，线程需要被挂起，当有线程往队列当中加入数据的时候被挂起的线程需要被唤醒。
 *  在我们实现的队列当中我们使用数组去存储数据，因此在构造函数当中需要提供数组的初始大小，设置用多大的数组。

### 阻塞队列实现原理 ###

#### 线程阻塞和唤醒 ####

在上面我们已经谈到了阻塞队列是**并发安全**的，而且我们还有将线程唤醒和阻塞的需求，因此我们可以选择可重入锁`ReentrantLock`保证并发安全，但是我们还需要将线程唤醒和阻塞，因此我们可以选择条件变量`Condition`进行线程的唤醒和阻塞操作，在`Condition`当中我们将会使用到的，主要有以下两个函数：

*  `signal`用于唤醒线程，当一个线程调用`Condition`的`signal`函数的时候就可以唤醒一个被`await`函数阻塞的线程。
 *  `await`用于阻塞线程，当一个线程调用`Condition`的`await`函数的时候这个线程就会阻塞。

#### 数组循环使用 ####

因为队列是一端进一端出，因此队列肯定有头有尾。

![3824e67fd5424012891849873bbed50e.png][]

当我们往队列当中加入一些数据之后，队列的情况可能如下：

![ef76b9a2dff34e0f96e76e799d6b7151.png][]

在上图的基础之上我们在进行四次出队操作，结果如下：

![6848e4ac744c419283170406ec1f69b8.png][]

在上面的状态下，我们继续加入8个数据，那么布局情况如下：

[038e1acc0733485a85601975dd73d3c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/4c834d7008924ab8a1a9217aeb33d8cb.png
[ArrayDeque_JDK]: https://link.juejin.cn?target=https%3A%2F%2Fmp.weixin.qq.com%2Fs%3F__biz%3DMzg3ODgyNDgwNg%3D%3D%26mid%3D2247484612%26idx%3D1%26sn%3D63a5a21fab640619333d9836a000ea44%26chksm%3Dcf0c98cdf87b11db7d63b2d028f0a70ea73e7c84338bce8e7cdf4bee9d5b0c7ec2bf23663233%26token%3D1311889589%26lang%3Dzh_CN%23rd
[JDK_ArrayQueue]: https://link.juejin.cn?target=https%3A%2F%2Fmp.weixin.qq.com%2Fs%3F__biz%3DMzg3ODgyNDgwNg%3D%3D%26mid%3D2247484813%26idx%3D1%26sn%3Dace534e0492bbc9f77b9cf488c7c4edc%26chksm%3Dcf0c9984f87b109210387f71d9591450ead667611351cd6857b7accb6f1fdc02939e12ad0434%26token%3D969171239%26lang%3Dzh_CN%23rd
[3824e67fd5424012891849873bbed50e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/cb123d412c4740639584df9d738fca03.png
[ef76b9a2dff34e0f96e76e799d6b7151.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/705de8e20f2244109a68fa698ded7b17.png
[6848e4ac744c419283170406ec1f69b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c01de8dd66e345faa4836f9777cbe5e4.png