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