Wend看源码-Java-集合学习(Queue)

概述

     Wend看源码-Java-集合学习(List)-CSDN博客 
     Wend看源码-Java-集合学习(Set)-CSDN博客

        在前两篇文章中，我们分别探讨了Java集合框架的父类以及List集合和Set集合的实现。接下来，本文将重点阐述Java中的Queue集合，包括其内部的数据结构以及核心方法的详尽说明。

Queue 集合

​

图1  Java-queue类型数据结构类图(基本）

​

图2 Java-Queue类型数据结构类图(线程安全的）

        如图1、图2 所示，Queue 接口继承自Collection 接口，而Queue 数据类型的实现，以及Deque 数据类型的实现均需要继承Queue 接口。Queue它用于表示一种队列数据结构，遵循先进先出（FIFO-First-In-First-Out）的原则。就像在生活中排队一样，先进入队列的元素先被取出。这种数据结构在很多场景下都非常有用，例如任务调度、消息传递等。

Queue 接口

        以下是Queue接口的主要方法列表：

• add:尝试将指定元素插入到队列中。该方法遵循这样的规则，如果队列当前有足够的空间（对于有容量限制的队列而言），且元素符合队列对元素类型等各方面要求，那么插入操作会成功，并且返回 true。但如果队列已满，无法再容纳新元素了，此时该方法会抛出 IllegalStateException 异常来表明插入失败。
• offer:同样是用于向队列中插入指定元素，不过和 add 方法有所区别。在插入时，如果队列有容量限制且当前已满，它不会抛出异常，而是直接返回 false，表示插入元素的操作没有成功；只有在元素成功插入到队列后，才会返回 true。所以在使用有容量限制的队列时，该方法相比 add 方法在处理插入失败情况时更加 “温和”，不会因插入失败而中断程序流程（抛出异常）。
• remove:用于从队列中移除并返回队列头部（也就是最先进入队列的那个元素，遵循先进先出原则）的元素。但要注意，如果当前队列为空，也就是没有元素可供移除时，该方法会抛出 NoSuchElementException 异常，以此提示调用者队列中无元素可操作。
• poll:也是用于移除并返回队列头部的元素，不过它和 remove() 方法的区别在于对队列为空情况的处理方式。当队列为空时，它不会抛出异常，而是直接返回 null，这样使得调用者可以通过判断返回值是否为 null 来知晓队列是否为空以及操作是否成功获取到了元素，使用起来更加灵活，在一些需要避免异常处理逻辑复杂的场景中较为实用。
• element:用于返回队列的头部元素，但它并不会将这个元素从队列中移除，也就是仅仅查看队列头部是谁。不过当队列为空时，它会抛出 NoSuchElementException 异常，和 remove() 方法对空队列的处理类似，使用该方法时需要确保队列中有元素，否则要做好异常处理准备。
• peek:同样是返回队列的头部元素且不做移除操作，与 element() 方法不同的是，当队列为空时，它不会抛出异常，而是返回 null。这样方便调用者通过简单判断返回值来知晓队列的状态以及获取头部元素情况，避免了异常处理的复杂性，在很多场景下代码逻辑会更简洁。

AbstractQueue

        AbstractQueue 是一个抽象类，它实现了 Queue 接口。它位于 Java 集合框架中，主要目的是为 Queue 接口提供部分通用的实现方法，方便其他类继承并实现自己的队列功能。它减少了实现 Queue 接口的工作量，通过提供一些基础的方法实现和定义必要的抽象方法，引导子类去完善队列的具体功能。

PriorityQueue

        PriorityQueue 是一个优先级队列，它实现了 Queue 接口，用于维护一个具有优先级顺序的元素集合。它的内部是通过一个可动态调整大小的数组来实现的，元素会根据一定的优先级规则进行排序。这个优先级规则可以是元素的自然顺序（如果元素实现了 Comparable 接口），或者是通过一个自定义的 Comparator 来确定。

主要特点

• 优先级排序：元素在队列中是按照优先级顺序排列的。例如，对于存储整数的 PriorityQueue，如果按照默认的自然顺序（从小到大）作为优先级，那么每次调用 poll 方法移除的元素都是当前队列中最小的整数。如果通过自定义 Comparator 改变了优先级规则，比如定义一个从大到小的比较器，那么每次移除的元素就是当前队列中最大的整数。
  • 插入元素时，也会根据优先级规则找到合适的位置插入。例如，在一个存储自定义任务对象的 PriorityQueue 中，每个任务有一个优先级属性，当插入一个新任务时，它会根据任务的优先级在队列中找到合适的位置插入，使得队列始终保持优先级顺序。
• 动态调整大小：它的内部数组会根据元素数量的变化自动调整大小。当元素数量达到一定阈值时，数组会进行扩容操作，以容纳更多的元素。这个过程对用户是透明的，不需要手动干预。例如，当不断向一个 PriorityQueue 中添加元素，它会自动增加内部数组的容量来存储新元素。

应用场景

• 任务调度：在操作系统的任务调度或者分布式系统的任务处理中，PriorityQueue 可以用来存储任务，按照任务的优先级进行调度。例如，高优先级的任务可以先被处理，通过将任务插入到 PriorityQueue 中，系统可以方便地获取优先级最高的任务进行处理。
• 数据排序和筛选：可以用于对数据进行排序和筛选。例如，在一个数据处理系统中，有一批数据对象，每个对象有一个权重属性，通过将这些数据对象放入 PriorityQueue 中，按照权重进行排序，然后可以方便地获取权重最高或最低的数据对象，用于进一步的分析和处理。

线程安全的 Queue

BlockingQueue 接口

  BlockingQueue是一个位于java.util.concurrent包中的接口，它是为了解决多线程环境下生产者 - 消费者问题而设计的。它在普通队列（Queue）的基础上增加了阻塞特性，当队列满时，生产者线程插入元素的操作会被阻塞；当队列空时，消费者线程获取元素的操作会被阻塞。这使得在多线程场景下可以方便地协调数据的生产和消费，避免了频繁地检查队列状态（如使用非阻塞队列时，需要不断检查队列是否为空或已满）。

应用场景

        在多线程的消息队列系统中，生产者线程将消息放入BlockingQueue，消费者线程从队列中获取消息进行处理。这种阻塞机制保证了消息的生产和消费能够有条不紊地进行，不会因为队列状态（满或空）而出现数据丢失或线程过度占用资源的情况。

ArrayBlockingQueue

   ArrayBlockingQueue是BlockingQueue接口的一个实现类，它基于数组来实现阻塞队列。在创建时需要指定队列的容量，这个容量一旦确定就不能改变。它内部通过一个数组来存储元素，并且维护了两个指针（索引），一个用于记录队列头部元素的位置，一个用于记录队列尾部元素的位置，通过移动这些指针来实现元素的添加和移除操作。

主要特点

• 有界性：由于基于固定大小的数组，它是有界的，队列容量在创建时就固定了。例如，ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10);创建了一个容量为 10 的整数队列。

• 公平性选项：在构造方法中可以指定是否为公平队列。公平队列会按照线程等待的先后顺序来访问队列，而非公平队列则不保证这一点，可能会出现后来的线程先访问队列的情况。例如，ArrayBlockingQueue<String> fairQueue = new ArrayBlockingQueue<>(5, true);创建了一个公平的字符串队列。

应用场景

        适用于需要限制队列大小的生产者 - 消费者场景，如在一个资源有限的系统中，对产生的数据进行缓存和处理。比如，一个服务器接收客户端请求，将请求放入ArrayBlockingQueue，然后由固定数量的工作线程从队列中获取请求进行处理，通过限制队列大小可以避免服务器内存被过多的请求耗尽。

LinkedBlockingQueue

  LinkedBlockingQueue也是BlockingQueue接口的实现类，它基于链表结构来实现阻塞队列。与ArrayBlockingQueue不同，它的容量可以在构造时指定，如果不指定容量，则默认为Integer.MAX_VALUE，实际上相当于无界队列（但受系统资源限制）。它通过链表节点来存储元素，添加和移除元素时操作链表的节点。

主要特点

• 可选有界性：可以根据需要创建有界或无界队列。例如，LinkedBlockingQueue<Double> boundedQueue = new LinkedBlockingQueue<>(100);创建了一个容量为 100 的有界双精度浮点数队列，而LinkedBlockingQueue<String> unboundedQueue = new LinkedBlockingQueue<>();创建了一个默认无界的字符串队列。

• 高并发性能：在高并发场景下，基于链表的实现方式使得它在插入和移除元素时的性能相对较好，因为链表的节点添加和删除操作在并发环境下对锁的竞争相对较小（相比于数组可能需要对整个数组进行锁定的情况）。

应用场景

        在高并发的生产者 - 消费者场景中，当需要处理大量的数据并且对队列大小不太确定或者希望有较大的缓冲空间时，LinkedBlockingQueue是一个很好的选择。例如，在一个大规模的数据采集系统中，采集到的数据可以放入LinkedBlockingQueue，然后由多个数据处理线程从队列中获取数据进行处理，由于其高并发性能和可选的无界特性，可以更好地适应数据流量的波动。

SynchronousQueue

  SynchronousQueue是一种特殊的BlockingQueue实现，它没有内部容量来存储元素。它的作用是作为一个同步点，用于线程之间的直接数据传递。当一个线程调用put方法尝试放入元素时，这个操作会阻塞，直到有另一个线程调用take方法来获取这个元素；反之，当一个线程调用take方法时，会阻塞直到有其他线程放入元素。

主要特点

• 无存储容量：这是它最显著的特点，使得它更像是一个线程之间的同步工具，而不是传统意义上的队列用于存储元素。例如，在一个简单的线程通信场景中，一个线程生产的数据必须立即被另一个线程消费，就可以使用SynchronousQueue。

• 公平性和非公平性选项：和ArrayBlockingQueue类似，在构造方法中可以指定公平性选项，影响线程获取元素的顺序。

应用场景

        适用于线程之间需要紧密同步传递数据的场景，如在一个高性能的线程池实现中，任务的提交和执行线程之间可以使        用SynchronousQueue来确保任务被立即执行，而不会在队列中等待。或者在一个简单的两线程通信场景中，一个线程生成的数据要直接交给另一个线程进行处理，避免中间存储。

DelayedQueue

  DelayedQueue是一个支持延迟获取元素的无界阻塞队列，它实现了BlockingQueue接口并且存储的元素必须实现Delayed接口。Delayed接口要求实现类定义一个获取剩余延迟时间的方法（getDelay）和一个比较方法（compareTo），用于确定元素的延迟顺序。DelayedQueue内部会根据元素的延迟时间来排序元素，只有当元素的延迟时间到期后，才能从队列中获取该元素。

主要特点

• 延迟特性：元素在放入队列后，不会立即被获取，而是要等待延迟时间结束。例如，在一个定时任务调度系统中，可以将任务放入DelayedQueue，每个任务有自己的执行时间（延迟时间），队列会根据任务的执行时间来安排任务的获取顺序。

• 排序依据延迟时间：内部按照元素的延迟时间进行排序，延迟时间短的元素会排在队列头部（更接近可以被获取的状态）。这是通过Delayed接口的compareTo方法来实现的，确保了队列中元素的顺序符合延迟时间的要求。

应用场景

        用于实现定时任务调度系统、缓存过期策略等场景。例如，在一个缓存系统中，缓存对象可以实现Delayed接口，设置缓存的过期时间作为延迟时间，放入DelayedQueue。当缓存过期时，从队列中获取到该缓存对象，然后进行清理操作。

PriorityBlockingQueue

  PriorityBlockingQueue是一个支持优先级的无界阻塞队列，它实现了BlockingQueue接口。内部是通过一个可动态调整大小的数组来实现的，元素按照优先级顺序排列，优先级可以通过元素的自然顺序（如果元素实现了Comparable接口）或者通过提供的Comparator来确定。它在多线程环境下是线程安全的，多个线程可以同时对队列进行操作。

主要特点

• 优先级排序：和PriorityQueue类似，元素在队列中按照优先级顺序存储和获取。例如，在一个任务管理系统中，任务可以根据重要性或者紧急程度设置优先级，放入PriorityBlockingQueue后，高优先级的任务会先被获取和处理。

• 无界性和动态调整大小：它是无界的，内部数组会根据元素数量自动调整大小，这使得它可以存储大量的元素，但也需要注意可能导致的内存问题。

• 线程安全：在多线程环境下，多个线程可以安全地插入和获取元素，这是通过内部的锁机制和并发控制来实现的。

应用场景

        适用于多线程环境下需要按照优先级处理任务或元素的场景，如操作系统中的进程调度、分布式系统中的任务分发等。例如，在一个分布式计算系统中，不同的计算任务有不同的优先级，将这些任务放入PriorityBlockingQueue，工作节点可以从队列中获取高优先级的任务先进行处理，提高系统的整体效率。

TransferQueue 接口

  TransferQueue是 Java 中的一个接口，它继承自BlockingQueue接口。这个接口主要用于在生产者 - 消费者模式中实现元素的转移。它允许生产者线程在队列满时等待消费者线程接收元素，而不是简单地阻塞或者抛出异常。

• transfer方法：这是TransferQueue接口的核心方法。生产者线程调用这个方法来传递一个元素e给消费者线程。如果此时有消费者线程正在等待接收元素，那么这个元素会立刻被传递给消费者；如果没有消费者在等待，那么生产者线程会被阻塞，直到有消费者来接收这个元素。

应用场景

        适用于生产者和消费者之间需要紧密同步的场景。例如，在一个多线程的消息传递系统中，当一个消息生产者产生了一个重要消息，它希望确保这个消息能被消费者立即处理，就可以使用TransferQueue。

LinkedTransferQueue

  LinkedTransferQueue是TransferQueue接口的一个实现类，它是基于链表结构实现的无界队列。它在性能上表现良好，特别是在高并发环境下，能够有效地处理元素的插入和移除操作。

特点

• 无界性：它的容量没有固定限制，可以不断地添加元素。不过，如果生产者的速度远远超过消费者的速度，可能会导致内存占用过高。

• 高效性：基于链表的实现使得元素的插入和移除操作在并发环境下具有较高的效率。在添加元素时，只需要对链表的节点进行操作，不需要像数组那样进行扩容等复杂操作。

• 公平性：LinkedTransferQueue支持公平和非公平两种模式。在公平模式下，线程按照它们请求操作的顺序（例如调用transfer方法的顺序）来访问队列；在非公平模式下，不保证这种顺序，新到达的线程可能会先于等待时间较长的线程访问队列。

应用场景

 LinkedTransferQueue适合在高并发的生产者 - 消费者场景中使用，例如在多线程的任务调度系统中，任务生产者将任务放入LinkedTransferQueue，任务消费者从队列中获取任务并执行。由于其无界性和高效性，可以有效地处理大量的任务。

ConcurrentLinkedQueue

        ConcurrentLinkedQueue是一个线程安全的队列，它实现了Queue接口。这个队列是基于链表实现的无界队列，它采用了一种高效的非阻塞算法来保证在并发环境下的正确操作。

特点

• 线程安全：它通过使用 CAS（Compare - And - Swap）操作来实现线程安全。在多个线程同时访问队列时，能够正确地处理元素的插入和移除操作，不会出现数据不一致的情况。

• 无界性：它的容量没有限制，可以容纳任意数量的元素。

• 弱一致性迭代器：ConcurrentLinkedQueue的迭代器是弱一致性的。这意味着在迭代过程中，如果队列被其他线程修改，迭代器可能不会反映这些修改，但是它不会抛出ConcurrentModificationException。

应用场景

        适用于多个生产者和多个消费者并发访问的场景，例如在分布式系统中的消息队列中间件的本地缓存队列，或者在多线程的日志收集系统中，多个线程可以安全地将日志消息添加到ConcurrentLinkedQueue中，然后由其他线程从队列中读取并处理这些消息。

Deque 接口

  Deque（双端队列）接口继承自Queue接口和SequencedCollection接口，它代表的是一种支持在两端进行元素插入和移除操作的线性集合。

        Deque 接口分为两种方法，分别是队首操作和队尾操作的方法，其中包括：

队首操作方法

• addFirst：尝试将指定元素e插入到此双端队列的前端，如果由于容量限制等原因无法立即插入，会抛出IllegalStateException异常。例如，在有容量限制且已满的双端队列上调用此方法就会抛异常。

• offerFirst：将指定元素e插入到此双端队列的前端，除非这样做会违反容量限制。如果插入成功返回true，否则返回false。在使用有容量限制的双端队列时，相较于addFirst方法更合适，因为addFirst只能通过抛异常来表示插入失败。

• removeFirst：检索并移除双端队列的第一个元素，如果队列为空则抛出NoSuchElementException异常。

• pollFirst：检索并移除双端队列的第一个元素，如果双端队列为空则返回null

• getFirst：检索但不移除此双端队列的第一个元素，如果双端队列为空则抛出NoSuchElementException异常。

• peekFirst：检索但不移除此双端队列的第一个元素，如果双端队列为空则返回null

队尾操作方法

• addLast：尝试将指定元素e插入到此双端队列的末尾。如果由于容量限制等原因无法立即插入，会抛出IllegalStateException异常。此方法等同于add方法。

• offerLast：将指定元素e插入到此双端队列的末尾，除非这样做会违反容量限制，插入成功返回true，否则返回false。在使用有容量限制的双端队列时，相较于addLast更合适。

• removeLast：检索并移除双端队列的最后一个元素，如果队列为空则抛出NoSuchElementException异常。

• pollLast：检索并移除双端队列的最后一个元素，如果双端队列为空则返回null。

• getLast：检索但不移除此双端队列的最后一个元素，如果双端队列为空则抛出NoSuchElementException异常。

• peekLast：检索但不移除此双端队列的最后一个元素，如果双端队列为空则返回null。

 使用特点与应用场景

• 作为队列（FIFO - 先进先出）使用时：元素添加到双端队列的末尾（调用addLast、offerLast等方法），从头部移除（调用removeFirst、pollFirst等方法），可以替代传统的Queue实现类，用于需要按顺序处理元素的场景，比如任务队列，按照任务添加的顺序依次执行任务。
• 作为栈（LIFO - 后进先出）使用时：元素在双端队列的头部进行压入（调用push或addFirst方法）和弹出（调用pop或removeFirst方法）操作，相比传统的Stack类，Deque接口提供了更灵活且线程安全的栈操作实现方式，适用于方法调用栈模拟、表达式求值等需要后进先出逻辑的场景。

ArrayDeque

  ArrayDeque是一种基于数组的双端队列。这意味着它可以高效地在两端进行插入和删除操作，并且具有动态调整大小的能力。它是一种非线程安全的集合类，如果需要在多线程环境下使用，可以通过适当的同步措施（如使用Collections.synchronizedDeque方法）来确保线程安全。

数据结构

  ArrayDeque内部使用一个数组来存储元素。它有两个指针，分别指向队列的头部和尾部，这样就可以方便地在两端进行操作。当元素被添加到头部或尾部时，指针会相应地移动。

        例如，在初始状态下，队列为空，头指针和尾指针都指向数组的起始位置。当添加一个元素到头部时，头指针会向左移动（如果数组是循环使用的话），然后将元素放置在新的头指针位置；添加元素到尾部时，尾指针向右移动，元素放置在尾指针位置。

线程安全的 Deque

BlockingDeque

   BlockingDeque是 Java 中的一个接口，它继承自Deque和BlockingQueue接口。这个接口在双端队列的基础上，提供了阻塞式的操作方法，主要用于在多线程环境下实现生产者 - 消费者模式等场景，使得线程在队列满或空时能够阻塞等待，而不是直接返回错误或异常。

 应用场景

        适合用于需要在多线程环境下，对双端队列进行安全且阻塞式操作的场景。比如在一个多线程的消息传递系统中，消息生产者和消费者通过BlockingDeque进行通信，当没有消息时消费者阻塞等待，当队列满时生产者阻塞等待。 

LinkedBlockingDeque

  LinkedBlockingDeque是BlockingDeque接口的一个实现类，它基于链表结构实现阻塞式双端队列。它的容量可以在初始化时指定，如果不指定容量，默认是Integer.MAX_VALUE，也就是一个无界队列。

特点

• 链表结构的优势：基于链表实现使得它在插入和删除操作时比较灵活，不需要像数组那样考虑扩容和元素移动的问题。在并发环境下，多个线程对队列两端进行操作时，链表结构能够有效地减少锁竞争，提高并发性能。

• 阻塞操作的实现：通过内部的锁和条件队列（Condition）来实现阻塞式操作。当队列满或空时，线程会在相应的条件队列中等待，直到其他线程执行了相应的插入或移除操作，唤醒等待的线程。

• 容量灵活性：可以根据实际需求在初始化时设定容量。如果确定是有界队列场景，设定合适的容量可以避免过度占用内存。

应用场景

        适用于高并发的生产者 - 消费者场景，特别是当生产者和消费者的速度可能不一致，且需要保证在队列满或空时线程能够正确等待的情况。例如在一个多线程的文件读取和处理系统中，文件读取线程作为生产者将读取到的文件内容放入LinkedBlockingDeque，文件处理线程作为消费者从队列中获取内容进行处理。 

ConcurrentLinkedDeque

   ConcurrentLinkedDeque是一个线程安全的双端队列，它实现了Deque接口。它是基于链表的无界队列，采用非阻塞算法（主要是通过 CAS 操作）来保证在并发环境下的操作正确性。

特点

• 线程安全的非阻塞实现：它使用 CAS（Compare - And - Swap）操作来实现多线程环境下的并发控制。CAS 操作是一种乐观锁机制，在更新元素时会先比较当前值与预期值，如果相同则更新，不同则表示有其他线程已经修改了该值，此时会重试操作。这种方式避免了传统锁机制可能带来的线程阻塞和性能下降问题。

• 无界性和动态性：作为无界队列，它可以容纳任意数量的元素，不会因为队列满而拒绝插入元素。并且其链表结构使得它能够动态地适应元素数量的变化。

• 弱一致性迭代器：ConcurrentLinkedDeque的迭代器是弱一致性的。这意味着在迭代过程中，如果队列被其他线程修改，迭代器可能不会反映这些修改，但是它不会抛出ConcurrentModificationException。 

应用场景

        适用于高并发的场景，特别是多个生产者和多个消费者同时对双端队列进行操作的情况。例如在分布式系统中的消息中间件，多个生产者可以将消息发送到ConcurrentLinkedDeque作为本地缓存队列，多个消费者可以同时从队列中获取消息进行处理，而且不用担心线程阻塞问题，能够高效地处理大量消息。 

参考文献

豆包

相关文章推荐

Wend看源码-Java-集合学习(List)-CSDN博客
Wend看源码-Java-集合学习(Set)-CSDN博客