Queue接口及其子接口

简介

18种队列：

序号 名称 类型 有界 线程安全 说明
1 Queue 接口 / / 最上层队列接口
2 BlockingQueue 接口 / / 阻塞队列接口
3 BlockingDeque 接口 / / 双向阻塞队列接口
4 Deque 接口 / / 双向队列接口
5 TransferQueue 接口 / / 传输队列接口
6 AbstractQueue 抽象类 / / 队列抽象类
7 PriorityQueue 普通类 N N 优先级队列
8 ArrayDeque 普通类 N N 数组双向队列类
9 LinkedList 普通类 N N 链表对象类
10 ConcurrentLinkedQueue 普通类 N Y 链表结构的线程安全的队列类
11 ConcurrentLinkedDeque 普通类 N Y 链表结构的线程安全的双向队列类
12 ArrayBlockingQueue 普通类 Y Y 数组结构的有界阻塞队列
13 LinkedBlockingQueue 普通类 Y Y 链表结构的有界阻塞队列
14 LinkedBlockingDeque 普通类 Y Y 链表结构的双向有界阻塞队列
15 LinkedTransferQueue 普通类 N Y 链表结构的无界阻塞传输队列
16 SynchronousQueue 普通类 Y Y 不存储元素的阻塞队列
17 PriorityBlockingQueue 普通类 N Y 支持优先级排序的无界阻塞队列
18 DelayQueue 普通类 N Y 优先级队列实现的延时无界阻塞队列

队列继承关系：

image-20210126144432320

队列是一种数据结构，元素从队列的一头进入、从另外一头出去，称为FIFO原则（先进先出原则）。

Queue

本质

  • Queue接口是一种Collection，被设计用于处理之前临时保存在某处的元素。
  • 除了基本的Collection操作之外，队列还提供了额外的插入、提取和检查操作。每一种操作都有两种形式：如果操作失败，则抛出一个异常；如果操作失败，则返回一个特殊值（null或false，取决于是什么操作）。
  • 队列通常是以FIFO（先进先出）的方式排序元素，但是这不是必须的。
  • 只有优先级队列可以根据提供的比较器对元素进行排序或者是采用正常的排序。无论怎么排序，队列的头将通过调用remove()或poll()方法进行移除。在FIFO队列种，所有新的元素被插入到队尾。其他种类的队列可能使用不同的布局来存放元素。

核心方法

image-20210126153640125

动作 抛异常 返回特殊值
插入 add(e) offer(e)
移除队头 remove() poll()
查询队头 element() peek()
  1. 插入：add(e)方法时，添加失败，则会抛异常；offer(e)方法失败时，则会返回false。在有界队列中，优先使用offer方法。假如队列满了，不能添加元素，offer方法返回false，这样我们就知道是队列满了，而不是运行时抛出的异常。
  2. 同理，移除（Remove）元素的动作，队列为空时，remove方法抛异常，而poll返回null。如果移除头部的元素成功，则返回移除的元素。
  3. 同理，返回头部元素（最开始加入的元素），但不删除元素， 如果队列为空，则element()方法抛异常，而peek()返回false。
  4. Queue实现类通常不允许插入null元素，尽管一些实现类比如LinkedList不禁止插入null，但是还是不建议插入null，因为null也被用在poll方法的特殊返回值，以说明队列不包含元素。

双端可用Deque

Deque概念

image-20210126164809969

双端队列Deque

支持两端元素插入和移除的线性集合。名称deque是双端队列的缩写。大多数实现Deque的类，对它们包含的元素的数量没有固定的限制的，支持有界和无界。

image-20210126163757855

相关方法

头元素 尾元素 头元素 尾元素
抛异常 返回特殊值 抛异常 返回特殊值
插入 addFirst(e) offerFirst(e) addLast(e) offerLast(e)
删除 removeFirst() pollFirst() removeLast() pollLast()
获取 getFirst() peekFirst() getLast() peekLast()
  • 这些方法种的每一种都存在两种形式：如果操作失败，则会抛出异常，另一种方法返回一个特殊值（null或false，取决于具体操作）。
  • 插入操作的后一种形式专门设计用于容量限制的Deque实现，大多数实现中，插入操作不能失败，所以可以用插入操作的后一种形式。
  • Deque接口扩展了Queue接口，当使用deque作为队列时，作为FIFO。元素将添加到deque的末尾，并从头开始删除。
  • Deque也可以用作LIFO（后进先出）栈，这个接口优于传统的Stack类。当作为栈使用时，元素被push到deque队列的头，而pop也是从队列的头pop出来。
  • peek方法不论是作为栈还是队列，都是从队列的检测队列的头，返回最先加入的元素。

队列骨架AbstractQueue

简介

AbstractQueue是一个抽象类，继承了Queue接口，提供了一些Queue操作的骨架实现。

image-20210126164027774

image-20210126164543250

相关方法

  • 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的clear方法
public void clear() {
    while (poll() != null)
        ;
}

注意：如果继承AbstractQueue抽象类则必须保证offer方法不允许null值插入。

阻塞队列BlockingQueue

image-20210126170138112

简介

BlockingQueue满了，Put操作会被阻塞

image-20210126165030408

阻塞队列满了

BlockingQueue为空，Take操作被阻塞

image-20210126165223795

阻塞队列为空

应用场景：生产者和消费者，生产者线程向队列里添加元素，消费者线程从队列里移除元素，阻塞队列时获取和存放元素的容器。

为什么要用阻塞队列：生产者生产和消费者消费的速率不一样，需要用队列来解决速率差问题，当队列满了或空的时候，则需要阻塞生产或消费动作来解决队列满或空的问题。

常用方法

插入

add(e)：返回true，添加失败时抛出异常

offer(e)：返回true/false，方法特别之处用于添加失败时只返回false

put(e)：void，当阻塞队列满时，生产者如果往队列里put元素，则队列会一直阻塞生产者线程，直到队列可用或者响应中断退出

offer(e,time,unit)：返回true/false，当阻塞队列满时，生产者如果往队列里面插入元素，队列会阻塞生产者线程一段时间，如果超过了指定时间，生产者线程会退出，并返回false

删除

remove()：返回true，移除失败时抛出异常

poll()：返回移除元素/null，移除失败时返回null

take()：返回移除元素，当阻塞队列为空时，消费者线程如果从队列里面移除元素，则队列会一直阻塞消费者线程，直到队列不为空

poll(time,unit)：返回移除元素/null，当阻塞队列空时，消费者如果从队列里面删除元素，则队列会一直阻塞消费者线程，如果超过了指定时间，消费者线程会退出，并返回null

获取

element()：返回头部的元素，如果队列为空，则抛出异常，否则返回头部元素

peek()：返回移除元素/null，如果队列为空，返回特殊值null，否则返回头部的元素。

其他方法

drainTo(Collection<? super E> c) 从该队列中删除所有可用的元素，并将它们添加到给定的集合中。

drainTo(Collection<? super E> c, int maxElements) 最多从该队列中删除给定数量的可用元素，并将它们添加到给定的集合中。

remainingCapacity() 返回队列剩余容量

        BlockingQueue<String> queue = new LinkedBlockingQueue<>(20);
        queue.put("111");
        queue.put("222");
        queue.put("333");
        queue.put("999");
        queue.put("333");
        queue.put("666");
        queue.put("333");
        queue.put("444");
        System.out.println(queue);
        ArrayList<Object> arrayList = new ArrayList<>(Arrays.asList("A", "B"));
        int i = queue.drainTo(arrayList,4);
        System.out.println(arrayList);
        System.out.println(queue);
        System.out.println(queue.remainingCapacity());

image-20210127090852779

BlockingQueue通过什么来阻塞插入和移除的？

  • 当往队列里插入一个元素时，如果队列不可用，那么阻塞生产者主要通过LockSupport. park（this）来实现。

  • park这个方法会阻塞当前线程，只有以下4种情况中的一种发生时，该方法才会返回。

    • 与park对应的unpark执行或已经执行时。“已经执行”是指unpark先执行，然后再执行park的情况。
    • 线程被中断时。
    • 等待完time参数指定的毫秒数时。
    • 异常现象发生时，这个异常现象没有任何原因

双端阻塞队列BlockingDeque

简介

image-20210127091538413

BlockingDeque满了

image-20210127091635567

BlockQueue为空
  • 线程安全。
  • 不允许使用null元素。
  • 无界和有界都可以

常用方法

抛出异常 返回特殊值 阻塞 超时
Insert addFirst(o) offerFirst(o) putFirst(o) offerFirst(o, timeout, timeunit)
Remove removeFirst(o) pollFirst(o) takeFirst(o) pollFirst(timeout, timeunit)
Examine getFirst(o) peekFirst(o)
抛出异常 返回特殊值 阻塞 超时
Insert addLast(o) offerLast(o) putLast(o) offerLast(o, timeout, timeunit)
Remove removeLast(o) pollLast(o) takeLast(o) pollLast(timeout, timeunit)
Examine getLast(o) peekLast(o)

TransferQueue

简介

如果有消费者正在获取元素，则将队列中的元素传递给消费者。如果没有消费者，则等待消费者消费。TransferQueue接口定义的相关内容如上所诉。

image-20210127093035709

该接口继承了BlockingQueue接口，所以TransferQueue具有阻塞队列的所有特性。LinkedTranferQueue实现了TransferQueue。

生活中的案例

  • 针对TransferQueue的transfer方法

    • 圆通快递员要将小明的2个快递送货到门，韵达快递员也想将小明的2个快递送货到门。小明一次只能拿一个，快递员必须等小明拿了一个后，才能继续给第二个。

  • 针对TransferQueue的tryTransfer方法

    • 圆通快递员要将小明的2个快递送货到门，韵达快递员也想将小明的2个快递送货到门。发现小明不在家，就把快递直接放到菜鸟驿站了。

  • 针对TransferQueue的tryTransfer超时方法

    • 圆通快递员要将小明的2个快递送货到门，韵达快递员也想将小明的2个快递送货到门。发现小明不在家，于是先等了5分钟，发现小明还没有回来，就把快递直接放到菜鸟驿站了。

常用方法

transfer(E e)

image-20210127100325697

  • 原理图解释：生产者线程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则表示至少有一个等待消费者。

测试

    public static void main(String[] args) {
        TransferQueue<Integer> queue = new LinkedTransferQueue<>();
        new Thread(() -> {
            try {
                Thread.sleep(200);  // 再改成1500
                System.out.println(Thread.currentThread().getName()+"-"+queue.take());
                System.out.println(Thread.currentThread().getName()+"-"+queue.take());
                System.out.println(Thread.currentThread().getName()+"-"+queue.take());
            } catch (InterruptedException e1) {
                e1.printStackTrace();
            }
        },"consumer").start();
        new Thread(() -> {
            System.out.println(Thread.currentThread().getName()+"-等待1被消费："+queue.tryTransfer(1));
            try {
                System.out.println(Thread.currentThread().getName()+"-等待2被消费："+queue.tryTransfer(2, 1, TimeUnit.SECONDS));
                queue.transfer(3);
                System.out.println(Thread.currentThread().getName()+"-等待3被消费：true");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        },"producer").start();
    }

image-20210127100753462

把睡眠时间改成1500时：

image-20210127100831367

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wwjj4811/p/14333650.html