Fixed Size Queue Implementations in Java

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.

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.

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.

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.

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.

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.

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) {
        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.

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

4.1. offer() Method Implementation

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.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:

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

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:

@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:

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];
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:

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

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.