Guide to the Java Queue Interface – Java队列接口指南

最后修改: 2019年 1月 12日

中文/混合/英文(键盘快捷键：t)

1. Introduction

1.绪论

In this tutorial, we’ll be discussing Java’s Queue interface.

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

First, we’ll take a peek at what a Queue does, and some of its core methods. Next, we’ll dive into a number of implementations that Java provides as standard.

首先，我们将看一看队列的作用，以及它的一些核心方法。接下来，我们将深入研究Java提供的一些标准的实现。

Finally, we’ll talk about thread safety before wrapping it all up.

最后，我们将在结束前谈谈线程安全问题。

2. Visualizing the Queue

2.队列的可视化

Let’s start with a quick analogy.

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

Imagine we’ve just opened our first business – a hot dog stand. We want to serve our new potential clients in the most efficient way possible for our small business; one at a time. First, we ask them to form an orderly line in front of our stand, with new customers joining at the rear. Thanks to our organization skills, we can now distribute our tasty hot dogs in a fair way.

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

Queues in Java work in a similar way. After we declare our Queue, we can add new elements to the back, and remove them from the front.

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

In fact, most Queues we’ll encounter in Java work in this first in, first out manner – often abbreviated to FIFO.

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

However, there’s one exception that we’ll touch upon later.

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

3. Core Methods

3.核心方法

The Queue declares a number of methods that need to be coded by all implementing classes. Let’s outline a few of the more important ones now:

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

  1. offer() – Inserts a new element onto the Queue
  2. poll() – Removes an element from the front of the Queue
  3. peek() – Inspects the element at the front of the Queue, without removing it

4. AbstractQueue

4.抽象队列

AbstractQueue is the simplest possible Queue implementation that Java provides. It includes a skeletal implementation of some of the Queue interface’s methods, excluding offer.

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

When we create a custom queue extending the AbstractQueue class, we must provide an implementation of the offer method which does not allow the insertion of null elements.

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

Additionally, we must provide the methods peek, poll, size, and java.util‘s iterator.

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

Let’s put together a simple Queue implementation using AbstractQueue.

让我们使用AbstractQueue.拼凑一个简单的Queue实现。

First, let’s define our class with a LinkedList to store our Queue’s elements:

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

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

    private LinkedList<T> elements;

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

}

Next, let’s override the required methods and provide the code:

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

@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();
}

Excellent, let’s check that it works with a quick unit test:

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

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

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

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

4. Sub-interfaces

4.子接口

Generally, the Queue interface is inherited by 3 main sub-interfaces. Blocking Queues, Transfer Queues, and Deques.

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

Together, these 3 interfaces are implemented by the vast majority of Java’s available Queues. Let’s take a quick look at what these interfaces have been set out to do.

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

4.1. Blocking Queues

4.1.阻断队列

The BlockingQueue interface supports additional operations which force threads to wait on the Queue depending on the current state. A thread may wait on the Queue to be non-empty when attempting a retrieval, or for it to become empty when adding a new element.

BlockingQueue接口支持额外的操作，这些操作迫使线程根据当前状态在Queue上等待。在尝试检索时，线程可能会等待Queue为非空，或者在添加新元素时等待它为空。

Standard Blocking Queues include LinkedBlockingQueue, SynchronousQueue, and ArrayBlockingQueue.

标准的阻塞队列包括LinkedBlockingQueue，SynchronousQueue，和ArrayBlockingQueue。

For more information, head over to our article on Blocking Queues.

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

4.2. Transfer Queues

4.2 传输队列

The TransferQueue interface extends the BlockingQueue interface but is tailored toward the producer-consumer pattern. It controls the flow of information from producer to consumer, creating backpressure in the system.

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

Java ships with one implementation of the TransferQueue interface, LinkedTransferQueue.

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

4.3. Deques

4.3.Deques</em

Deque is short for Double-Ended Queue and is analogous to a deck of cards – elements may be taken from both the start and end of the Deque. Much like the traditional Queue, the Deque provides methods to add, retrieve and peek at elements held at both the top and bottom.

Deque是Double-Ended Queue的缩写，类似于一副牌–元素可以从Deque的起点和终点取出。与传统的Queen非常相似，Deque提供了添加、检索和偷看保存在顶部和底部的元素的方法。

For a detailed guide on how the Deque works, check out our ArrayDeque article.

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

5. Priority Queues

5.优先级队列

We saw earlier that most of the Queues that we come across in Java follow the FIFO principle.

我们在前面看到，我们在Java中遇到的大多数Queue都遵循FIFO原则。

One such exception to this rule is the PriorityQueue. When new elements are inserted into the PriorityQueue, they are ordered based on their natural ordering, or by a defined Comparator provided when we construct the PriorityQueue.

这个规则的一个例外是PriorityQueue。当新元素被插入到Priority队列中时，它们会根据它们的自然排序，或者通过我们构建Priority队列时提供的定义Comparator。

Let’s take a look at how this works with a simple unit test:

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

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);

Despite the order in which our integers were added to the PriorityQueue, we can see that the retrieval order is changed according to the natural order of the numbers.

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

We can see that the same is also true when applied to Strings:

我们可以看到，在应用于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. Thread Safety

6.螺纹安全

Adding items to Queues is particularly useful in multi-threaded environments. A Queue can be shared amongst threads, and be used to block progress until space is available – helping us overcome some common multi-threaded problems.

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

For example, writing to a single disk from multiple threads creates resource contention and can lead to slow writing times. Creating a single writer thread with a BlockingQueue can alleviate this issue and lead to vastly improved write speeds.

例如，从多个线程向单个磁盘写入会产生资源争夺，并可能导致缓慢的写入时间。创建一个带有BlockingQueue的单一写入器线程可以缓解这一问题，并导致大大改善写入速度。

Luckily, Java offers ConcurrentLinkedQueue, ArrayBlockingQueue, and ConcurrentLinkedDeque which are thread-safe and perfect for multi-threaded programs.

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

7. Conclusion

7.结语

In this tutorial, we’ve taken a deep dive into the Java Queue interface.

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

Firstly, we explored what a Queue does, as well as the implementations that Java provides.

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

Next, we looked at a Queue’s usual FIFO principle, as well as the PriorityQueue which differs in its ordering.

接下来，我们看了一个队列的通常FIFO原则，以及PriorityQueen，它在排序方面有所不同。

Finally, we explored thread safety and how Queues can be used in a multi-threaded environment.

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

As always, the code is available over on GitHub.

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