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

最后修改: 2022年 9月 16日

1. Overview


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.


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


2. Java Collections Framework Queues


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


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.


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


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.


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


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.


Finally, the inspection methods defined in the Queue interface:


E element();
E peek();

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


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

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


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 队列并实现了 QueueCollection 接口中的大多数方法。

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:


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

    public FifoFixedSizeQueue(int capacity) {

        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.


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:


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

First, as nulls aren’t allowed, we check if the element is null. If this is the case, we throw a 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) {

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


this.items[count] = e;

4.2. poll() Method Implementation


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:


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

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


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:


E item = (E) items[0];

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:


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

4.3. Peek Method Implementation


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


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

5. Conclusion


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.


As always, the code is available over on GitHub.