Java7种常见队列

以你之姓@ 2024-03-22 14:26 38阅读 0赞

##### LinkedBlockingQueue #####

###### 特点 ######

1.线程安全：多个线程同时访问队列时不会出现数据错乱

2.阻塞队列：队列已满时，插入操作会被阻塞等待；队列为空时，取出操作会被阻塞等待

3.无界队列：如果不指定容量大小，就是一个无界队列，可以一直添加元素

4.可以实现生产者消费者模型：多个生产者线程可以往队列中添加元素，多个消费者线程可以从队列中取出元素，可以实现生产者消费模型

###### 底层 ######

使用链表实现的无界队列。其内部有一个头节点和一个尾节点，在插入和删除元素时会对头尾节点进行操作。具体来说，插入元素的操作会将新元素添加到尾节点的后面，并修改尾结点指向；删除元素的操作会从头结点的后一个位置开始删除，并修改头节点指向。由于是链表实现的，LinkedBlockingQueue理论上可以容纳无限数量的元素。  
使用锁和条件变量来实现线程间的同步。当队列满时，插入操作会被阻塞并进入等待队列。只有当另一个线程往队列中插入了一个元素时，阻塞的插入操作线程才会被唤醒，继续执行操作；同理当另一个线程从队列中取出了一个元素时，阻塞的取出的操作线程才会被唤醒，继续执行。

##### ArrayBlockingQueue #####

###### 特点 ######

1.固定大小：在创建时需要指定队列的容量，之后队列的大小就不能再进行扩展了

2.阻塞操作：当队列已满时，后续插入操作会被阻塞，直到队列中有空间可以放置元素。同样地，当队列为空时，后序的取出操作也会被阻塞，直到队列中有可用的元素。

3.线程安全：多个线程可以同时对队列进行读写操作，而不会引发静态条件等线程安全问题

###### 底层 ######

使用数组实现的有界队列，数组中保存队列元素的值。它同时使用了一个锁和两个条件变量来实现线程之间的同步。当队列满时，插入操作会阻塞并进入等待队列；当队列为空时，取出操作会阻塞并进入等待队列。只有当另一个线程从队列中去除了一个元素时，阻塞的线程才会被唤醒，继续执行操作。这样可以避免忙等待带来的CPU资源浪费，提高了效率

##### SynchronousQueue #####

###### 特点 ######

1.大小为0：容量为0，即它不会保存任何元素

2.阻塞操作：没有任何元素时，插入和取出操作都会被阻塞，直到另外一个线程来执行相应的取出或插入操作

3.零容错：如果没有其它线程等待并准备好进行各自需要的操作，则插入操作的返回值为false，取出操作则返回null

###### 底层 ######

通过一种称为"transfer"机制来实现线程间同步的，这种机制可以让两个线程直接交换元素。在插入或删除元素时，如果队列为空，则将当前线程加入等待队列中，并挂起该线程；如果队列不为空，则从等待队列中选择一个线程（通常是等待时间最长的）进行交换。  
其中，每个等待操作都会创建一个节点，节点之间形成一个链表结构。当产生匹配的插入和删除操作时，相应的等待操作的节点会被唤醒，并被连接到执行操作的节点上，以完成数据提交和接受。

需要注意的是SynchronousQueue的插入和删除操作是成对出现的，在这两个操作中至少由一个操作完成前，线程会一直阻塞等待。同时，SynchronousQueue没有任何容量限制，只要还有线程在尝试往队列中添加元素，它就无限制地正常

##### PriorityBlockingQueue #####

###### 特点 ######

###### 1.有序性：保证了每次取出的元素都是当前队列中优先级最高的元素 ######

2.阻塞操作：当队列为空时，取出操作会被阻塞，直到队列不再为空；当队列已满时，插入操作也会被阻塞，直到队列可以容纳插入元素

3.线程安全：内部使用了锁和条件变量来实现线程间同步，可以被多个线程同时访问而不会发生数据竞争或者其他线程安全问题。

需要对每个元素定义一个优先级，，这个优先级可以通过Coparator来进行定义，在默认情况下元素会按照其自然次序进行排序（例如数字按升序排列，字符串按字典序排列等）。每次插入操作都会将新元素插入到合适的位置，并重新调整队列中元素的顺序可以维护有序性，因此相比于普通队列，它具有更高的开销

###### 底层 ######

是基于一个堆数据结构实现的，堆是一种具有有序特性的树形数据结构。堆被用来维护队列的有序性，并确保每次去除元素都是当前优先级最高的元素。  
使用ReentrantLock来保证线程安全，并使用Condition来实现阻塞操作。在添加元素时，如果队列已满，则插入操作会阻塞，并等待其他线程取出元素以空出空间。在删除元素时，如果队列为空，则删除操作会阻塞，并等待其他线程王队列中添加元素。

核心方法是siftUp和siftDown，这两个方法用来调用整堆的结构以满足有序性。在插入元素时，新元素被加到堆的底部，然后通过siftUp方法向上调整位置，直到达到合适位置位置；在取出元素时，堆顶元素被删除并返回，然后将堆底部的元素放到堆顶位置，再通过sifDown方向向下调整位置，直到达到合适位置位置。这样就实现了有序性，而且操作效率高

##### DelayQueue #####

###### 特性 ######

###### 1.有序性：是一个有序队列，其中元素根据其到期时间进行排序，从而保证了每次去除的元素都是已经到期的元素 ######

2.延迟操作：可以实现延迟操作，即元素插入到队列中时可以指定一个过期时间，在这个时间之前元素不可取出，只能被保存在队列中等待到期

3.线程安全：内部使用了锁和条件变量来实现线程间同步，可以被多个线程同时访问而不会发生数据竞争或其他线程安全问题

在使用DelayQueue时，需要为每个元素定义一个过期时间，在插入元素时，DelayQueue会根据过期时间对元素进行排序，并按照优先级从小到大依次放入队列中。当使用take方法获取队头元素时，如果此时队头元素尚未到期，则take方法会被阻塞知道元素到期；如果队列为空，则take方法也会被阻塞，知道队列中有新的元素插入。

适合实现任务调度和超时控制功能。我们可以将需要延迟执行的任务封装成Delayed对象，并将其插入到队列中，在使用take方法获取队头元素时，如果此时队头元素已经到期，则可以取出该任务执行；否则重新放回队列中等待下次执行。通过这种方法，我们可以实现非常精确的任务调度和超时控制功能，使得程序的运行更加严谨和可靠

###### 底层 ######

是基于一个PriorityQueue和一个等待队列(WaitQueue)实现的

##### LinkedTransferQueue #####

###### 特点 ######

1.支持高并发：采用无锁算法、分离锁等方式来实现高效的并发操作支持。另外该队列还是用了一些辅助线程进行帮助性操作，如在添加元素时动态创建内部节点以优化性能

2.双向通道：相比于普通的阻塞队列，它不仅支持传统的put、task等操作，还提供了Transfer方法，该方法可以实现一个双向通道，可以在两个线程之间直接进行数据传输。其中，Transfer方法将阻塞当前线程，直到有其他线程调用了对应的receive方法才会唤醒，保证了数据的及时传输

3.无界队列：基于链表实现的是一个无界队列，可以在队列中持续添加元素而不必担心队列满的情况

公平性：使用公平锁来保证线程获取元素的顺序与插入元素的顺序一致

总结：它是一种高性能且灵活的队列类型，可以在多个线程之间快速通信。它结合了传统的生产者-消费者模型和直接传递模式，使得线程间的数据传输更加便捷和高效，并且支持公平性和无锁算法等特性，使得高并发环境中也能够保证其稳定性和可靠性。

###### 底层 ######

是基于一个链表实现的，其中每个结点都定义了一个等待列表，用于保存等待接受的线程

##### LinkedBlockingDeque #####