详解 18 种队列，你知道几种？ |
您所在的位置：网站首页 › 模型开发方法有哪几种类型 › 详解 18 种队列，你知道几种？ |
详解 18 种队列，你知道几种？
|
本篇主要内容如下：
本篇主要内容 帮你总结好的阻塞队列：
18种Queue总结 一、Queue自我介绍
队列原理图 1.1 Queue自我介绍hi，大家好，我的英文名叫Queue，中文名叫队列，无论现实生活中还是计算机的世界中，我都是一个很重要的角色哦~ 我是一种数据结构，大家可以把我想象成一个数组，元素从我的一头进入、从另外一头出去，称为FIFO原则（先进先出原则）。 我还有两个亲兄弟：List（列表）、Set（集），他们都是Collection的儿子，我还有一个远房亲戚：Map（映射）。他们都是java.util包这个大家庭的成员哦~ 1.2 现实生活中的场景海底捞排号等位（先排号的优先进餐厅） 邮政员寄送信件（信箱是队列） 1.3 计算机世界中的场景消息队列 RabbitMQ UDP协议（接收端将消息存放在队列中，从队列中读取数据） 二、高屋建瓴，纵览全局18种队列分为三大类： 接口、抽象类、普通类。 弄清楚下面的继承实现关系对后面理解18种队列有很大帮助。
18个Queue的继承实现关系图 Queue接口继承 Collection接口，Collection接口继承 Iterable接口 BlockingQueue接口、Deque接口 继承 Queue接口 AbstractQueue抽象类实现 Queue接口 BlockingDeque接口、TransferQueue接口继承 BlockingQueue接口 BlockingDeque接口继承Deque接口 LinkedBlockingDeque类实现 BlockingDeque接口 LinkedTransferQueue类接口实现 TransferQueue接口 LinkedList类、ArrayDeque类、ConcurrentLinkedDeque类实现 了Deque接口 ArrayBlockingQueue类、LinkendBlockingQueue类、LinkedBlockingDeque类、LinkedTransferQueue类、SynchronousQueue类、PriorityBlockQueue类、DelayQueue类继承 了AbstractQueue抽象类和实现了BlockingQueue接口 PriorityQueue类和ConcurrentLinkedQueue类继承 了AbstractQueue抽象类 注意： Deque：全称Double-Ended queue，表示双端队列。 类实现接口，用implements 接口继承接口，用 extends 类继承类，用extends 三、万物归宗Queue接口 2.1 深入理解Queue接口的本质Queue接口是一种Collection，被设计用于处理之前临时保存在某处的元素。 除了基本的Collection操作之外，队列还提供了额外的插入、提取和检查操作。每一种操作都有两种形式：如果操作失败，则抛出一个异常；如果操作失败，则返回一个特殊值（null或false，取决于是什么操作）。 队列通常是以FIFO（先进先出）的方式排序元素，但是这不是必须的。 只有优先级队列可以根据提供的比较器对元素进行排序或者是采用正常的排序。无论怎么排序，队列的头将通过调用remove()或poll()方法进行移除。在FIFO队列种，所有新的元素被插入到队尾。其他种类的队列可能使用不同的布局来存放元素。 每个Queue必须指定排序属性。 2.2 Queue接口的核心方法总共有3组方法，每一组方法对应两个方法。如下图所示：
Queue的核心方法 动作抛异常返回特殊值Insertadd(e)offer(e)Removeremove()pollExamineelement()peek()（1）比如添加（Insert）元素的动作，会有两种方式：add(e)和offer(e)。如果调用add(e)方法时，添加失败，则会抛异常，而如果调用的是offer(e)方法失败时，则会返回false。offer方法用于异常是正常的情况下使用，比如在有界队列中，优先使用offer方法。假如队列满了，不能添加元素，offer方法返回false，这样我们就知道是队列满了，而不是去handle运行时抛出的异常。 （2）同理，移除（Remove）元素的动作，队列为空时，remove方法抛异常，而poll返回null。如果移除头部的元素成功，则返回移除的元素。 （3）同理，检测（Examine）元素的动作，返回头部元素（最开始加入的元素），但不删除元素， 如果队列为空，则element()方法抛异常，而peek()返回false。 （4）Queue接口没有定义阻塞队列的方法，这些方法在BlockQueue接口中定义了。 （5）Queue实现类通常不允许插入null元素，尽管一些实现类比如LinkedList不禁止插入null，但是还是不建议插入null，因为null也被用在poll方法的特殊返回值，以说明队列不包含元素。 四、双端可用Deque接口 4.1 深入理解Deque接口的原理
双端队列Deque （1）Deque概念： 支持两端元素插入和移除的线性集合。名称deque是双端队列的缩写，通常发音为deck。大多数实现Deque的类，对它们包含的元素的数量没有固定的限制的，支持有界和无界。 （2）Deque方法说明：
Deque方法 说明： 该列表包含包含访问deque两端元素的方法，提供了插入，移除和检查元素的方法。 这些方法种的每一种都存在两种形式：如果操作失败，则会抛出异常，另一种方法返回一个特殊值（null或false，取决于具体操作）。 插入操作的后一种形式专门设计用于容量限制的Deque实现，大多数实现中，插入操作不能失败，所以可以用插入操作的后一种形式。 Deque接口扩展了Queue接口，当使用deque作为队列时，作为FIFO。元素将添加到deque的末尾，并从头开始删除。 作为FIFO时等价于Queue的方法如下表所示：
比如Queue的add方法和Deque的addLast方法等价。 Deque也可以用作LIFO（后进先出）栈，这个接口优于传统的Stack类。当作为栈使用时，元素被push到deque队列的头，而pop也是从队列的头pop出来。 Stack（栈）的方法正好等同于Deque的如下方法：
注意：peek方法不论是作为栈还是队列，都是从队列的检测队列的头，返回最先加入的元素。比如第一次put 100，第二次put 200，则peek返回的是100。如下图所示：
示例代码 4.1 哪些类实现了Deque接口LinkedList类 ArrayDeque类 ConcurrentLinkedDeque类 LinkedBlockingDeque类 4.2 哪些类继承了Deque接口BlockingDeque接口 五、队列骨架AbstractQueue抽象类 5.1 深入理解AbstractQueue抽象类AbstractQueue是一个抽象类，继承了Queue接口，提供了一些Queue操作的骨架实现。
AbstractQueue的方法 方法add、remove、element方法基于offer、poll和peek。也就是说如果不能正常操作，则抛出异常。我们来看下AbstactQueue是怎么做到的。 AbstractQueue的add方法 public boolean add(E e) { if (offer(e)) return true; else throw new IllegalStateException("Queue full"); }AbstractQueue的remove方法 public E remove() { E x = poll(); if (x != null) return x; else throw new NoSuchElementException(); }AbstractQueue的element方法 public E element() { E x = peek(); if (x != null) return x; else throw new NoSuchElementException(); }注意： 如果继承AbstractQueue抽象类则必须保证offer方法不允许null值插入。 5.2 哪些类继承了AbstractQueue抽象类ArrayBlockingQueue类、LinkendBlockingQueue类、LinkedBlockingDeque类、LinkedTransferQueue类、SynchronousQueue类、PriorityBlockQueue类、DelayQueue类继承 了AbstractQueue抽象类 PriorityQueue类和ConcurrentLinkedQueue类继承 了AbstractQueue抽象类 六、阻塞缓冲BlockingQueue接口 6.1 宏观来看BlockingQueue（阻塞队列）BlockQueue满了，PUT操作被阻塞
阻塞队列满了的情况 BlockQueue为空，Take操作被阻塞
阻塞队列为空的情况 （1）BlockingQueue（阻塞队列）也是一种队列，支持阻塞的插入和移除方法。 （3）阻塞的插入：当队列满时，队列会阻塞插入元素的线程，直到队列不满。 （4）阻塞的移除：当队列为空，获取元素的线程会等待队列变为非空。 （5）应用场景：生产者和消费者，生产者线程向队列里添加元素，消费者线程从队列里移除元素，阻塞队列时获取和存放元素的容器。 （6）为什么要用阻塞队列：生产者生产和消费者消费的速率不一样，需要用队列来解决速率差问题，当队列满了或空的时候，则需要阻塞生产或消费动作来解决队列满或空的问题。 6.2 案例解析线程A往阻塞队列（Blocking Queue）中添加元素，而线程B从阻塞队列中移除元素。 当阻塞队列为空的时候 （一个元素都没有），则从队列中获取元素的操作将会被阻塞。 生活中的案例：去海底捞吃火锅的时候，早上8点没人来吃火锅，所以需要等客人过来。 翻译成线程：现在没有元素需要添加，而且阻塞队列为空，所以线程B不需要从队列中拿元素出来，所以线程B获取元素的操作被阻塞了。 当阻塞队列满了的时候 （所有位置都放有元素），则从队列中添加元素的操作将会被阻塞。 生活中的案例：去海底捞吃火锅的时候，人太多了，需要排号，等其他桌空出来了才能进去。 翻译成线程：线程A往阻塞队列中添加元素，将队列填满了，线程B现在正在忙，无法拿出队列中的元素，所以阻塞队列没有地方再放元素了，这个时候线程A添加元素的操作就被阻塞了 6.3 操刀BlockingQueue接口BlockingQueue接口的10个核心方法：
继承的方法 10个核心方法总结如下：
BlockingQueue接口的10个核心方法 有三大类操作：插入、移除、检查。 插入有四种方法： add、offer、put、offer超时版。 IllegalStateException - 队列满了 ClassCastException - 添加的元素类型不匹配 NullPointerException - 添加的元素为null IllegalArgumentException - 添加的元素某些属性不匹配 add方法特别之处用于添加失败时抛出异常，共有四种异常： offer方法特别之处用于添加失败时只返回false put方法特别之处用于当阻塞队列满时，生产者如果往队列里put元素，则队列会一直阻塞生产者线程，直到队列可用或者响应中断退出 offer超时方法特别之处用于当阻塞队列满时，生产者如果往队列里面插入元素，队列会阻塞生产者线程一段时间，如果超过了指定时间，生产者线程会退出，并返回false。 移除有四种方法： remove、poll、take、poll超时版 NoSuchElementException - 如果这个队列是空的 remove方法特别之处用于移除失败时抛出异常 poll方法特别之处用于移除失败时返回null take方法特别之处用于当阻塞队列为空时，消费者线程如果从队列里面移除元素，则队列会一直阻塞消费者线程，直到队列不为空 poll超时方法特别之处用于当阻塞队列空时，消费者如果从队列里面删除元素，则队列会一直阻塞消费者线程，如果超过了指定时间，消费者线程会退出，并返回null 检查有两种方法： element、peek element方法用于检测头部元素的存在性，如果队列为空，则抛出异常，否则返回头部元素。 peek方法用于检测头部元素的存在性，如果队列为空，返回特殊值null，否则返回头部的元素。 6.4 BlockingQueue通过什么来阻塞插入和移除的？当往队列里插入一个元素时，如果队列不可用，那么阻塞生产者主要通过LockSupport. park（this）来实现。 park这个方法会阻塞当前线程，只有以下4种情况中的一种发生时，该方法才会返回。 与park对应的unpark执行或已经执行时。“已经执行”是指unpark先执行，然后再执行park的情况。 线程被中断时。 等待完time参数指定的毫秒数时。 异常现象发生时，这个异常现象没有任何原因。 6.5 哪些类继承了BlockingQueue接口？BlockingDeque接口 - 双端阻塞队列 TransferQueue接口 - 传输队列 6.6 哪些类实现了BlockingQueue接口？ArrayBlockingQueue类 - 由数组构成的有界阻塞队列 LinkedBlockingQueue类 - 由链表构成的有界阻塞队列，界限默认大小为Integer.MAX_Value（2^31-1），值非常大，相当于无界。 LinkedBlockingDeque类 - 由链表构成的双向阻塞队列 LinkedTransferQueue类 - 由链表构成的无界阻塞队列 SynchronousQueue类 - 不存储元素的阻塞队列，只有一个元素进行数据传递。 LinkedTransferQueue类 - 由链表构成的无界阻塞TransferQueue队列 DelayQueue类 - 使用优先级队列实现的延迟无界阻塞队列 6.6 BlockingQueue接口继承了哪些接口BlockingQueue接口继承了Queue接口，可作为队列使用 七、双端阻塞BlockingDeque接口 7.1 从原理图上理解BlockDequeBlockQueue满了，两端的Take操作被阻塞
BlockingDeque满了 BlockQueue为空，两端的Take操作被阻塞
BlockQueue为空 7.2 BlockingDeque接口方法是阻塞队列BlockingQueue和双向队列Deque接口的结合。有如下方法：
BlockingDeque接口方法 示例： 尝试执行以下方法： LinkedBlockingDeque queue = new LinkedBlockingDeque(); queue.addFirst("test1"); queue.addFirst(300); queue.addLast("400");最后队列中的元素顺序如下： 300, test1, 400。 先添加了test1放到队列的头部，然后在头部的前面放入300，所以300在最前面，成为头部，然后将400放入队列的尾部，所以最后的结果是300, test1, 400。
队列种的元素 7.3 BlockDeque和BlockQueue的对等方法
BlockDeque和BlockQueue的对等方法 7.4 BlockingDeque的特点线程安全。 不允许使用null元素。 无界和有界都可以。 7.5 BlockingDeque接口继承了哪些接口？Queue接口，具有队列的功能 Deque接口，具有双端队列的功能 BlockingQueue接口，可作为阻塞队列使用 7.6 哪些类实现了BlockDeque接口？LinkedBlockingDeque 八、使命必达TransferQueue接口 8.1 Transfer怎么理解？如果有消费者正在获取元素，则将队列中的元素传递给消费者。如果没有消费者，则等待消费者消费。我把它称作使命必达队列，必须将任务完成才能返回。 8.2 生活中的案例针对TransferQueue的transfer方法 圆通快递员要将小明的2个快递送货到门，韵达快递员也想将小明的2个快递送货到门。小明一次只能拿一个，快递员必须等小明拿了一个后，才能继续给第二个。 针对TransferQueue的tryTransfer方法 圆通快递员要将小明的2个快递送货到门，韵达快递员也想将小明的2个快递送货到门。发现小明不在家，就把快递直接放到菜鸟驿站了。 针对TransferQueue的tryTransfer超时方法 圆通快递员要将小明的2个快递送货到门，韵达快递员也想将小明的2个快递送货到门。发现小明不在家，于是先等了5分钟，发现小明还没有回来，就把快递直接放到菜鸟驿站了。 8.3 TransferQueue的原理解析transfer(E e) 原理如下图所示：
transfer方法的原理 原理图解释：生产者线程Producer Thread尝试将元素B传给消费者线程，如果没有消费者线程，则将元素B放到尾节点。并且生产者线程等待元素B被消费。当元素B被消费后，生产者线程返回。 如果当前有消费者正在等待接收元素（消费者通过take方法或超时限制的poll方法时），transfer方法可以把生产者传入的元素立刻transfer（传输）给消费者。 如果没有消费者等待接收元素，transfer方法会将元素放在队列的tail（尾）节点，并等到该元素被消费者消费了才返回。 tryTransfer(E e) 试探生产者传入的元素是否能直接传给消费者。 如果没有消费者等待接收元素，则返回false。 和transfer方法的区别是，无论消费者是否接收，方法立即返回。 tryTransfer(E e, long timeout, TimeUnit unit) 带有时间限制的tryTransfer方法。 试图把生产者传入的元素直接传给消费者。 如果没有消费者消费该元素则等待指定的时间再返回。 如果超时了还没有消费元素，则返回false。 如果在超时时间内消费了元素，则返回true。 getWaitingConsumerCount() 获取通过BlockingQueue.take()方法或超时限制poll方法等待接受元素的消费者数量。近似值。 返回等待接收元素的消费者数量。 hasWaitingConsumer() 获取是否有通过BlockingQueue.tabke()方法或超时限制poll方法等待接受元素的消费者。 返回true则表示至少有一个等待消费者。 8.3 TransferQueue接口继承了哪些接口？BlockingQueue接口，可作为阻塞队列使用 Queue接口，可作为队列使用 8.4 哪些类实现了TransferQueue接口？LinkedTranferQueue接口 九、优先由你PriorityQueue类 9.1 理解PriorityQueue类本应该按照升序排序
本应该按照升序排序 按照倒叙排序
按照自定义优先级排序 PriorityQueue是一个支持优先级的无界阻塞队列。 默认自然顺序升序排序。 可以通过构造参数Comparator来对元素进行排序。 public PriorityQueue(Comparator |
【本文地址】
今日新闻 |
推荐新闻 |