关于java:Java中的5大队列你知道几个

本文已收录至 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 关键字，比方以下这些：

ArrayBlockingQueue
LinkedBlockingQueue
PriorityBlockingQueue
…….

接下来咱们来演示一下当阻塞队列的容量满了之后会怎么，示例代码如下：

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 {
                    // 休眠 1S
                    Thread.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:1

Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:2

Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:3

Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:4

Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:5

Mon Oct 19 20:16:13 CST 2020 | ArrayBlockingQueue Size:5

Mon Oct 19 20:16:14 CST 2020 | ArrayBlockingQueue Size:5

Mon Oct 19 20:16:15 CST 2020 | ArrayBlockingQueue Size:5

Mon Oct 19 20:16:16 CST 2020 | ArrayBlockingQueue Size:5

Mon Oct 19 20:16:17 CST 2020 | ArrayBlockingQueue Size:5

Mon 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），所以从使用者的角度来看相当于“无界”的。

接下来就是本文的重点了，咱们以性能来划分一下队列，它能够被分为：一般队列、优先队列、双端队列、提早队列、其余队列等，接下来咱们别离来看。

一般队列（Queue）是指实现了先进先出的根本队列，例如 ArrayBlockingQueue 和 LinkedBlockingQueue，其中 ArrayBlockingQueue 是用数组实现的一般队列，如下图所示：

而 LinkedBlockingQueue 是应用链表实现的一般队列，如下图所示：

罕用办法

一般队列中的罕用办法有以下这些：

offer()：增加元素，如果队列已满间接返回 false，队列未满则直接插入并返回 true；
poll()：删除并返回队头元素，当队列为空返回 null；
add()：增加元素，此办法是对 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());
        }
    }
}

以上代码的执行后果如下：

Hello

Java

中文社群

双端队列（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());
        }
    }
}

以上代码的执行后果如下：

offerFirst

offer

offerLast

优先队列（PriorityQueue）是一种非凡的队列，它并不是先进先出的，而是优先级高的元素先出队。

优先队列是依据二叉堆实现的，二叉堆的数据结构如下图所示：

二叉堆分为两种类型：一种是最大堆一种是最小堆。 以上展现的是最大堆， 在最大堆中，任意一个父节点的值都大于等于它左右子节点的值。

因为优先队列是基于二叉堆实现的，因而它能够将优先级最好的元素先出队。

接下来咱们来演示一下优先队列的应用：

import java.util.PriorityQueue;

public class PriorityQueueTest {
    // 自定义的实体类
    static class Viper {
        private int id; // id
        private 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 Comparator<Viper>() {
            @Override
            public 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());
        }
    }
}

以上代码的执行后果如下：

Name：MySQL Level：5

Name：Redis Level：3

Name：Java Level：1

从上述后果能够看出， 优先队列的出队是不思考入队程序的，它始终遵循的是优先级高的元素先出队 。

提早队列（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 实现
        @Getter
        @Setter
        private String msg;

        /**
         * 初始化
         * @param delayTime 设置提早执行工夫
         * @param msg       执行的音讯
         */
        public MyDelay(long delayTime, String msg) {this.delayTime = (this.delayTime + delayTime);
            this.msg = msg;
        }

        // 获取剩余时间
        @Override
        public long getDelay(TimeUnit unit) {return unit.convert(delayTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
        }

        // 队列里元素的排序根据
        @Override
        public 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;}
        }
        @Override
        public String toString() {return this.msg;}
    }
}

以上代码的执行后果如下：

开始执行工夫：2020-10-20 20:17:28

音讯 1

音讯 2

完结执行工夫：2020-10-20 20:17:31

从上述完结执行工夫和开始执行工夫能够看出，音讯 1 和音讯 2 都失常实现了提早执行的性能。

在 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 0

Mon Oct 19 21:00:22 CST 2020，元素入队

Mon Oct 19 21:00:23 CST 2020，元素出队：Data 1

Mon 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。

文末福利：搜寻公众号「Java 中文社群」发送“面试”，支付最新的面试材料。

关于java:Java中的5大队列你知道几个

阻塞队列和非阻塞队列

阻塞队列性能演示

非阻塞队列

有界队列和无界队列

按性能分类

1. 一般队列

罕用办法

2. 双端队列

3. 优先队列

4. 提早队列

5. 其余队列

总结