Fixed-size array-based implementation of a queue

Question

For my computer science class, I've implemented a Java version of a queue and would like to know if there's anything wrong with it. After my tests, it seems to work fine, but maybe somebody can point out what can be improved or if something is wrong.

public class Queue<E> implements IQueue<E> {
private E[] internalQueue;
private int currIndex;
public Queue(int size) {
 internalQueue = (E[]) new Object[size];
 currIndex = 0;
}
@Override
public void push(E input) {
 internalQueue[currIndex] = input;
 currIndex++;
}
public E[] getQueueDebug() {
 return this.internalQueue;
}
@Override
public E pop() {
 if (currIndex != 0) {
 E toReturn = internalQueue[0];
 for (int i = 1; i <= internalQueue.length - 1; i++) {
 internalQueue[i - 1] = internalQueue[i];
 internalQueue[i] = null;
 }
 currIndex--;
 return toReturn;
 }
 return null;
}
@Override
public E top() {
 if (currIndex != 0)
 return internalQueue[0];
 return null;
}
@Override
public boolean empty() {
 return (currIndex == 0);
}
}

Answer 1

API

The method names you chose are unusual for queues. It's good to get inspiration from the JDK. Following the example of Queue, I suggest these renames:

• push -> add
• pop -> poll
• top -> peek
• empty -> isEmpty

Protecting internal implementation details

The getQueueDebug should ideally not be there at all, and definitely not with public visibility. It's best to test classes through their public interfaces. Avoid exposing internal details.

Readability

The currIndex != 0 condition is used at multiple places. This meaning of this condition is "not empty", and the code would be more readable if you replaced it with a !isEmpty() method call.

Copying arrays

Instead of manually copying contents of an array like this:

for (int i = 1; i <= internalQueue.length - 1; i++) {
 internalQueue[i - 1] = internalQueue[i];
 internalQueue[i] = null;
}

It's more efficient to use System.arraycopy:

System.arraycopy(internalQueue, 1, internalQueue, 0, internalQueue.length - 1);

Performance

Moving the elements of internalQueue on every poll is inefficient. You could instead use two indexes to point to the first and last element in the queue, and only move elements when really necessary.

In fact, @TedHopp put it beautifully in a comment:

[...] By thinking of the array as circular (and using two indexes as suggested) it's never necessary to move elements. All it takes is some close attention to indexing to distinguish between an empty and a full queue.

Java conventions

Note that it's not a convention in Java to prefix interface names with a capital I, as you could see already in the Queue interface of the JDK.

You could use Queue as your interface name, and since the implementation is effectively an array-backed bounded queue, you could name the implementation class ArrayBackedBoundedQueue, for example.

• Ted Hopp: Nice analysis. I'd just like to add that by thinking of the array as circular (and using two indexes as suggested) it's never necessary to move elements. All it takes is some close attention to indexing to distinguish between an empty and a full queue.
• janos: Thanks @TedHopp, very well said, I added that to my answer.

Answer 2

You should never shift array contents unless explicitly requested.

In your case, do not shift array in pop method (should be actually named poll, as @janos says), just shift head of the queue, same way as you shift its tail currIndex. Obviously, with this strategy both head and tail will only increase, so they should be wrapped to zero when reaching your queue size.

Something like this (repeated parts omitted)

private int head = 0;
public void push(E input) {
 internalQueue[currIndex] = input;
 currIndex = ++currIndex % internalQueue.length;
}
public E pop() {
 if (currIndex != head) {
 E toReturn = internalQueue[head];
 head = ++head % internalQueue.length;
 return toReturn;
 }
 return null;
}

• Oliver: This implementation doesn't provide ways to say if the queue is completely empty or completely full when both indexes are same (just read Ted Hopp's comment)

Answer 3

Your queue does not have any overflow protection. As queues tend to be used in multi-threaded environments with different producer and consumer threads, you'll have an immediate overflow when the consumer stalls for a while. In fact, this will simply throw an ArrayIndexOutOfBoundsException right now, so you'll have a program crash (which is somewhat OK.) If you expand this by creating a ring-buffer on a fixed array, you'll overwrite unread data without even noticing it and find yourself in the hell of untracable program behaviour.

Thus: add bounds checks.