【Java技术】盘点 Java 中的队列

队列是一种重要的数据结构，Java 语言提供了队列的支持，内置了多种类型的队列供我们使用。限于篇幅，本文不会讨论太多细节。

队列数据结构

队列是一个先进先出的抽象数据结构，可类比于生活中的排队场景。通常情况下，队列有数组和链表两种实现方式。

采用链表实现的队列，没有个数限制。插入元素时直接接在链表的尾部，取出元素时直接从链表的头部取出即可。

采用数组实现的队列，通常是循环数组，受限于数组的大小，存在天然的个数上限。插入和取出元素时，必须采用队列头部指针和队列尾部指针进行队列满和队列空的判断。

Java 队列定义

Java 定义了队列的基本操作，接口类型为 java.util.Queue，接口定义如下所示。Queue 定义了两套队列操作方法：

add、remove、element 操作失败抛出异常；

offer 操作失败返回 false 或抛出异常，poll、peek 操作失败返回 null；

public interface Queue<E> extends Collection<E> {
    //插入元素，成功返回true，失败抛出异常
    boolean add(E e);

    //插入元素，成功返回true，失败返回false或抛出异常 
    boolean offer(E e);

    //取出并移除头部元素，空队列抛出异常 
    E remove();

    //取出并移除头部元素，空队列返回null 
    E poll();

    //取出但不移除头部元素，空队列抛出异常 
    E element();

    //取出但不移除头部元素，空队列返回null 
    E peek();
}

Queue 作为先进先出队列，只能从头部取元素、插入元素到尾部。Java 同样定义了双向队列 Deque，可以同时在头部、尾部插入和取出元素，接口定义如下所示。Deque 也同样定义了两套队列操作方法，针对头部操作方法为 xxxFirst、针对尾部操作方法为 xxxLast：

add、remove、get 操作失败抛出异常；

offer 操作失败返回 false 或抛出异常，poll、peek 操作失败返回 null；

Deque 另外还有 removeFirstOccurrence、removeLastOccurrence 方法用于删除指定元素，元素存在则删除，不存在则队列不变。

public interface Deque<E> extends Queue<E> {
    //插入元素到队列头部，失败抛出异常 
    void addFirst(E e);

    //插入元素到队列尾部，失败抛出异常  
    void addLast(E e);

    //插入元素到队列头部，失败返回false或抛出异常 
    boolean offerFirst(E e);

    //插入元素到队列尾部，失败返回false抛出异常  
    boolean offerLast(E e);

    //取出并移除头部元素，空队列抛出异常 
    E removeFirst();

    //取出并移除尾部元素，空队列抛出异常 
    E removeLast();

    //取出并移除头部元素，空队列返回null
    E pollFirst();

    //取出并移除尾部元素，空队列返回null
    E pollLast();

    //取出但不移除头部元素，空队列抛出异常
    E getFirst();

    //取出但不移除尾部元素，空队列抛出异常
    E getLast();

    //取出但不移除头部元素，空队列返回null
    E peekFirst();

    //取出但不移除尾部元素，空队列返回null
    E peekLast();

    //移除指定头部元素，若不存在队列不变，移除成功返回true 
    boolean removeFirstOccurrence(Object o);

    //移除指定尾部元素，若不存在队列不变，移除成功返回true 
    boolean removeLastOccurrence(Object o);

    //单向队列方法，参考Queue   
    //栈方法，参考栈
    //集合方法，参考集合定义   
}

Java 并发工具包中定义了阻塞队列 BlockingQueue 和 BlockingDueue。阻塞队列在前面的队列定义基础上增加了以下几个方法，来支持阻塞操作。

take：取出并移除元素，如队列为空则一直阻塞直到有元素；

put：插入元素，如队列满则一直阻塞直到有空位可以插入元素；

可超时的offer：插入元素并指定超时时间，如队列满等待指定的时间；

可超时的poll：取出并移除元素，如队列空等待指定的时间。

Java 中的 Queue 实现

Java 中的队列实现，基本上都继承了 AbstractQueue 类。AbstractQueue 抽象队列实现了 add、remove、element 方法，这些方法调用 offer、poll、peek 方法并在失败时抛出异常，此外还提供了清空队列的 clear 方法和批量插入元素的 addAll 方法。

非阻塞队列访问队列元素时可以立即返回，主要有优先级队列 PriorityQueue、并发队列 ConcurrentLinkedQueue。

PriorityQueue 是一个无界优先级队列，基于一个优先级堆实现。队列中的元素按照自然排序先后排列，或者使用创建时提供的 Comparator 比较先后顺序。优先级队列需要比较顺序，因此不能包含 null 元素。使用自然顺序排序时，元素必须是可以比较大小的，否则会导致类型转换异常。优先级队列的头部元素是队列中按照顺序最靠前的元素，如有多个元素排序相等则随机选择一个。

ConcurrentLinkedQueue 是一个基于链表实现的线程安全的无界队列。内部元素按先进先出的顺序排序，最后插入的元素位于队列尾部。ConcurrentLinkedQueue 不允许插入 null。当有多个线程同时访问队列时，此队列是一个比较合适的选择。

Queue 接口的子接口 BlockingQueue 定义了阻塞队列。阻塞队列访问队列元素时，可能会一直阻塞直到操作完成，比如从空队列中取元素、向满队列中插入元素等，主要有延时队列、同步队列、链表阻塞队列、数组阻塞队列、优先级阻塞队列。

DelayQueue 是一个无界延时队列，元素只有在延时时间已经过期的情况下才能被访问。头部元素是队列中延时时间过期最久的元素。如果没有元素过期则没有头部元素，取元素的方法会返回 null。当元素过期时，调用元素的 getDelay 方法会返回 0 或 负数。未过期的元素不能被取出，但是统计队列大小时仍然包含未过期元素。

SynchronousQueue 是一个同步队列。同步队列与其他阻塞队列不太一样，插入元素时会一直阻塞直到有另一个线程取元素，取元素同样会一直阻塞直到有另一个线程插入元素。同步队列本身没有容量的概念，也不保持元素，可以理解为两个线程交换数据的媒介，因此也不能执行 size、peek 类型的操作。

LinkedBlockingQueue 是一个基于链表实现的有界的阻塞队列。如未指定队列大小，默认为Integer.MAX_VALUE。内部元素按先进先出的顺序排序，最后插入的元素位于队列尾部。

ArrayBlockingQueue 是一个基于数组实现的有界的阻塞队列。一旦创建队列的大小不会再发生变化，是一个典型的有界队列。内部元素按先进先出的顺序排序，最后插入的元素位于队列尾部。

PriorityBlockingQueue 是一个无界优先级阻塞队列。这个队列与 PriorityQueue 类似，但当队列空或满时会阻塞相关操作。

阻塞队列经常存在生产者等待消费者消费元素的情况，BlockingQueue 的子接口 TransferQueue 定义了一种新队列来支持这种情况，实现类为 LinkedTransferQueue。TransferQueue 允许生产者调用 transfer 方法来等待消费者调用 take 或 poll 消费元素，如果有消费者正在取元素则直接交给消费者，否则便把元素插入队列尾部并阻塞生产者当前线程直到元素被消费者取走。

Java 中的 Deque 实现

Deque 接口的实现相对较少，主要有 LinkedList、ArrayDeque、ConcurrentLinkedDeque 和 LinkedBlockingDeque。

LinkedList 就是我们常用的链表，实现了 Deque 接口。LinkedList 为了提高性能，本身支持从链表两端插入和取出元素，与 Deque 的要求恰好一致。

ArrayDeque 是一个基于数组的双向队列，大小可变。ArrayDeque 是非线程安全的，在多线程并发时需要外部调用者自行处理并发。

ConcurrentLinkedDeque 是一个基于链表实现的线程安全的无界双向队列。内部元素按先进先出的顺序排序，最后插入的元素位于队列尾部，不允许插入 null。当有多个线程同时访问双向队列时，此队列是一个比较合适的选择。

Deque 接口有一个子接口 BlockingDeque 定义了阻塞双向队列。实现类为 LinkedBlockingDeque，是一个基于链表实现的有界的阻塞双向队列。如未指定队列大小，默认为Integer.MAX_VALUE。内部元素按先进先出的顺序排序，最后插入的元素位于队列尾部。

Java 中的队列就讨论到这里，欢迎留言留下您的观点和看法。

分享学习笔记和技术总结，内容涉及 Java 技术、软件架构、前沿技术、开源框架、数据结构与算法、编程感悟等多个领域，欢迎关注。本文首发于微信公众号“后端开发那点事儿” 。