# Queue over resizable array implementation

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;

public Queue() {
data = new Integer[2];
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;
}
});
}

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

### 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;
}


### 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];
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;
}

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];
if (head == tail) {
head = tail = 0;
}
if (size() == data.length / SHRINK_TRIGGER_RATIO) {
resize(data.length / RESIZE_FACTOR);
}
return item;
}
}

• Thanks a lot for broad answer. but one mention: ability to resize make this structure effective... or I didn't understand lecture:) – kharandziuk Jul 5 '14 at 18:27
• Or maybe you didn't understand my answer ;-) I'm not against resizing (yes you need to resize), I'm against the realign method. See my alternative implementation at the end. It resizes (of course), but no more realigning. – janos Jul 5 '14 at 18:34
• Oh, cool! Your solution is really nice. – kharandziuk Jul 5 '14 at 18:43
• But, I think you should moved code to top of code. Because it really hard to get from philosophy to real code;-) It looks strange in situation when code is really cool. – kharandziuk Jul 5 '14 at 18:48

## 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;

Queue queue = new Queue();

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.