Java Queue 接口的指南

1.绪论

在本教程中，我们将讨论Java的Queue接口。

首先，我们将一瞥Queue 的功能及其一些核心方法。接下来，我们将深入探讨 Java 作为标准提供的一些实现。

最后，我们将在结束前讨论一下线程安全问题。

2.队列的可视化

让我们从一个简单的比喻开始。

想象一下，我们刚刚开了我们的第一个生意 – 一个热狗摊。我们想以最有效的方式为我们的小生意的潜在新客户提供服务；一次一个。首先，我们要求他们在我们的摊位前有序地排好队，新客户在后面加入。由于我们的组织能力，我们现在可以以公平的方式分发我们美味的热狗。

Java中的Queue工作方式类似。在我们声明了我们的Queue之后，我们可以在后面添加新的元素，并从前面删除它们。

事实上，我们在Java中遇到的大多数队列都是以这种先入先出的方式工作的 – 通常被缩写为FIFO。

然而，有一个例外，我们将在后面的中提及。

3.核心方法

Queen 声明了若干方法，这些方法需要由所有的实现类来编码。让我们现在概述一下几个比较重要的方法：

offer() – 在Queue上插入一个新的元素。
poll() – 从Queue的前面删除一个元素。
peek() – 检查Queue的前面的元素，而不删除它。

4.抽象队列

AbstractQueue 是Java提供的最简单的Queue实现。它包括Queue接口的一些方法的骨架实现，不包括offer。

当我们创建一个自定义队列扩展AbstractQueue类时， 我们必须提供一个实现 的offer 方法，它不允许插入null元素。

此外，我们必须提供方法peek，poll，size，和java.util的iterator。

让我们把一个简单的队列实现使用AbstractQueue.的队列放在一起。

首先，让我们用一个LinkedList 来定义我们的类，以存储我们的Queen的元素。

public class CustomBaeldungQueue<T> extends AbstractQueue<T> {

    private LinkedList<T> elements;

    public CustomBaeldungQueue() {
      this.elements = new LinkedList<T>();
    }

}

接下来，让我们覆盖所需的方法，并提供代码：

@Override
public Iterator<T> iterator() {
    return elements.iterator();
}

@Override
public int size() {
    return elements.size();
}

@Override
public boolean offer(T t) {
    if(t == null) return false;
    elements.add(t);
    return true;
}

@Override
public T poll() {
    Iterator<T> iter = elements.iterator();
    T t = iter.next();
    if(t != null){
        iter.remove();
        return t;
    }
    return null;
}

@Override
public T peek() {
    return elements.getFirst();
}

很好，让我们用一个快速的单元测试来检查它是否正常工作。

customQueue.add(7);
customQueue.add(5);

int first = customQueue.poll();
int second = customQueue.poll();

assertEquals(7, first);
assertEquals(5, second);

4.子接口

一般来说，Queue接口由3个主要的子接口继承。阻塞队列、传输队列和双端队列。

这3个接口一起被绝大多数的Java可用的Queues.所实现。让我们快速看看这些接口被设定为做什么的。

4.1.阻断队列

BlockingQueue interface支持额外的操作，迫使线程在Queue 上等待，这取决于当前状态。当尝试检索时，线程可能会等待Queue非空，或者当添加新元素时，它可能会变成空。

标准的阻塞队列包括链接阻塞队列、同步队列、 和ArrayBlockingQueue。

欲了解更多信息，请浏览我们关于阻塞队列的文章。

4.2 传输队列

TransferQueue 接口扩展了BlockingQueue接口，但针对生产者-消费者模式进行了定制。它控制从生产者到消费者的信息流，在系统中产生背压。

Java提供了一个TransferQueue 接口的实现，LinkedTransferQueue.。

4.3. 双端队列

Deque 是 Double-Ended Queue 的缩写，类似于一副纸牌 - 可以从 Deque 的开头和结尾获取元素。很像传统的队列，双端队列提供了添加、检索和查看顶部和底部元素的方法。。

关于Deque 如何工作的详细指南，请查看我们的ArrayDeque 文章。

5.优先级队列

我们在前面看到，我们在Java中遇到的大多数队列都是遵循先进先出的原则。

此规则的一个例外是PriorityQueue。当新元素被插入到优先级队列中时，它们会根据它们的自然顺序或定义的 Comparator 在我们构造优先级队列时提供。

让我们来看看这一点是如何通过一个简单的单元测试来实现的。

PriorityQueue<Integer> integerQueue = new PriorityQueue<>();

integerQueue.add(9);
integerQueue.add(2);
integerQueue.add(4);

int first = integerQueue.poll();
int second = integerQueue.poll();
int third = integerQueue.poll();

assertEquals(2, first);
assertEquals(4, second);
assertEquals(9, third);

尽管我们的整数被添加到PriorityQueue的顺序，我们可以看到检索顺序是根据数字的自然顺序改变的。

我们可以看到，当应用于Strings时，也是如此。

PriorityQueue<String> stringQueue = new PriorityQueue<>();

stringQueue.add("blueberry");
stringQueue.add("apple");
stringQueue.add("cherry");

String first = stringQueue.poll();
String second = stringQueue.poll();
String third = stringQueue.poll();

assertEquals("apple", first);
assertEquals("blueberry", second);
assertEquals("cherry", third);

6.线程安全

将项目添加到Queue在多线程环境中特别有用。一个Queue可以在线程之间共享，并被用来阻止进度，直到空间可用 – 帮助我们克服一些常见的多线程问题。

例如，从多个线程写入单个磁盘会造成资源争用，并可能导致写入时间变慢。使用BlockingQueue创建单个写入线程可以缓解此问题并大大改善写入速度。

幸运的是，Java提供了ConcurrentLinkedQueue、ArrayBlockingQueue和ConcurrentLinkedDeque，它们都是线程安全的，非常适合多线程程序。

7.结语

在本教程中，我们对Java Queue 接口进行了深入的研究。

首先，我们探索了队列的作用，以及 Java 提供的实现。

接下来，我们看了队列的通常FIFO原则，以及优先级队列，后者在排序上有所不同。

最后，我们探讨了线程安全以及如何在多线程环境中使用Queue。

像往常一样，代码可以在GitHub上获得。