The paper

An ArrayQueue is a circular Queue that inherits the AbstractList abstract class and is implemented internally as an array.

The source code

package com.sun.jmx.remote.internal;

import java.util.AbstractList;
import java.util.Iterator;

public class ArrayQueue<T> extends AbstractList<T> {
    
    // Initializer must pass in the length
    public ArrayQueue(int capacity) {
        this.capacity = capacity + 1;
        this.queue = newArray(capacity + 1);
        this.head = 0;
        this.tail = 0;
    }

    // Expand the queue
    public void resize(int newcapacity) {
        int size = size();
        if (newcapacity < size)
            throw new IndexOutOfBoundsException("Resizing would lose data");
        newcapacity++;
        if (newcapacity == this.capacity)
            return;
        T[] newqueue = newArray(newcapacity);
        // Copy the data from the original queue to the new queue
        for (int i = 0; i < size; i++)
            newqueue[i] = get(i); // Rewrite the get() method to get data from the head of the queue;
        this.capacity = newcapacity;
        this.queue = newqueue;
        this.head = 0; // Move the queue head back to the first position;
        this.tail = size;  // Set the tail pointer to the position next to the last element in the current queue;
    }

    @SuppressWarnings("unchecked")
    private T[] newArray(int size) {
        return (T[]) new Object[size];
    }

    // Add to the end of the queue
    public boolean add(T o) {
        queue[tail] = o;
        int newtail = (tail + 1) % capacity; // execute the subscript loop by dividing the remainder;
        if (newtail == head)
            throw new IndexOutOfBoundsException("Queue full");
        tail = newtail;
        return true; // we did add something
    }

    // Remove the first element
    public T remove(int i) {
        if(i ! =0)
            throw new IllegalArgumentException("Can only remove head of queue");
        if (head == tail)
            throw new IndexOutOfBoundsException("Queue empty");
        T removed = queue[head];
        queue[head] = null;
        head = (head + 1) % capacity; // execute the subscript loop by dividing the remainder;
        return removed;
    }

    // Overrides the get() method on List to get elements in queue order
    public T get(int i) {
        int size = size();
        if (i < 0 || i >= size) {
            final String msg = "Index " + i + ", queue size " + size;
            throw new IndexOutOfBoundsException(msg);
        }
        int index = (head + i) % capacity;
        return queue[index];
    }

    public int size(a) {
        // Can't use % here because it's not mod: -3 % 2 is -1, not +1.
        int diff = tail - head;
        if (diff < 0)
            diff += capacity;
        return diff;
    }

    private int capacity; // The size of the current queue, immutable
    private T[] queue; // Queue array
    private int head; // The position of the first element in the queue
    private int tail; // The position of the last element in the queue
}

Copy the code

Let’s tidy it up,

resize(): Expand the queue (copy data from the old queue to the new queue).

add(): Adds data to the end of the column.

remove(): Deletes the queue head element.



If you look at the code like this, maybe some of you will not understand how the pointer operates inside, let’s look at a picture.



Let’s say I have a length 8ArrayQueue, filled with data (7), marked 0-7.

Delete data, head will point to1,0Position data is set to NULL (queue is first in, first out).

When you insert data, tail points to0 newtail = (tail + 1) % capacity



In other words, the entire ArrayQueue is circular. Deleting elements always sets the memory address pointed by head to null, and adding elements always inserts the memory address pointed by tail. The entire storage structure is a continuous memory segment, but it is like a circle.