Fixed Size Queue Implementations in Java – Java中固定大小队列的实现

最后修改: 2022年 9月 16日

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

1. Overview

1.概述

In this article, we’ll learn what Java offers about queues. Firstly, we’ll explore the basics of the queues from the Java Collections Framework.

在这篇文章中，我们将学习Java提供的关于队列的内容。首先，我们将从Java集合框架中探讨队列的基本知识。

Next, we’ll explore the fixed-sized queue implementations in the Java Collections Framework. Finally, we’ll create a fixed-size queue implementation.

接下来，我们将探索Java集合框架中的固定尺寸队列实现。最后，我们将创建一个固定大小的队列实现。

2. Java Collections Framework Queues

2.Java集合框架队列

The Java Collections Framework offers different queue implementations which we can use depending on our needs. For instance, if we need a thread-safe implementation, we could use the ConcurrentLinkedQueue. Likewise, if we need to specify how the elements must be ordered inside the queue, we could use the PriorityQueue.

Java Collections Framework 提供了不同的queue实现，我们可以根据自己的需要来使用。例如，如果我们需要一个线程安全的实现，我们可以使用ConcurrentLinkedQueue。同样地，如果我们需要指定元素在队列中必须如何排序，我们可以使用 PriorityQueue。

The Java Collections Framework offers a few different fixed-size queues implementations. One such implementation is the ArrayBlockingQueue – a FIFO bounded queue using a fixed array to store the elements. The size of the queue can’t be modified once it’s created.

Java集合框架提供了一些不同的固定尺寸队列实现。其中一个实现是ArrayBlockingQueue – 一个使用固定数组来存储元素的FIFO边界队列。一旦队列被创建，它的大小就不能被修改。

Another example is LinkedBlockingQueue. This implementation is also a FIFO queue, but it’s optionally bounded, so if the capacity isn’t set, then the limit of the queue will be Integer.MAX_VALUE elements. Linked queues offer better throughput than array queues when we aren’t in a concurrent environment.

另一个例子是LinkedBlockingQueue。这个实现也是一个 FIFO 队列，但是它可以选择边界，所以如果没有设置容量，那么队列的极限将是Integer.MAX_VALUE元素。当我们不在并发环境中时，链接队列比数组队列提供更好的吞吐量。

The last fixed-size queue that we can find in the Java Collections Framework is the LinkedBlockingDeque implementation. However, let’s note that this class implements the Deque interface and not only the Queue interface.

我们可以在Java Collections Framework中找到的最后一个固定大小的队列是LinkedBlockingDeque实现。然而，让我们注意到这个类实现了Deque接口，而不仅是Queue接口。

Although the framework offers many queue implementations, we may not always find one to suit our solution. In this scenario, we can create our own implementation.

尽管该框架提供了许多队列实现，但我们不一定能找到适合我们的解决方案。在这种情况下，我们可以创建自己的实现。

3. Queue Interface in Java

3.Java中的Queue接口

In order to understand the example better, let’s take a closer look at the Queue interface. The Queue interface extends the Collection interface and adds specific insertion, extraction, and inspection operations. Each operation has two forms, one that will throw an exception if the operation fails and the other which will return a specific value.

为了更好地理解这个例子，让我们仔细看看Queue接口。Queue接口扩展了Collection接口并且加入了特定的插入、提取和检查操作。每个操作都有两种形式，一种是在操作失败时抛出一个异常，另一种是返回一个特定的值。。

Let’s take a look at the insertion operations defined in the Queue interface:

让我们来看看Queue接口中定义的插入操作。

boolean add(E e);
boolean offer(E e);

Both will add a new element to the tail of the queue if it’s not full. The offer() method will return false when the queue is full, and the element can’t be inserted, but the add() method will throw an IllegalStateException exception.

如果队列未满，两者都将在队列的尾部添加一个新元素。当队列已满，元素不能被插入时，offer()方法将返回false，但add()方法将抛出IllegalStateException异常。

Next, we have the extraction operations defined in the Queue interface:

接下来，我们有在Queue接口中定义的提取操作。

E remove();
E poll();

These methods will return the head of the queue and will remove the element from the queue. The difference between them is that the poll() method will return null if the queue is empty, while the remove() method will throw a NoSuchElementException exception.

这些方法将返回队列的头部，并将从队列中删除该元素。它们之间的区别是，如果队列是空的，poll()方法将返回null，而remove()方法将抛出NoSuchElementException异常。

Finally, the inspection methods defined in the Queue interface:

最后，在Queue接口中定义的检查方法。

E element();
E peek();

Notice the type E in all the methods of the Queue interface. This means that the Queue interface is generic:

注意在Queue接口的所有方法中的类型E。这意味着Queue接口是generic。

public interface Queue<E> extends Collection<E> {
    // ...
}

4. FIFO Fixed-Size Queue Implementation, Which Removes Oldest Element When Full

4.固定大小的FIFO队列的实施，当满员时删除最老的元素

Let’s create our queue implementation, a fixed-size FIFO queue that will remove the eldest element when it’s full. Let’s call it FifoFixedSizeQueue.

让我们来创建我们的队列实现，一个固定大小的 FIFO 队列，当它满了的时候会移除最长的元素。让我们把它叫做FifoFixedSizeQueue。

The AbstractQueue abstract class is a good starting point because it defines a FIFO queue and implements most of the methods from Queue and Collection interfaces.

AbstractQueue 抽象类是一个很好的起点，因为它定义了一个 FIFO 队列并实现了 Queue 和 Collection 接口中的大多数方法。

Let’s implement the fixed-size queue as an array of elements. We’ll use an array of Object to store our data, which allows us to insert objects of any type. Also, we’ll keep a count attribute to indicate the number of elements in the queue:

让我们将固定大小的队列实现为一个元素数组。我们将使用一个Object数组来存储我们的数据，这使我们可以插入任何类型的对象。另外，我们将保留一个count属性来表示队列中元素的数量。

public class FifoFixedSizeQueue<E> extends AbstractQueue<E> {
    final Object[] items;
    int count;

    public FifoFixedSizeQueue(int capacity) {
        super();

        items = new Object[capacity];
        count = 0;
    }

    ...
}

Above, we can see that the constructor initializes the array that will hold the queue’s elements and the count attribute. As the queue is empty, all the elements of the array will be null, and the count attribute will be zero.

在上面，我们可以看到构造函数初始化了将保存队列元素的数组和count属性。由于队列是空的，数组中的所有元素将是null,，count属性将是零。

Next, let’s implement all of the abstract methods.

接下来，让我们实现所有的抽象方法。

4.1. offer() Method Implementation

4.1. offer()方法实现

The main rule is that all the elements should be inserted, but if the queue is full, the eldest element must be removed before. We also need to make sure that the queue won’t allow the insertion of null elements:

主要的规则是，所有的元素都应该被插入，但是如果队列已经满了，最年长的元素必须先被移除。我们还需要确保队列不允许插入null元素：。

public boolean offer(E e) {
    if (e == null) {
        throw new NullPointerException("Queue doesn't allow nulls");
    }
    if (count == items.length) {
        this.poll();
    }
    this.items[count] = e;
    count++;
    return true;
}

First, as nulls aren’t allowed, we check if the element is null. If this is the case, we throw a NullPointerException:

首先，由于nulls不被允许，我们检查该元素是否为null。如果是这样，我们会抛出一个NullPointerException。

if (e == null) {
    throw new NullPointerException("Queue doesn't allow nulls");
}

Next, we check if the queue is full, and if so, we’ll remove the eldest element from the queue:

接下来，我们检查队列是否已满，如果是，我们将从队列中删除最长的元素。

while (count >= items.length) {
    this.poll();
}

Finally, we insert the element into the tail of the queue and update the queue number of elements:

最后，我们将该元素插入队列的尾部，并更新队列的元素数量。

this.items[count] = e;
count++;

4.2. poll() Method Implementation

4.2.poll()方法实现

The poll() method will return the head element of the queue and remove it from the queue. In case the queue is empty, the poll() method will return null:

poll()方法将返回队列的头部元素并将其从队列中移除。如果队列是空的，poll()方法将返回null。

@Override
public E poll() {
    if (count <= 0) {
        return null;
    }
    E item = (E) items[0];
    shiftLeft();
    count--;
    return item;
}

Firstly, we check if the queue is empty and return null if it is:

首先，我们检查队列是否为空，如果是，则返回null。

if (count <= 0) {
    return null;
}

If not, we store the head of the queue in a local variable that will be returned at the end and move all the elements of the queue one step towards the head of the queue calling the shiftLeft() method:

如果不是，我们将队列的头部存储在一个局部变量中，该变量将在最后返回，并将队列的所有元素向队列的头部移动一步，调用shiftLeft()方法。

E item = (E) items[0];
shiftLeft();

Finally, we update the queue number of elements and return the head of the queue.

最后，我们更新队列的元素数，并返回队列的头部。

Before moving forward, let’s check the method shiftLeft(). This method starts from the second element in the queue and goes till the end, moving each element one place towards the head of the queue:

在前进之前，让我们检查一下shiftLeft()方法。这个方法从队列中的第二个元素开始，一直到最后，将每个元素向队列的头部移动一个位置。

private void shiftLeft() {
    int i = 1;
    while (i < items.length) {
        if (items[i] == null) {
            break;
        }
        items[i - 1] = items[i];
        i++;
    }
}

4.3. Peek Method Implementation

4.3.Peek方法实现

The peek() method works as the poll() method but doesn’t remove the element from the queue:

peek()方法与poll()方法一样工作，但不会从队列中删除元素。

public E peek() {
    if (count <= 0) {
        return null;
    }
    return (E) items[0];
}

5. Conclusion

5.总结

In this article, we’ve covered the basics of the Java Collections Framework queues. We’ve seen the fixed-size queues that the framework has to offer and learned how to create our own.

在这篇文章中，我们已经介绍了Java集合框架队列的基础知识。我们看到了该框架提供的固定大小的队列，并学习了如何创建我们自己的队列。

As always, the code is available over on GitHub.

一如既往，代码可在GitHub上获得。