Queue over resizable array implementation

Question

I study data structures on coursera's course, and there is an extra exercise to create a Queue data structure.

I created it:

class Queue {

  Integer[] data;
  int head, tail;

  public Queue() {
    data = new Integer[2];
    head = 0;
    tail = 0;
  }

  public int size() {
    return tail - head;
  }

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

  private void realign() {
    java.util.Arrays.sort(data, new java.util.Comparator<Object>() {
      public int compare(Object o1, Object o2) {
        if (o1 == null) return 1;
        else if(o2 == null) return -1;
        else return 0;
      }
    });
    tail -= head;
    head = 0;
  }

  private void resize() {
    if (tail == data.length && size() != data.length) {
      realign();
    }
    if (data.length == size()) {
      int newLength = data.length * 2;
      //Duplication
      Integer[] newData = new Integer[newLength];
      System.arraycopy(data, 0, newData, 0, data.length);
      data = newData;
    } else if (size() == data.length / 4 && size() != 0) {
      int newLength = data.length / 2;
      //Duplication
      Integer[] newData = new Integer[newLength];
      System.arraycopy(data, 0, newData, 0, data.length);
      data = newData;
    }
  }

  public void enqueue(Integer item) {
    if (item == null) { throw new NullPointerException(); }
    resize();
    data[tail] = item;
    tail++;
    return;
  }

  public int dequeue() {
    if (isEmpty()) { throw new java.util.NoSuchElementException(); }
    int res = data[head];
    data[head] = null;
    head++;   
    if (head == tail) {
      head = tail = 0;
    }
    return res;
  }
}

And a test suit for it:

import org.junit.Test;
import static org.junit.Assert.*;
import java.util.*;

public class QueueTest {


  @Test
  public void testQueueN() {
    Queue q = new Queue();
    int N = 65;
    for(int i = 0; i < N; i++) {
      q.enqueue(i);
    }
    assertFalse(q.isEmpty());
    for(int i = 0; i < N; i++) {
      assertEquals(i, q.dequeue());
      assertEquals(N - i -1, q.size());
    }
    assertTrue(q.isEmpty());
  }

  @Test
  public void testEnDeEn() {
    Queue q = new Queue();
    q.enqueue(2);
    assertEquals(1, q.size());
    assertEquals(2, q.dequeue());
    q.enqueue(5);
    assertEquals(5, q.dequeue());
  }

  @Test(expected=java.util.NoSuchElementException.class)
  public void testDeOnEmpty() {
    Queue q = new Queue();
    q.dequeue();
  }
  @Test(expected=NullPointerException.class)
  public void testEnWithNull() {
    Queue q = new Queue();
    q.enqueue(null);
  }
}

Please, review it from perspective of implementation and performance.

Update: I improved(thanks to @Vogel612) this code a little bit. Improved version

Answer 1

Learn from what already exists

There is an interface defined in java.util.Queue. It makes sense to implement it in your solution.

If you don't need some of the methods of the interface, you can just throw new UnsupportedOperationException(); for the time being, and implement them later when you need them.

The interface methods will guide your design in the right direction. For example, you implemented methods to add elements at the end and remove from the head, but you did not implement the converse: add at the head and remove from the end. Looking at the methods required by java.util.Queue, you would have spotted that.

An existing interface like java.util.Queue also helps you use "standard" method naming. You called your methods enqueue and dequeue, when they would have been better as add and poll, respectively, following the "standard".

Generalize

The interface in java.util is defined with a type parameter, as Queue<E>. Indeed your implementation would work just fine with any kind of object, not only integers. You could follow the example and generalize your implementation so it can work with anything.

If you don't know how to go about that, you can get ideas from an existing implementation, for example the PriorityQueue of OpenJDK

Allow null values

Your implementation doesn't allow null values. I suppose it's because that would break your realign method. If you think about it, that realign method is ugly. Suppose you have 1000 elements, if you call dequeue followed by enqueue, your call will move 999 elements one by one, and in a really awkward way with that comparator and sorting.

Hint: realigning could be part of your resizing logic. Now you are resizing the array with:

System.arraycopy(data, 0, newData, 0, data.length);

But you can do better than that, using head and tail:

System.arraycopy(data, head, newData, 0, tail - head);

You could get rid of the ugly realign method and allow nulls by refactoring your code (see my solution at the bottom).

Don't Repeat Yourself

This code appears twice:

Integer[] newData = new Integer[newLength];
System.arraycopy(data, 0, newData, 0, data.length);
data = newData;

This calls for a helper method:

private void resize(int newLength) {
    Integer[] newData = new Integer[newLength];
    System.arraycopy(data, head, newData, 0, tail - head);
    data = newData;
    tail -= head;
    head = 0;
}

Constants

It's good to use constants for clearer logic, and also to avoid duplication. For example:

private static final int INITIAL_CAPACITY = 2;
private static final int SHRINK_TRIGGER_RATIO = 4;
private static final int RESIZE_FACTOR = 2;

// ...

public Queue() {
    data = new Integer[INITIAL_CAPACITY];
    // ...
}

if (tail == data.length) {
    resize(data.length * RESIZE_FACTOR);
}

// ...

if (size() == data.length / SHRINK_TRIGGER_RATIO) {
    resize(data.length / RESIZE_FACTOR);
}

When to resize?

Your implementation is asymmetric: grow or shrink if needed when adding items. I haven't put a lot of thought into this, but it would seem to make sense to make this symmetric: grow if needed when adding items, shrink if needed when removing items.

Unit test case naming

First of all, it's great that you added many unit tests, covering most of your implementation and corner cases. But your test case names are not very good. It's good to make test case names long and descriptive, for example testDequeueOnEmpty instead of testDeOnEmpty, and testEnqueueDequeueEnqueue instead of testEnDeEn.

Although it may seem trivial, I would also add a simple test for emptiness alone:

@Test
public void testIsEmpty() {
    Queue q = new Queue();
    assertTrue(q.isEmpty());
    q.enqueue(4);
    assertFalse(q.isEmpty());
    q.dequeue();
    assertTrue(q.isEmpty());
}

Suggested implementation

Here's an alternative implementation based on yours that supports null values and without the ugly realign method:

public class Queue {
    private static final int INITIAL_CAPACITY = 2;
    private static final int SHRINK_TRIGGER_RATIO = 4;
    private static final int RESIZE_FACTOR = 2;

    private Integer[] data;
    private int head, tail;

    public Queue() {
        data = new Integer[INITIAL_CAPACITY];
        head = 0;
        tail = 0;
    }

    public int size() {
        return tail - head;
    }

    public boolean isEmpty() {
        return tail == head;
    }

    private void resize(int newLength) {
        Integer[] newData = new Integer[newLength];
        System.arraycopy(data, head, newData, 0, tail - head);
        data = newData;
        tail -= head;
        head = 0;
    }

    public void enqueue(Integer item) {
        if (tail == data.length) {
            resize(data.length * RESIZE_FACTOR);
        }
        data[tail] = item;
        tail++;
    }

    public Integer dequeue() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException();
        }
        Integer item = data[head];
        data[head] = null;
        head++;
        if (head == tail) {
            head = tail = 0;
        }
        if (size() == data.length / SHRINK_TRIGGER_RATIO) {
            resize(data.length / RESIZE_FACTOR);
        }
        return item;
    }
}

Answer 2

Imports:

import java.util.*;

NEVER do this. Look how many classes you got now. This is ineffective and needlessly clutters your IDE's "do what I want button"-suggestions.

The fun thing is, in your main class you do it the other way round:

java.util.Arrays.sort(data, new java.util.Comparator<Object>() {

why not:

import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;

//Later:
Arrays.sort(data, new Comparator<Object>()) {

This is shorter, does exactly the same and allows your ClassLoader to preload the classes needed --> possible performance improvements

Queue<E> and Scoping

While we're in the java.util package.. You can find an interface there.. Queue<E>. This is something you can program against. To prevent a name-conflict I'd rename your implementation to MyQueue or something similar.

You class would then begin with the following:

public class MyQueue implements Queue<Integer> {
    private Integer[] data;
    private int head;
    private int tail;

Here I also made some changes to your code.
Why? In short: You should restrict the visibility of members as much as possible. With your code, classes in the same package as your Queue could do:

Queue queue = new Queue(); 
queue.data[0] = Integer.MAX_VALUE;

This is not good. noone should be messing with the state of your class. That's why these members should be private (or maximally protected), but definitely not package-private which is the default scope.

same goes for your head and tail.