Java中的常用队列

我就是我 2024-04-27 15:39 1阅读 0赞

🏆今日学习目标：

🍀Java中的常用队列  
✅创作者：林在闪闪发光  
⏰预计时间：30分钟  
🎉个人主页：[林在闪闪发光的个人主页][Link 1]

🍁林在闪闪发光的个人社区，欢迎你的加入: [林在闪闪发光的社区][Link 2]

**目录**

一 什么是队列

java 队列接口继承图

二 java队列分类

三 阻塞队列

3.2.阻塞队列的特点

3.3.阻塞队列常用方法

4.3 常见的阻塞队列

4.3.1 ArrayBlockingQueue

4.3.2 LinkedBlockingQueue

4.3.3 SynchronousQueue

4.4.4 PriorityBlockingQueue

4.4.5 DelayQueue

五 非阻塞队列

ConcurrentLinkedQueue

队列常用方法

有界和无界

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

## 一 什么是队列 ##

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

![2b311a4646ed4eed984c7c981521347d.png][]

## java 队列接口继承图 ##

![ded66c769a9040d6ae8a98069c1a722f.png][]

## 二 java队列分类 ##

队列主要分为阻塞和非阻塞，有界和无界、单向链表和[双向链表][Link 3]之分；

![597ebcb2d08849d7ab82d3ce16a1228b.png][]

## 三 阻塞队列 ##

阻塞队列--[BlockingQueue][]，它是一个接口

public interface BlockingQueue<E> extends Queue<E>

BlcokingQueue继承了Queue接口，是队列的一种，Queue和BlockingQueue都是在Java5中加入的，BlockingQueue是线程安全的，我们在很多场景下都可以利用线程安全的队列来优雅地解决我们业务自身的[线程安全问题][Link 4]。

Java提供的线程安全的队列 主要分为阻塞队列和非阻塞队列俩大类

**阻塞队列**的典型例子就是BlockingQueue接口的实现类，主要有6种实现：ArrayBlcokingQueue,LinkedBlockingQueue,SynchronousQueue,DelayQueue,PriorityBlockingQueue和LinkedTransherQueue,它们各自有不同不同的特点。  
**非阻塞并发队列**最典型的就是ConcurrentLinkedQueue，这个类不会让线程阻塞，利用CAS保证了线程安全。

#### 3.2.阻塞队列的特点 ####

阻塞队列的特点就是阻塞两个字，哈哈哈哈。像是废话。阻塞功能使得生产者和消费者两端的能力得以平衡，当有任何一端速度过快时，阻塞队列便会把过快的速度降下来。最重要的两个方法：take()和put()；  
**take()**  
take方法的功能是获取并移除队列的头节点，通常在队列里有数据的时候是可以正常移除的，当队列里无数据，则阻塞，直到队列里面有数据。一旦有数据了，就立刻解除阻塞状态，并且获取到数据 put()  
put方法插入元素时，如果队列没有满可以正常插入，如果队列满了，则阻塞，直到队列里面有了空闲空间，就会消除阻塞状态，并把数据添加进去。

阻塞队列容量问题

阻塞队列分为两种有界和无界。无界队列意味着里面可以容纳非常多的元素，例如LinkedBlcokingQueue的上限是Integer.MAX\_VALUE。学过Java的人都知道这个数其实挺大的。但有界队列例如ArrayBlockingQueue如果队列满了，也不会扩容

#### 3.3.阻塞队列常用方法 ####

在阻塞队列中有很多方法，而且都非常相似，这里我把常用的8个方法总结了一下以添加、删除为主。主要分为三类：

*  抛出异常：add、remove、element
 *  返回结果但是不抛出异常：offer、poll、peek、
 *  阻塞：take、put、

#### 4.3 常见的阻塞队列 ####

#### 4.3.1 ArrayBlockingQueue ####

ArrayBlockingQueue是最典型的有界队列，其内部是用数组存储元素的，利用Reentrant实现线程安全

public ArrayBlockingQueue(int capacity) {
       this(capacity, false);
    }
     
    public ArrayBlockingQueue(int capacity, boolean fair) {
       if (capacity <= 0)
           throw new IllegalArgumentException();
       this.items = new Object[capacity];
       lock = new ReentrantLock(fair);
       notEmpty = lock.newCondition();
       notFull =  lock.newCondition();
    }

我们在创建它的时候就需要指定它的容量，之后也不可以在扩容了，在构造函数中我们同样可以指定是否是公平的。如果ArrayBlockingQueue被设置为非公平的，那么就存在插队的可能；如果设置为公平的，那么等待了最长时间的线程会优先被处理，其它线程不允许插队。

#### 4.3.2 LinkedBlockingQueue ####

LinkedBlockingQueue内部使用链表实现的，如果我们不指定它的初始容量，那么它的默认容量就为整形的最大值Integer.MAX\_VALUE,由于这个数特别特别的大，所以它也被称为无界队列。

#### 4.3.3 SynchronousQueue ####

SynchronousQueue最大的不同之处在于，它的容量不同，所以没有地方来暂存元素，导致每次取数据都要先阻塞，直到有数据放入；同理，每次放数据的时候也会阻塞，直到有消费者来取。SynchronousQueue的容量不是1而是0，因为SynchronousQueue不需要去持有元素，它做的就是直接传递。

#### 4.4.4 PriorityBlockingQueue ####

PriorityBlockingQueue是一个支持优先级的无界阻塞队列，可以通过自定义类实现compareTo()方法来制定元素排序规则，或者初始化时通过构造器参数Comparator来制定排序规则。同时，插入队列的对象必须是可比较大小的，也就是Comparable的，否则就会抛出ClasscastException异常。  
它的take方法在队列为空时会阻塞，但是正因为它是无界队列，而且会自动扩容，所以它的队列永远不会满，所以它的put()方法永远不会阻塞，添加操作始终都会成功。

#### 4.4.5 DelayQueue ####

Delay这个队列比较特殊，具有延迟的功能，我们可以设定在队列中的任务延迟多久之后执行。它是无界队列，但是放入的元素必须实现Delayed接口，而Delayed接口又继承了Comparable接口，所以自然就拥有了比较和排序的能力.

public interface Delayed extends Comparable<Delayed> {
     
        /**
         * Returns the remaining delay associated with this object, in the
         * given time unit.
         *
         * @param unit the time unit
         * @return the remaining delay; zero or negative values indicate
         * that the delay has already elapsed
         */
        long getDelay(TimeUnit unit);
    }

可以看出这个Delayed接口继承自Comparable，里面需要涉嫌getDelay.这里的getDelay方法返回的是还剩下多长的延迟时间才会被执行。如果返回0或者负数则代表任务已过期。元素会根据延迟时间的长短被放到队列的不同位置，越靠近队列头代表越早过期。

## 五 非阻塞队列 ##

基于锁的算法会带来一些活跃度失败的风险。如果线程在持有锁的时候因为阻塞I/O、页面错误、或其他原因发生延迟，很可能所有的线程都不能工作了。一个线程的失败或挂起不应该影响其他线程的失败或挂起，这样的算法称为非阻塞算法；如果算法的每一个步骤中都有一些线程能够继续执行，那么这样的算法称为锁自由（lock-free）算法。在线程间使用CAS进行协调，这样的算法如果能构建正确的话，它既是非阻塞的，又是锁自由的。java中提供了基于CAS非阻塞算法实现的队列，比较有代表性的有ConcurrentLinkedQueue和LinkedTransferQueue，它们的性能一般比阻塞队列的好。

#### ConcurrentLinkedQueue ####

public boolean offer(E e) {
        checkNotNull(e);
        final Node<E> newNode = new Node<E>(e);
     
        for (Node<E> t = tail, p = t;;) {
            Node<E> q = p.next;
            if (q == null) {
                // p is last node
                if (p.casNext(null, newNode)) {
                    // Successful CAS is the linearization point
                    // for e to become an element of this queue,
                    // and for newNode to become "live".
                    if (p != t) // hop two nodes at a time
                        casTail(t, newNode);  // Failure is OK.
                    return true;
                }
                // Lost CAS race to another thread; re-read next
            }
            else if (p == q)
                // We have fallen off list.  If tail is unchanged, it
                // will also be off-list, in which case we need to
                // jump to head, from which all live nodes are always
                // reachable.  Else the new tail is a better bet.
                p = (t != (t = tail)) ? t : head;
            else
                // Check for tail updates after two hops.
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }

通过源码我们可以清晰的看出，非阻塞队列ConcurrentLinkedQueue它的主要流程就是在判空以后，会进入一个大循环中，p.casNext()方法，这个方法正是利用了CAS来操作的，这个死循环去配合CAS其实就是我们平时说的乐观锁的思想。其实非阻塞队列ConcurrentLickedQueue使用CAS非阻塞算法+不停重试的实际来实现线程安全的.

**LinkedTransferQueue**

jdk7才提供这个类，这个类实现了TransferQueue接口，也是基于链表的，对于所有给定的生产者都是先入先出的。与其他阻塞队列的区别是：其他阻塞队列，生产者生产数据，如果队列没有满，放下数据就走，消费者获取数据，看到有数据获取数据就走。而LinkedTransferQueue生产者放数据的时候，如果此时消费者没有获取，则需阻塞等待直到有消费者过来获取数据。有点类似SynchronousQueue，但是LinkedTransferQueue是被设计有容量的。LinkedTransferQueue 通过使用CAS来实现并发控制，是一个无界的安全队列。其长度可以无限延伸，当然带来的问题也是显而易见的。

## 队列常用方法 ##

>   
> 　　**add** 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常  
> 　　**remove** 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常  
> 　　**element** 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常  
> 　　**offer** 添加一个元素并返回true 如果队列已满，则返回false  
> 　　**poll** 移除并返问队列头部的元素 如果队列为空，则返回null  
> 　　**peek** 返回队列头部的元素 如果队列为空，则返回null  
> 　　**put** 添加一个元素 如果队列满，则阻塞  
> 　　**take** 移除并返回队列头部的元素 如果队列为空，则阻塞  
>  **drainTo(list)** 一次性取出队列所有元素

**知识点： remove、element、offer 、poll、peek 其实是属于Queue接口。**

> #### 有界和无界 ####
> 
> **有界**：有界限，大小长度受限制  
>  **无界**：无限大小，其实说是无限大小，其实是有界限的，只不过超过界限时就会进行扩容，就行ArrayList 一样，在内部动态扩容

![94ebab4bf1694c53a434bb10918ad99e.png][]

[Link 1]: https://blog.csdn.net/weixin_68829137?type=blog
[Link 2]: https://bbs.csdn.net/forums/947a8b4d170b4a8f8d6bbfbf524c1a1e?spm=1001.2014.3001.6682
[2b311a4646ed4eed984c7c981521347d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/2b78c52144b54c6d8272909d28587249.png
[ded66c769a9040d6ae8a98069c1a722f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/424b0a867431422782ef14439b82ec21.png
[Link 3]: https://so.csdn.net/so/search?q=%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8&spm=1001.2101.3001.7020
[597ebcb2d08849d7ab82d3ce16a1228b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/5f8d40ed8a654550b5bb23c4ea6c6363.png
[BlockingQueue]: https://so.csdn.net/so/search?q=BlockingQueue&spm=1001.2101.3001.7020
[Link 4]: https://so.csdn.net/so/search?q=%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%E9%97%AE%E9%A2%98&spm=1001.2101.3001.7020
[94ebab4bf1694c53a434bb10918ad99e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/09b1fe05bc78468da1cdd019b4dbfe29.png