DoublingQueue in Java Inspired by this CR question, I decided to create my own queue! If you guys see anything taboo or have any improvements, please let me know. Ultimately I want it to be feature rich and bug free, with every possible case tested, so if there's anything else that can be added (like an iterator) and thoroughly tested, please mention it.

IDoublingQueue.java

public interface IDoublingQueue&lt;E&gt; {
    public boolean isEmpty();
    public int size();

    public void enqueue(E item);
    public E dequeue();
}


DoublingQueue.java

public class DoublingQueue&lt;E&gt; implements IDoublingQueue&lt;E&gt; {

    private E[] queue;
    private int size = 0;
    private int first = 0;

    public DoublingQueue() {
        queue = (E[]) new Object[2];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }

    private void resize(int max) {
        assert max &gt;= size;

        E[] temp = (E[]) new Object[max];

        for (int i = 0; i &lt; size; ++i) {
            temp[i] = queue[(first + i) % queue.length];
        }

        queue = temp;
        first = 0;
    }

    @Override
    public void enqueue(E item) {
        // be sure no null items make it into the queue
        if (item == null) {
            throw new IllegalArgumentException("ERROR: Null elements cannot be inserted!");
        }

        if (size == queue.length) {
            resize(2 * queue.length);
        }

        queue[size++] = item;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("ERROR: Queue underflow");
        }

        E item = queue[first];

        queue[first] = null;
        size--;
        first++;

        if (first == queue.length) {
            first = 0;
        }

        // shrink the queue if necessary
        if (size &gt; 0 &amp;&amp; size == queue.length / 4) {
            resize(queue.length / 2);
        }

        return item;
    }
}


Tests

public class DoublingQueueTest {

    private final DoublingQueue&lt;Integer&gt; queue = new DoublingQueue();

    @Test(expected = IllegalArgumentException.class)
    public void enqueueNullTest() {
        queue.enqueue(null);
    }

    @Test(expected = RuntimeException.class)
    public void dequeueEmptyTest() {
        queue.dequeue();
    }

    @Test
    public void enqueueTest() {
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        assertTrue(queue.size() == 3);
    }

    @Test
    public void dequeueTest() {
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        int num = queue.dequeue();

        assertTrue(num == 1);
    }
}
Edit:
As coderodde excellently pointed out in his answer, your implementation has the issue of not reusing previous entries in the array that have already been dequeued. This means that your array will always keep on growing in size. See his answer for an explanation on this.



First of all, good job on improving your coding skills through an exercise like this. More people should be doing this. Now lets get into the criticism from which you will hopefully learn even more.

Constructor

It's strange that you do not allow the user to specificy the initial size of the queue. Even if this were to be a design choice, I think 2 is too low of a value. Also the magic number 2 should be moved to a constant like DEFAULT_QUEUE_SIZE to increase readability and maintainability.

Size

Your size variable is quite confusing. For a while I thought it was the current size of the queue, meaning it would start at 2 and then double over time. But later I found out that it actually represents the amount of items currently in the queue. I think that this might also be confusing to anyone calling your size() method.

isFull()

In your enqueue() method you check size == queue.length. This is essentially the isFull() method. Replacing this with a call to isFull() would not only increase the readability of your enqueue() method, but also add the isFull()method to the public API of your class, fulfilling the symmetry with isEmpty().

resize()

To improve coherence and readability, I would add two methods called doubleSize()and halfSize(), which would simply then call the resize() method with the correct parameters. This improves the readability and intentions in the enqueue() and dequeue() method and allows the explanatory comment // shrink the queue if necessary to be removed.

Comments

There are a lot of opinions about comments. I share mine with Robert C. Martin in that they show a failure of expressing yourself by means of code. The comment I mentioned in the section above about the resize() method is a good example of that.

The other comment in your code, // be sure no null items make it into the queue, can also be removed, because the code below it is perfectly clear. It is simply a duplication of information, and just as duplication of code is bad, this kind of duplication is bad as well. This is because comments tend to get out of sync with the code they were intended to enlighten.

Interface

Personally, I do not see the use of an interface for this implementation. I think it is merely clutter as it provides no additional information that the concrete class itself does not already provide.



Testing

There is a lot that could be improved in the testing department here. I will try to create a somewhat short, comprehensive list of the things that I think are missing or incorrect. You will find that most of the things I say about testing have also been said in the Code Review question that inspired you, so perhaps you should also read through the accepted answer there on testing.


Your enqueueTest function is testing size() functionality.
Your test function names are not very descriptive about the situation that is being tested and what the expected outcome should be. There is a small blogpost by Google on test function names that might be useful to read.


Test ALL the things.

You are not even scratching the surface of having all scenarios tested.


Are you sure that dequeue() actually halves the queue size when it can? You shouldn't be, because you haven't tested it.
isEmpty() is not even tested once. What happens when isEmpty() is called when the queue is empty, filled or full? Or full and then emptied again. All of these scenarios should be tested.
Your test for the size() method is way too simplistic. Does size() return 0 if the queue is empty? does it return the correct amount after enqueueing X items and dequeueing Y items? Does it return the correct amount after doubling and halving the queue X amount of times?
You should also test the FIFO (First In First Out) concept of your queue more elaborately. You started with it in dequeueTest(), but kept it way too simple.


Test examples

In this section I will provide some example tests for only the method isEmpty() to illustrate my points above.

@Test
public void testIsEmptyReturnsTrueWhenQueueIsEmpty() {
    assertTrue(queue.isEmpty());
}

@Test
public void testIsEmptyReturnsFalseWhenQueueIsFilled() {
    queue.enqueue(1);
    assertFalse(queue.isEmpty());
}

@Test
public void testIsEmptyReturnsFalseWhenQueueIsFull() {
    // Since your magic starting queue size number
    // is 2 I enqueue two items.
    queue.enqueue(1);
    queue.enqueue(2);

    assertFalse(queue.isEmpty());
}

@Test
public void testIsEmptyReturnsTrueWhenQueueIsEmptiedAfterUse() {
    for (int i = 0; i &lt; 10; i++) queue.enqueue(i);
    for (int i = 0; i &lt; 10; i++) queue.dequeue();

    assertTrue(queue.isEmpty());

    // This second part is debatable since you generally want
    // to test only one thing per test.
    for (int i = 0; i &lt; 10; i++) {
        queue.enqueue(i);
        queue.dequeue();
    }

    assertTrue(queue.isEmpty());
}