做网站客户一般会问什么问题,做pc端网站精英,网站网页设计怎么报价,公建一般多少钱作者 | 王磊来源 | Java中文社群#xff08;ID#xff1a;javacn666#xff09;转载请联系授权#xff08;微信ID#xff1a;GG_Stone#xff09;本文已收录至 https://github.com/vipstone/algorithm 《算法图解》系列。通过前面文章的学习《一文详解「队列」#xff0… 作者 | 王磊来源 | Java中文社群IDjavacn666转载请联系授权微信IDGG_Stone本文已收录至 https://github.com/vipstone/algorithm 《算法图解》系列。通过前面文章的学习《一文详解「队列」手撸队列的3种方法》我们知道了队列Queue是先进先出FIFO的并且我们可以用数组、链表还有 List 的方式来实现自定义队列那么本文我们来系统的学习一下官方是如何实现队列的。Java 中的队列有很多例如ArrayBlockingQueue、LinkedBlockingQueue、PriorityQueue、DelayQueue、SynchronousQueue 等那它们的作用是什么又是如何分类的呢其实 Java 中的这些队列可以从不同的维度进行分类例如可以从阻塞和非阻塞进行分类也可以从有界和无界进行分类而本文将从队列的功能上进行分类例如优先队列、普通队列、双端队列、延迟队列等。虽然本文的重点是从功能上对队列进行解读但其它分类也是 Java 中的重要概念所以我们先来了解一下它们。阻塞队列和非阻塞队列阻塞队列Blocking Queue提供了可阻塞的 put 和 take 方法它们与可定时的 offer 和 poll 是等价的。如果队列满了 put 方法会被阻塞等到有空间可用再将元素插入如果队列是空的那么 take 方法也会阻塞直到有元素可用。当队列永远不会被充满时put 方法和 take 方法就永远不会阻塞。我们可以从队列的名称中知道此队列是否为阻塞队列阻塞队列中包含 BlockingQueue 关键字比如以下这些ArrayBlockingQueueLinkedBlockingQueuePriorityBlockingQueue.......阻塞队列功能演示接下来我们来演示一下当阻塞队列的容量满了之后会怎样示例代码如下import java.util.Date;
import java.util.concurrent.ArrayBlockingQueue;public class BlockingTest {public static void main(String[] args) throws InterruptedException {// 创建一个长度为 5 的阻塞队列ArrayBlockingQueue q1 new ArrayBlockingQueue(5);// 新创建一个线程执行入列new Thread(() - {// 循环 10 次for (int i 0; i 10; i) {try {q1.put(i);} catch (InterruptedException e) {e.printStackTrace();}System.out.println(new Date() | ArrayBlockingQueue Size: q1.size());}System.out.println(new Date() | For End.);}).start();// 新创建一个线程执行出列new Thread(() - {for (int i 0; i 5; i) {try {// 休眠 1SThread.sleep(1000);} catch (InterruptedException e) {e.printStackTrace();}if (!q1.isEmpty()) {try {q1.take(); // 出列} catch (InterruptedException e) {e.printStackTrace();}}}}).start();}
}
以上代码的执行结果如下Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:1Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:2Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:3Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:4Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:5Mon Oct 19 20:16:13 CST 2020 | ArrayBlockingQueue Size:5Mon Oct 19 20:16:14 CST 2020 | ArrayBlockingQueue Size:5Mon Oct 19 20:16:15 CST 2020 | ArrayBlockingQueue Size:5Mon Oct 19 20:16:16 CST 2020 | ArrayBlockingQueue Size:5Mon Oct 19 20:16:17 CST 2020 | ArrayBlockingQueue Size:5Mon Oct 19 20:16:17 CST 2020 | For End.从上述结果可以看出当 ArrayBlockingQueue 队列满了之后就会进入阻塞当过了 1 秒有元素从队列中移除之后才会将新的元素入列。非阻塞队列非阻塞队列也就是普通队列它的名字中不会包含 BlockingQueue 关键字并且它不会包含 put 和 take 方法当队列满之后如果还有新元素入列会直接返回错误并不会阻塞的等待着添加元素如下图所示非阻塞队列的典型代表是 ConcurrentLinkedQueue 和 PriorityQueue。有界队列和无界队列有界队列是指有固定大小的队列比如设定了固定大小的 ArrayBlockingQueue又或者大小为 0 的 SynchronousQueue。无界队列指的是没有设置固定大小的队列但其实如果没有设置固定大小也是有默认值的只不过默认值是 Integer.MAX_VALUE当然实际的使用中不会有这么大的容量超过 Integer.MAX_VALUE所以从使用者的角度来看相当于 “无界”的。按功能分类接下来就是本文的重点了我们以功能来划分一下队列它可以被分为普通队列、优先队列、双端队列、延迟队列、其他队列等接下来我们分别来看。1.普通队列普通队列Queue是指实现了先进先出的基本队列例如 ArrayBlockingQueue 和 LinkedBlockingQueue其中 ArrayBlockingQueue 是用数组实现的普通队列如下图所示而 LinkedBlockingQueue 是使用链表实现的普通队列如下图所示常用方法普通队列中的常用方法有以下这些offer()添加元素如果队列已满直接返回 false队列未满则直接插入并返回 truepoll()删除并返回队头元素当队列为空返回 nulladd()添加元素此方法是对 offer 方法的简单封装如果队列已满抛出 IllegalStateException 异常remove()直接删除队头元素put()添加元素如果队列已经满则会阻塞等待插入take()删除并返回队头元素当队列为空则会阻塞等待peek()查询队头元素但不会进行删除element()对 peek 方法进行简单封装如果队头元素存在则取出并不删除如果不存在抛出 NoSuchElementException 异常。注意一般情况下 offer() 和 poll() 方法配合使用put() 和 take() 阻塞方法配合使用add() 和 remove() 方法会配合使用程序中常用的是 offer() 和 poll() 方法因此这两个方法比较友好不会报错。接下来我们以 LinkedBlockingQueue 为例演示一下普通队列的使用import java.util.concurrent.LinkedBlockingQueue;static class LinkedBlockingQueueTest {public static void main(String[] args) {LinkedBlockingQueue queue new LinkedBlockingQueue();queue.offer(Hello);queue.offer(Java);queue.offer(中文社群);while (!queue.isEmpty()) {System.out.println(queue.poll());}}
}
以上代码的执行结果如下HelloJava中文社群2.双端队列双端队列Deque是指队列的头部和尾部都可以同时入队和出队的数据结构如下图所示接下来我们来演示一下双端队列 LinkedBlockingDeque 的使用import java.util.concurrent.LinkedBlockingDeque;/*** 双端队列示例*/
static class LinkedBlockingDequeTest {public static void main(String[] args) {// 创建一个双端队列LinkedBlockingDeque deque new LinkedBlockingDeque();deque.offer(offer); // 插入首个元素deque.offerFirst(offerFirst); // 队头插入元素deque.offerLast(offerLast); // 队尾插入元素while (!deque.isEmpty()) {// 从头遍历打印System.out.println(deque.poll());}}
}
以上代码的执行结果如下offerFirstofferofferLast3.优先队列优先队列PriorityQueue是一种特殊的队列它并不是先进先出的而是优先级高的元素先出队。优先队列是根据二叉堆实现的二叉堆的数据结构如下图所示二叉堆分为两种类型一种是最大堆一种是最小堆。以上展示的是最大堆在最大堆中任意一个父节点的值都大于等于它左右子节点的值。因为优先队列是基于二叉堆实现的因此它可以将优先级最好的元素先出队。接下来我们来演示一下优先队列的使用import java.util.PriorityQueue;public class PriorityQueueTest {// 自定义的实体类static class Viper {private int id; // idprivate String name; // 名称private int level; // 等级public Viper(int id, String name, int level) {this.id id;this.name name;this.level level;}public int getId() {return id;}public void setId(int id) {this.id id;}public String getName() {return name;}public void setName(String name) {this.name name;}public int getLevel() {return level;}public void setLevel(int level) {this.level level;}}public static void main(String[] args) {PriorityQueue queue new PriorityQueue(10, new ComparatorViper() {Overridepublic int compare(Viper v1, Viper v2) {// 设置优先级规则倒序等级越高权限越大return v2.getLevel() - v1.getLevel();}});// 构建实体类Viper v1 new Viper(1, Java, 1);Viper v2 new Viper(2, MySQL, 5);Viper v3 new Viper(3, Redis, 3);// 入列queue.offer(v1);queue.offer(v2);queue.offer(v3);while (!queue.isEmpty()) {// 遍历名称Viper item (Viper) queue.poll();System.out.println(Name item.getName() Level item.getLevel());}}
}
以上代码的执行结果如下NameMySQL Level5NameRedis Level3NameJava Level1从上述结果可以看出优先队列的出队是不考虑入队顺序的它始终遵循的是优先级高的元素先出队。4.延迟队列延迟队列DelayQueue是基于优先队列 PriorityQueue 实现的它可以看作是一种以时间为度量单位的优先的队列当入队的元素到达指定的延迟时间之后方可出队。我们来演示一下延迟队列的使用import lombok.Getter;
import lombok.Setter;
import java.text.DateFormat;
import java.util.Date;
import java.util.concurrent.DelayQueue;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;public class CustomDelayQueue {// 延迟消息队列private static DelayQueue delayQueue new DelayQueue();public static void main(String[] args) throws InterruptedException {producer(); // 调用生产者consumer(); // 调用消费者}// 生产者public static void producer() {// 添加消息delayQueue.put(new MyDelay(1000, 消息1));delayQueue.put(new MyDelay(3000, 消息2));}// 消费者public static void consumer() throws InterruptedException {System.out.println(开始执行时间 DateFormat.getDateTimeInstance().format(new Date()));while (!delayQueue.isEmpty()) {System.out.println(delayQueue.take());}System.out.println(结束执行时间 DateFormat.getDateTimeInstance().format(new Date()));}static class MyDelay implements Delayed {// 延迟截止时间单位毫秒long delayTime System.currentTimeMillis();// 借助 lombok 实现GetterSetterprivate String msg;/*** 初始化* param delayTime 设置延迟执行时间* param msg 执行的消息*/public MyDelay(long delayTime, String msg) {this.delayTime (this.delayTime delayTime);this.msg msg;}// 获取剩余时间Overridepublic long getDelay(TimeUnit unit) {return unit.convert(delayTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);}// 队列里元素的排序依据Overridepublic int compareTo(Delayed o) {if (this.getDelay(TimeUnit.MILLISECONDS) o.getDelay(TimeUnit.MILLISECONDS)) {return 1;} else if (this.getDelay(TimeUnit.MILLISECONDS) o.getDelay(TimeUnit.MILLISECONDS)) {return -1;} else {return 0;}}Overridepublic String toString() {return this.msg;}}
}
以上代码的执行结果如下开始执行时间2020-10-20 20:17:28消息1消息2结束执行时间2020-10-20 20:17:31从上述结束执行时间和开始执行时间可以看出消息 1 和消息 2 都正常实现了延迟执行的功能。5.其他队列在 Java 的队列中有一个比较特殊的队列 SynchronousQueue它的特别之处在于它内部没有容器每次进行 put() 数据后添加数据必须等待另一个线程拿走数据后才可以再次添加数据它的使用示例如下import java.util.concurrent.SynchronousQueue;public class SynchronousQueueTest {public static void main(String[] args) {SynchronousQueue queue new SynchronousQueue();// 入队new Thread(() - {for (int i 0; i 3; i) {try {System.out.println(new Date() 元素入队);queue.put(Data i);} catch (InterruptedException e) {e.printStackTrace();}}}).start();// 出队new Thread(() - {while (true) {try {Thread.sleep(1000);System.out.println(new Date() 元素出队 queue.take());} catch (InterruptedException e) {e.printStackTrace();}}}).start();}
}
以上代码的执行结果如下Mon Oct 19 21:00:21 CST 2020元素入队Mon Oct 19 21:00:22 CST 2020元素出队Data 0Mon Oct 19 21:00:22 CST 2020元素入队Mon Oct 19 21:00:23 CST 2020元素出队Data 1Mon Oct 19 21:00:23 CST 2020元素入队Mon Oct 19 21:00:24 CST 2020元素出队Data 2从上述结果可以看出当有一个元素入队之后只有等到另一个线程将元素出队之后新的元素才能再次入队。总结本文讲了 Java 中的 5 种队列普通队列、双端队列、优先队列、延迟队列、其他队列。其中普通队列的典型代表为 ArrayBlockingQueue 和 LinkedBlockingQueue双端队列的代表为 LinkedBlockingDeque优先队列的代表为 PriorityQueue延迟队列的代表为 DelayQueue最后还讲了内部没有容器的其他队列 SynchronousQueue。
往期推荐
一文详解「队列」手撸队列的3种方法动图演示手撸堆栈的两种实现方法JDK 竟然是这样实现栈的关注我每天陪你进步一点点
