Java 队列接口及其实现

在这里，我们将讨论 Java Queue 接口。您将了解什么是队列数据结构，它在 Java 中是如何表示的，哪些方法对所有队列最重要。此外，Queue 的哪些实现是用 Java 语言编写的。之后，我们将仔细研究最重要的实现并通过示例来学习它们。

队列数据结构

队列是一种线性抽象数据结构，具有特定的执行操作顺序——先进先出 (FIFO)。这意味着您只能在结构的末尾添加一个元素（或入队，放入队列），并且只能从其开头获取一个元素（出队或从队列中删除）。你可以很容易地想象队列数据结构。这看起来就像现实生活中的队列或客户队列。先来的顾客，也将先得到服务。如果你有四个人在麦当劳或其他地方排队，那么第一个排队的人将第一个拿到商店。如果新顾客来了，他/她将排在第 5 位去买汉堡包。 所以，在使用队列时，新元素被添加到末尾，如果你想获取一个元素，它将从头开始获取。这是经典队列数据结构工作的主要原则。

Java中的队列

Java中的队列是一个接口。根据 Oracle 文档，Queue 接口有 2 个超接口、4 个继承自队列的不同接口，以及一个极其令人印象深刻的类列表。 这是什么意思？首先，Java Queue是Collection Framework的一部分，实现了Collection接口。所以它支持Collection接口的所有方法，如插入、删除等。Queue 实现 Iterable 接口，允许对象成为“for-each 循环”语句的目标。

队列方法 Java

Queue 声明了许多方法。作为接口的方法，它们应该在所有实现 Queue 的类中表示。最重要的队列方法，Java：

• Boolean offer() – 如果可能，将一个新元素插入队列
• Boolean add(E e) – 如果可能，将一个新元素插入队列。如果成功则返回 true，如果没有空间则抛出 IllegalStateException。
• Object poll() – 从 的头部检索并删除一个元素。如果队列为空，则返回 null。
• Object remove() – 从队列头部检索并删除一个元素。
• Object peek() – 检索但不从队列头部移除元素。如果队列为空，则返回 null。
• Object element() – 检索但不从队列头部移除元素。

Java队列的子接口

Queue接口由 4 个子接口继承——BlockingDeque<E>、BlockingQueue<E>、Deque<E>、TransferQueue<E>。您可以将它们分为 3 组：Deques、Blocking Queues 和 Transfer Queues，其中 BlockingDeque 属于前两者。让我们来看看这些群体。

德奎斯

Deque 的意思是双端队列，它支持从作为队列（先进先出/FIFO）的数据尾部添加或删除数据，或者作为另一种流行的称为堆栈（后进先出）的数据结构从头部添加或删除先出/后进先出）。 实现Deque接口的类： ArrayDeque、ConcurrentLinkedDeque、LinkedBlockingDeque、LinkedList。

阻塞队列

阻塞队列是在两种情况下阻塞线程的队列：

• 线程试图从空队列中获取元素
• 线程试图将元素放入完整队列

当一个线程试图从一个空队列中获取项目时，它会等待直到其他线程将项目放入队列中。类似地，当一个线程试图将元素放入一个已满的队列时，它会一直等到其他线程将元素从队列中取出来为元素获取可用空间。当然，“满队列”的概念意味着队列的大小是有限的，这通常在构造函数中指定。标准阻塞队列包括 LinkedBlockingQueue、SynchronousQueue 和 ArrayBlockingQueue。BlockingQueue接口的实现类：ArrayBlockingQueue、DelayQueue、LinkedBlockingDeque、LinkedBlockingQueue、LinkedTransferQueue、PriorityBlockingQueue、SynchronousQueue。 阻塞双端队列是 BlockingQueue 的子接口。BlockingQueue等BlockingDeque是一个阻塞队列，但是是双向的。所以它继承了Deque接口的属性。它面向多线程执行，不允许零元素并且容量可能受到限制。如果队列为空，则 BlockingDeque 接口的实现会阻止获取元素的操作，如果队列已满，则将元素添加到队列中。

传输队列

TransferQueue 接口扩展了 BlockingQueue 接口。但是，与 BlockingQueue 接口队列的实现不同，如果队列为空（读取）或队列已满（写入），线程可能会被阻塞，TransferQueue 接口队列会阻塞写入流，直到另一个流检索元素。为此使用传输方法。也就是说，BlockingQueue的实现保证Producer创建的元素一定在队列中，而TransferQueue的实现保证Producer元素被Consumer“接收”。TransferQueue 接口的官方 Java 实现只有一个——LinkedTransferQueue。

Java 队列实现

有很多类实现了 Queue 接口：

• AbstractQueue根据 Queue Java 8 文档，这个抽象类提供了一些 Queue 操作的基本实现。它不允许空元素。基于Queue经典的offer、poll、peek分别增加了3个方法add、remove、element 。但是，它们会抛出异常，而不是通过返回 false 或 null 来指示失败。
• ArrayBlockingQueue — 由数组支持的固定大小的 FIFO 阻塞队列
• ArrayDeque — Deque 接口的可调整大小的数组实现
• ConcurrentLinkedDeque — 基于链接节点的无界并发双端队列。
• ConcurrentLinkedQueue — 基于链接节点的无界线程安全队列。
• DelayQueue — 由堆支持的基于时间的调度队列
• LinkedBlockingDeque — Deque 接口的并发实现。
• LinkedBlockingQueue — 由链接节点支持的可选边界 FIFO 阻塞队列
• LinkedList — List 和 Deque 接口的双向链表实现。实现所有可选列表操作，并允许所有元素（包括 null）
• LinkedTransferQueue — 基于链接节点的无界传输队列
• PriorityBlockingQueue — 由堆支持的无界阻塞优先级队列
• PriorityQueue——基于堆数据结构的优先级队列
• SynchronousQueue — 一个阻塞队列，其中每个插入操作都必须等待另一个线程的相应删除操作，反之亦然。

最流行的实现是 LinkedList、ArrayBlockingQueue 和 PriorityQueue。让我们看看它们并做一些例子以便更好地理解。

链表

Java 中的 LinkedList 类实现了 List 和 Deque 接口。所以，它是 List 和 Deque 的组合，一个双向队列，支持从两侧添加和删除元素。在 Java 中，LinkedList 是双向链表：List 的每个元素都调用 Node 并包含一个对象和对两个相邻对象（前一个和下一个）的引用。 您可能会说 LinkedList 在使用内存方面不是很有效。没错，但是这种数据结构在插入和删除操作性能方面可能很有用。然而，它只有在你为它们使用迭代器时才会发生（在这种情况下它发生在恒定时间内）。通过从头到尾（取较近的）搜索所需元素来执行按索引的访问操作。但是，不要忘记在元素之间存储引用的额外成本。因此，LinkedList 是 Java 中最流行的队列实现。它也是 List 和 Deque 的实现，它允许我们创建一个双向队列，该队列由包括 null 在内的任何对象组成。LinkedList 是元素的集合。

链表构造函数

不带参数的LinkedList()用于构造一个空列表。 LinkedList(Collection<? extends E> c)用于创建包含指定集合的​​元素的列表，它们按顺序由集合的迭代器返回。

主要链表方法：

• add(E element) 将指定的元素附加到此列表的末尾；
• add(int index, E element) 在指定位置index处插入元素；
• get(int index) 返回此列表中指定位置的元素；
• remove(int index) 移除索引位置的元素；
• remove(Object o) 从此列表中移除第一个出现的 ?o 元素（如果存在）。
• remove() 检索并删除列表的第一个元素。
• addFirst(), addLast() 添加一个元素到列表的开头/结尾
• clear() 从列表中删除所有元素
• 如果列表包含 o 元素，则 contains(Object o) 返回 true。
• indexOf(Object o) 返回 o 元素第一次出现的索引，如果不在列表中则返回 -1。
• set(int index, E element) 用元素替换索引位置的元素
• size() 返回列表中元素的数量。
• toArray() 返回一个数组，其中包含列表中从第一个元素到最后一个元素的所有元素。
• pop() 从堆栈中弹出一个元素（由列表表示）
• push(E e) 将元素推入堆栈（由此列表表示）

Java 队列示例——LinkedList（以不同方式放置和删除元素）

import java.util.*;
 
public class LinkedListTest {
 
       public static void main(String args[]){
 
           LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
           myLinkedList.add(1);
           myLinkedList.add(2);
           myLinkedList.add(4);
           System.out.println("three added elements: " + myLinkedList);
           //put one element into the head, not to the tail:
           myLinkedList.push(5);
           System.out.println("The new element last in will be the first: " + myLinkedList);
           //add new element at the specified position:
           myLinkedList.add(4,3);
           //put one element into the head, not to the tail (same as push):
           myLinkedList.addFirst(6);
           System.out.println(myLinkedList);
           //now remove element no 2 (it is 1):
           myLinkedList.remove(2);
           System.out.println(myLinkedList);
           //now remove the head of the list
           myLinkedList.pop();
           System.out.println(myLinkedList);
           //remove with the other method
           myLinkedList.remove();
           System.out.println(myLinkedList);
           //and with one more
           myLinkedList.poll();
           System.out.println(myLinkedList);
       }
       }

优先队列

PriorityQueue不完全是FIFO一般意义上的队列。优先级队列的元素根据它们的自然顺序进行排序，或者由队列构造时提供的比较器排序，具体取决于使用的构造函数。然而，它不是像列表这样的线性结构中的顺序（从最大到最小，反之亦然）。基于优先级最小堆的优先级队列。堆是一种基于二叉树的数据结构. 每个父母的优先权大于其子女的优先权。如果每个父节点不超过两个子节点，并且级别的填充从上到下（从同一级别 - 从左到右），则一棵树称为完全二叉树。每次向其中添加或删除新元素时，二叉堆都会自行重组。在最小堆的情况下，无论插入顺序如何，最小的元素都会进入根。基于这个最小堆的优先级队列，所以如果我们有一个整数 PriorityQueue，它的第一个元素将是这些数字中最小的。如果删除根，则下一个最小的成为根。

主要的 PriorityQueue 方法：

• boolean add(object)将指定的元素插入到优先级队列中。成功时返回真。如果队列已满，该方法将抛出异常。
• boolean offer(object)将指定元素插入此优先级队列。如果队列已满，则该方法返回 false。
• boolean remove(object)从此队列中移除指定元素的单个实例（如果存在）。
• 对象 poll()检索并删除此队列的头部。如果队列为空，则返回 null。
• void clear()从优先级队列中删除所有元素。
• Object element()检索此队列的头部而不删除它。如果队列为空，则抛出 NoSuchElementException。
• 对象 peek()检索队列的头部而不删除它。如果队列为空，则返回 null。
• 如果队列包含 o 元素，则boolean contains(Object o)返回 true。
• int size()返回此队列中的元素数。

优先队列的例子

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

重要的是要了解优先级队列是基于二叉堆的，因此它们不会使元素保持线性排序。从根到叶的每条路都是有序的，但从根到不同的路则不是。这意味着您可以非常快速地获取队列的最小元素。如果你每次都删除头部，你将打印一个排序结构。

数组阻塞队列

ArrayBlockingQueue的内部数据结构是基于一个循环数组来存储元素的。它是一个典型的队列（FIFO），以防新元素插入队列尾部，提取操作从队列头部返回一个元素。队列容量一旦创建就无法更改。尝试将元素插入（放置）到已满队列会导致阻塞流程；试图从空队列中取出一个元素也会阻塞线程。正如我们之前所说，这个数组是圆形的。这意味着数组的第一个和最后一个元素在逻辑上是相邻的。每次将元素放入队列或从队列中移除时，队列都会推进头元素和尾元素的索引。如果某个索引推进数组的最后一个元素，它会从 0 重新开始。因此，在头部移除的情况下，队列不必移动所有元素（就像在通常的数组中一样）。但是，在从中间移除元素（使用 Iterator.remove）的情况下，元素会移动。 ArrayBlockingQueue支持在构造函数中使用fair参数的附加公平策略，以对生产者（插入元素）和消费者（提取元素）的等待流的工作进行排序。默认情况下，不保证顺序。但是，如果队列是使用“fair == true”创建的，则 ArrayBlockingQueue 类的实现以 FIFO 顺序提供线程访问。股权通常会减少带宽，但也会降低波动性并防止资源耗尽。

ArrayBlockingQueue 类构造函数

• ArrayBlockingQueue (int capacity)创建一个具有固定容量和默认访问策略的队列。
• ArrayBlockingQueue (int capacity, boolean fair)创建一个具有固定容量和指定访问策略的队列。
• ArrayBlockingQueue (int capacity, boolean fair, Collection <? extends E> c)创建一个由访问策略指定的具有固定容量的队列，并包含队列中的元素。

这里我们有 BlockingQueueExample 示例。我们创建一个 ArrayBlockingQueue 队列，其容量为一个元素和一个公平标志。启动了两个线程。其中第一个是生产者线程，它使用 put 方法对来自消息数组的消息进行排队。第二个 Consumer 线程使用take方法从队列中读取元素并将它们显示在控制台中。元素的顺序是队列的自然顺序。

import java.util.concurrent.*;
 
public class ArrayBlockingQueueExample {
 
   private BlockingQueue<Integer> blockingQueue;
   private final Integer[]  myArray = {1,2,3,4,5};
  
       public ArrayBlockingQueueExample ()
       { blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
           (new Thread(new Producer())).start();
           (new Thread(new Consumer())).start();
       }
 
       class Producer implements Runnable
       {
           public void run() {
               try {
                   int counter = 0;
                   for (int i=0; i < myArray.length; i++) {
                       blockingQueue.put(myArray[i]);
                       if (counter++ < 2)
                           Thread.sleep(3000);
                   } blockingQueue.put(-1);
               }
               catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }
 
       class Consumer implements Runnable
       {
           public void run() {
               try {
                   Integer message = 0;
                   while (!((message = blockingQueue.take()).equals(-1)))
                       System.out.println(message);
               } catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }
 
       public static void main(String[] args) {
           new ArrayBlockingQueueExample();
       }
   }

输出是自然顺序的队列；前两个元素出现延迟。 为了巩固您所学的知识，我们建议您观看我们的 Java 课程中的视频课程

结论

• Queue 用于在队列末尾插入元素并从队列开头移除元素。它遵循 FIFO 概念。
• Java Queue 是 Collection Framework 的一部分，实现了 Collection 接口。所以它支持Collection接口的所有方法，如插入、删除等。
• Queue 最常用的实现是 LinkedList、ArrayBlockingQueue 和 PriorityQueue。
• 优先级队列的元素根据它们的自然顺序进行排序，或者由队列构造时提供的比较器排序，具体取决于使用的构造函数。
• 如果对 BlockingQueues 执行任何 null 操作，则会抛出 NullPointerException。