FIFO Queue Implementation

Question

My Implementation of a FIFO queue. I am mainly curious about my initialization of empty generic arrays.

public class Queue<T> {
 T queue[];
 public Queue()
 {
 queue = (T[])new Object[0];
 }
 public T pop()
 {
 T queue2[] = (T[])new Object[queue.length-1];
 T obj = queue[0];
 for(int i = 0; i < queue.length-1; i++)
 queue2[i] = queue[i+1];
 queue = queue2;
 return obj;
 }
 public void push(T node)
 {
 T queue2[] = (T[])new Object[queue.length+1]; 
 for(int i = 0; i < queue.length; i++)
 {
 queue2[i] = queue[i];
 }
 queue2[queue.length] = node;
 queue = queue2;
 }
 public T peek()
 {
 return queue[0];
 } 
 public int size()
 {
 return queue.length;
 }
}

• OhadR: you know, you can you LinkedList....
• OhadR: or ConcurrentLinkedQueue

Answer 1

Trying to use a generic array in Java, is a disaster waiting to happen. The T[] field is really an Object[] at runtime, and trying to do otherwise just hides this fact. It makes you think you're dealing with a T[], but it's a lie; you're really dealing with an Object[]. There are very good reasons not to use generic arrays. I'll add that if you peek into the current Oracle implementation of ArrayList or CopyOnWriteArrayList, you won't see a generic array being used, but Object[] explicitly. It makes it clear to the developers and to the readers that the array being handled does not have a generic type.

In your particular case, there are no unsafe operations done with it, so that's good. But be careful if you add a toArray() method in the future... Just take a look to see how easy it is to make a mistake: add the method

public T[] toArray() {
 return queue; // or queue.clone();
}

Looks fine. Even compiles without warnings. Now do:

Queue<String> queue = new Queue<>();
queue.push("foo");
String[] array = queue.toArray();

Looks also fine. Still no warnings. But this will fail at run-time:

Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.String;

Runtime is the worst moment to have those exceptions. It is always better to detect bugs as early as possible, and fail directly at compile-time. And this exception, is because the array really isn't a String[], but an Object[]. There are ways around that of course (the simpler being to return Object[] from the method), but the point is that you're opening yourself to a lot of unforeseen troubles. All in all, if you really want a backing array, don't lie to yourself and:

• Just use Object[]. You'll have to cast when poping or pushing elements, but you can ensure that it is safe to do by having the proper generic type for the methods, just like you have in the current code.
• If you want strong typing, pass the class of the elements as constructor to the Queue.

Couple of side-notes:

• It would be preferable to throw an NoSuchElementException if the queue is empty inside peek, instead of failing with an out of bounds exception.
• To copy arrays, you can use System.arraycopy, like mentioned in this other answer.

• jacksonecac: Wow It never occurred to me to use Object instead of T. That is brilliant. Thank you!

Answer 2

The most efficient way to copy arrays as you want is using: System.arraycopy(). So, I would suggest you to replace your loops with System.arraycopy calls.

In the pop() method instead of copying one by one like this:

for(int i = 0; i < queue.length-1; i++)
 queue2[i] = queue[i+1];

System.arraycopy can be used as:

System.arraycopy(queue, 1, queue2, 0, queue.length-1);

And in the push() method, instead of copying one by one like this:

for(int i = 0; i < queue.length; i++)
{
 queue2[i] = queue[i];
}

You could use:

System.arraycopy(queue, 0, queue2, 0, queue.length);

See also reference.

• OhadR: did he ask about copying?
• sanastasiadis: @OhadR I thought that my answer made an "insightful observation" as mentioned in What goes into an answer