Circular Queue

A CircularQueue implements the PureQueue interface minimizing the burden on the garbage collector while providing \( O(1) \) time implementations for all methods.

`Queue` Review

The PureQueue interface provides the following methods

boolean offer(E element) — adds element to the back of the queue. Returns true if successful.
E poll() — removes and returns the element at the front of the queue.
E peek() — returns the element at the front of the queue without removing it.
int size() — returns the number of elements in the queue.
boolean isEmpty() — returns true if and only if there are no elements in the queue.

Both poll() and peek() throw a NoSuchElementException if called on an empty queue.

The PureQueue interface can be implemented by adapting a List. Here offer() would add to the back of the list; poll() and peek() operate on the first element in the list; and size() and isEmpty() are identical to the list's operations.

Using an ArrayList to implement the PureQueue is not efficient because poll() requires removing the element from the front of the list, which is a \( O(n) \) operation.

Using a LinkedList to implement the PureQueue is better since all methods can be implemented in \( O(1) \) time.

Why Queues?

Queues are a critical component in software. Whenever data is moved from one component to another, it is often useful to make use of a queue to:

Ensure data is not lost
Improve performance

Ensure data is not lost

When sending data from one component to another, the receiving component must be ready to accept the data being sent. If it is not ready, the data may be lost. For example, if you type a key on your keyboard and the operating system is not able to accept it, that keypress will be lost. A queue can be used by the operating system to collect the keypresses when they are pressed and then process them when the operating system is ready to deal with them.

Improve performance

Often we may find that transferring one piece of data is nearly as expensive as transferring a larger chunk of data. For example, each read request to read from a file requires significant overhead associated with our program communicating with the operating system which then needs to communicate with the file system and return the information. Reading multiple bytes from a file requires hardly any additional overhead versus reading one byte. The java.io.BufferedInputStream reads large chunks of bytes and stores them in an internal queue. The input stream can then be used without needing to bug the file system while the queue is emptied. Once emptied, the BufferInputSteam makes a call to the file system to fill up the queue. Similarly, a java.io.BufferedOutputStream wraps an OutputStream. Whenever a write request is made, the data is placed in the queue and only written to the file system when the queue has been filled (or the output stream is closed).

Overview of CircularQueues

An implementation with all constant time methods sounds pretty good; however, every call to offer() results in a new Node object being created and every call to poll() results in a Node object being orphaned. That is, a call to poll() sets head to point to the second node in the list, and the first node no longer has any references to it. As a result, the garbage collector now needs to free up the memory used by the node.

Allocating and deallocating space for every key pressed or every byte read from or written to a file introduces unnecessary overhead. The CircularQueue provides an implementation that avoids Node objects altogether. The tradeoff we make is that our queue will have a fixed capacity.¹

Core Idea for the CircularQueue

By fixing the capacity of our queue, we can allocate an array with a length equal to the capacity. That array will store all the items in our queue. Since we will never have more than capacity items in the queue, the array will always have enough space to store them.

Each time an item is removed from the queue, every remaining item in the queue must advance one position closer to the front of the queue. When implementing the queue with an adaptor class that used a LinkedList, the front of the queue was at index 0 and the back of the queue was at index size() - 1. We could efficiently advance each item in the queue one closer to the front but updating the head reference to point to the next item in the queue. It was now in the first position, making its neighbor now the second item, whose neighbor is now the third item, etc...

We rejected using an ArrayList because each call to poll() required shifting all remaining elements in the queue so that the front of the queue remained at index 0.

With a CircularQueue we don't move items in the array. Once an item is placed into the queue, its position in the array doesn't change; however, we still need to adjust its location in the queue.

First let's consider what happens when we add items to our empty circular queue. The first item will be placed in position 0. The second item is placed in position 1. Each time we add an element, the position of the back of the queue increased by one until the array is filled.

We can do something similar with the front of the queue. If we remove the first item in the queue, the item at position 1 is now at the front of the queue. Instead of shifting all the items in the queue one position to the left, we simply update the location of the front of the queue.

To do this, we will need to keep track of two integers, front and back, which indicate the position of the front and back of the queue. Both variables should start at zero. back is incremented each time offer() is called, and front is incremented each time poll() is called.

Make a queue with a capacity of four. Add four items to it and then remove each item from the queue. What are the values for front and back?

Circularizing the array

Notice that once front moves from 0 to 1, we no longer are using position 0 to store anything in the queue. As a result, once back gets to the end of the array, it can move to 0, then 1, etc... This works as long as back doesn't get larger than front. If it does, that means that we have overwritten data that was stored in our queue.

What instance variables will we need to implement our CircularQueue?

Implementation

Our CircularQueue maintains the following instance variables:

public class CircularQueue<E> implements PureQueue<E> {
    public final static int DEFAULT_SIZE = 1024;
    private Object[] data;
    private int front;
    private int back;
    private boolean isFull;

    public CircularQueue() {
        this(DEFAULT_SIZE);
    }

    public CircularQueue(int capacity) {
        data = new Object[capacity];
        front = 0;
        back = 0;
        isFull = false;
    }

This is not a strict requirement. We could increase the capacity, if needed, by creating a larger array whenever the size exceeds the capacity, but this is typically not done.