JAVA集合类--几种特殊的Queue

时间：2022-10-10 17:03:25

优先级队列

优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。
*的定义也可以看看： https://en.wikipedia.org/wiki/Priority_queue

JAVA语言对优先级队列的支持

实现方式

查看JDK源码，可以发现 
    public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }
优先级队列的每个元素都需要实现Comparator接口，也就是可以排序的
JAVA基本数据类型的包装类和String类型都实现了这个接口
关于对象的排序，请参考 JAVA基础之对象的排序
关于优先级队列的具体实现，这里不想谈，一般是使用堆这种数据结构

API

这里我们中点区分下面几个方法 
public boolean add(E e) {return offer(e);}//这两个方法没有区别，将指定的元素插入此优先级队列。

JAVA集合类--几种特殊的Queue

双端队列

基本概念与基本方法

双端队列是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。 
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
双端队列具有栈和队列的双重特性
JAVA集合类--几种特殊的Queue
JAVA集合类--几种特殊的Queue

一个小问题

阻塞队列

      阻塞队列与普通队列的区别在于，当队列是空的时，从队列中获取元素的操作将会被阻塞，或者当队列是满时，往队列里添加元素的操作会被阻塞。试图从空的阻塞队列中获取元素的线程将会被阻塞，直到其他的线程往空的队列插入新的元素。同样，试图往已满的阻塞队列中添加新元素的线程同样也会被阻塞，直到其他的线程使队列重新变得空闲起来  
一个常见的应用是生产者-消费者问题

 BlockingQueue是个接口，有如下实现类：
       1. ArrayBlockQueue：一个由数组支持的有界阻塞队列。此队列按 FIFO（先进先出）原则对元素进行排序。创建其对象必须明确大小，像数组一样。
       2. LinkedBlockQueue：一个可改变大小的阻塞队列。此队列按 FIFO（先进先出）原则对元素进行排序。创建其对象如果没有明确大小，默认值是Integer.MAX_VALUE。链接队列的吞吐量通常要高于基于数组的队列，但是在大多数并发应用程序中，其可预知的性能要低。 


       3. PriorityBlockingQueue：类似于LinkedBlockingQueue，但其所含对象的排序不是FIFO，而是依据对象的自然排序顺序或者是构造函数所带的Comparator决定的顺序。


       4. SynchronousQueue：同步队列。同步队列没有任何容量，每个插入必须等待另一个线程移除，反之亦然。

标签：

相关文章