FIFO array/queue

Question

I'm new to programming and was tasked with programming a generic circular FIFO queue, without using anything but an underlying array and self-programmed methods. I still don't know how to approach bigger projects like this yet. I managed to program something that technically works, but I need someone brutal to really tear this apart and let me know how I can improve. I try to practice when I can, but I still miss so many obvious things and get stuck constantly. I already submitted this work, but you can refrain from explicit answers anyway. Any tips at all are very much appreciated.

The array needs to be able to double or be halved as needed for more memory or to take up less memory. Then it needs to be able to print everything out.

public class FloatingQueue<T>
{
 private T[] theArray;
 private static final int initialCap = 10;
 private int capacity = initialCap;
 private int theHead = 0;
 private int theTail = -1;
 private int size;
 FloatingQueue() {
 theArray = (T[]) new Object[ initialCap ];
 }
 //adds object to the end of the queue and returns true if array is now changed successfully
 public boolean offer ( T newData ) {
 boolean hasChanged = false;
 String changeCheck = this.toString();
 size++;
 theTail++;
 if ( size > capacity ) {
 this.doubleUp();
 hasChanged = true;
 }
 if ( size > 1 & theTail == theHead | theArray[0] == null ) {
 theTail = returnNullIndex();
 }
 theArray[theTail] = newData;
 if ( this.toString() != changeCheck ) {
 hasChanged = true;
 }
 return hasChanged;
 }
 //removes and returns first object in the queue
 public T poll() {
 if ( size == 0 ) {
 return null;
 }
 T temp = theArray[theHead];
 theArray[theHead] = null;
 size--;
 if ( this.size() > 0 )
 theHead++;
 if ( size != 0 & theArray[theHead] == null ) {
 theHead = returnNonNullIndex();
 if ( returnNullIndex() > 0 & returnNullIndex() < theTail ) {
 theHead = 0;
 }
 if ( size < capacity / 4 && capacity != 10 ) {
 this.downSize();
 }
 }
 return temp;
 }
 //returns the first object and does not remove it
 public T peek() {
 T temp;
 if ( isEmpty() == false ) {
 temp = theArray[theHead];
 return temp;
 }
 return null;
 }
 //Return number of objects in queue
 public int size() {
 return size;
 }
 //returns true if queue is empty
 public boolean isEmpty() {
 boolean noElements = false;
 if ( size() == 0 )
 noElements = true;
 return noElements;
 }
 //empties the queue
 public void clear() {
 for ( int i = 0; i < theArray.length; i++ ) {
 if ( theArray == null )
 break;
 theArray[i] = null;
 }
 size = 0;
 theHead = 0;
 theTail = -1;
 }
 //should hopefully print out the strings in order
 public String toString() {
 String allElements = "[";
 if ( size > 0 )
 allElements += theArray[theHead].toString() + ",";
 for ( int i = 0; i < capacity; i++ ) {
 if ( theArray[i] != null && theArray[i] != theArray[theHead] && theArray[i] != theArray[theTail] ) {
 allElements += theArray[i].toString() + ",";
 }
 } 
 if ( size > 1 )
 allElements += theArray[theTail] + ",";
 allElements = (size() == 0) ? allElements : allElements.substring(0, allElements.length()-1);
 allElements += "]";
 return allElements;
 }
 //doubles array size and copies into bigger array
 private void doubleUp ( ) {
 capacity *= 2;
 T[] biggerArray = (T[]) new Object[ capacity ];
 for (int i = 0; i < theArray.length; i++) {
 biggerArray[i] = theArray[i];
 }
 theArray = biggerArray;
 }
 //halves underlying array and copies over
 private void downSize ( ) {
 capacity /= 2;
 int smallArrayIndex = 0;
 T[] smallerArray = (T[]) new Object[ capacity ];
 for ( int i = theHead; i <= theTail; i++ ) {
 smallerArray[smallArrayIndex] = theArray[i];
 smallArrayIndex++;
 }
 theHead = 0;
 theTail = size - 1;
 theArray = smallerArray;
 }
 //finds first null index
 private int returnNullIndex () {
 for (int i = 0; i < theArray.length-1; i++) {
 if ( theArray[i] == null ) {
 return i;
 }
 }
 return -1;
 }
 //finds non null index
 private int returnNonNullIndex () {
 for (int i = 0; i < theArray.length-1; i++) {
 if ( theArray[i] != null ) {
 return i;
 }
 }
 return -1;
 }

Answer 1

Advice 1

In Java Collection Framework (the data structure framework residing in java.util.*), the item type is denoted by E, and not T. I suggest you do this:

public class FloatingQueue<E> {
 ... E here and there.
}

Advice 2

FloatingQueue() {
 ....
}

You are clearly missing the public keyword here; without it, only the code in the same package can construct your queue. Declare like this

public FloatingQueue() {
 ....
}

Advice 3

FloatingQueue is a strange name for your class. What is Floating? Consider ArrayFIFOQueue instead to denote that it's a FIFO queue implemented via arrays (and not linked lists).

Advice 4

theArray = (T[]) new Object[ initialCap ];

According to common Java programming conventions, there should not be spaces within the square brackets []. Instead, write like this:

theArray = (T[]) new Object[initialCap];

Advice 5

Also, private static constants should be named using uppercase SNAKE_CASE:

private static final int INITIAL_CAPACITY = 10;

Advice 6

Write always if ( condition ) { as if (condition) {.

Advice 7

private int theHead = 0;
private int theTail = -1;

Consider the following instead:

private int headIndex = 0;
private int tailIndex = 0;

Advice 8

The offer method is overkilling it in my opinion. Consider this:

public void offer(E item) {
 if (shouldExtendArray()) {
 extendArray();
 }
 
 array[tailIndex++] = item;
 size++;
 
 if (tailIndex == array.length) {
 tailIndex = 0;
 }
}

Advice 9

Your poll method requires some comment explanation on what is being done their. Looks like you degrade it to linear time (instead of possible constant time) using the returnNullIndex and returnNonNullIndex.

Advice 10

if ( size != 0 & theArray[theHead] == null ) {

While & is not a bit operand in this context, it differs from conventional && in that it does not short-circuit. For example getFalse() & getTrue() will evaluate both the calls even if the first getFalse() returns false. You don't need this. Use && and || instead of & and |, respectively.

Summa summarum

All in all, I thought about the following rewrite:

public class ArrayFIFOQueue<E> {
 private static final int INITIAL_CAPACITY = 10;
 private E[] array;
 private int headIndex;
 private int tailIndex;
 private int size;
 public ArrayFIFOQueue() {
 this.array = (E[]) new Object[INITIAL_CAPACITY];
 }
 public void offer(E item) {
 if (shouldExtendArray()) {
 extendArray();
 }
 array[tailIndex++] = item;
 size++;
 if (tailIndex == array.length) {
 tailIndex = 0;
 }
 }
 public E peek() {
 return size == 0 ? null : array[headIndex];
 }
 public int size() {
 return size;
 }
 public boolean isEmpty() {
 return size == 0;
 }
 public void clear() {
 // Help garbage collector:
 for (int i = 0; i < size; i++) {
 int index = (headIndex + i) % array.length;
 array[index] = null;
 }
 size = 0;
 }
 public E poll() {
 if (size == 0) {
 return null;
 }
 E returnValue = array[headIndex];
 array[headIndex++] = null;
 if (headIndex == array.length) {
 headIndex = 0;
 }
 size--;
 if (shouldContract()) {
 contractArray();
 }
 return returnValue;
 }
 private boolean shouldExtendArray() {
 return size == array.length;
 }
 private boolean shouldContract() {
 return size * 4 <= array.length && array.length >= 4 * INITIAL_CAPACITY;
 }
 private void extendArray() {
 assert size == array.length;
 E[] newArray = (E[]) new Object[2 * array.length];
 for (int i = 0; i < array.length; i++) {
 newArray[i] = array[(headIndex + i) % array.length];
 }
 this.array = newArray;
 this.headIndex = 0;
 this.tailIndex = size;
 }
 private void contractArray() {
 assert size <= array.length / 4;
 E[] newArray = (E[]) new Object[array.length / 4];
 for (int i = 0; i < size; i++) {
 newArray[i] = array[(headIndex + i) % array.length];
 }
 this.array = newArray;
 this.headIndex = 0;
 this.tailIndex = size;
 }
}

• Rishabh Deep Singh: Advice-6 might be redundant might be using some sort of formatter

Answer 2

Here are a couple details from a quick glance at the code:

• If you are implemented a queue, consider actually implementing the Java Queue interface: FloatingQueue implements Queue

• Check you usage of booleans:

if (isEmpty() == false) {
 ...
}

Is written in a more readable way as:

if (!isEmpty()) {
 ...
}

Also, your isEmpty method is simply returning whether the size is zero. Then just do that, and remove the unneeded intermediate variable:

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

• In your offer method, I'm not completely sure under which circumstances you would need to compare the queue to itself to check whether it has changed. If you added a new element to it, it definitely has changed. If what you want is to check the added element is not null, do that explicitly at the beginning of the method.

public boolean offer ( T newData ) {
 // This already makes your offer method a O(N) time complexity in best case scenario
 String changeCheck = this.toString();
 ...
 if (this.toString() != changeCheck) {
 ...
 }

Answer 3

When having no clue on how to resolve such a problem it often helps to go through a couple of examples or use cases. Re-using those later as test cases helps to ensure everything works as intended.

Try to keep the cases as small as possible but just big enough. When choosing them consider the corner cases of how things operate.

E.g. let's take a capacity of 3

• What if theTail is at the end of the array and your "offer"?
• What if theTail is at the middle (,start, end) of the array on expanding the size?
• What if theHead is at the end (,start, middle) of the array on shrinking the size?

Observations on coderodde's solution.

• Polled data gets cleared to remove no longer needed data, this is not needed to have its solution correctly function. However as long as the array has the references to the data, the data cannot be garbage collected.
• It ensures that the theHead and theTail stay within the array.
• Some implementations have a reserve(int) function very similar to extendArray that allows to make the FIFO a certain size if such a size is expected to be useful (e.g. you know you will store lots of data).

Observations on your solution:

• There is hysteresis between extending and reducing the array. (Offer followed by poll will not extend and reduce immediately after each other.)

General:

• A stack is very common FIFO, where the offer operation is called push and the poll is called pop.
• Somehow I'm tempted to swap head and tail or would call them "read" and "write" pointer.
• It's possible to not track size but derive it from Head and Tail. (for indexing use them % size, store them with % (2*size), and Size=Tail-Head, except if Head>Tail in which case a small correction is needed.
• Lots of hardware prefers values with are \2ドル^n\$ (e.g. 8 or 16) for the capacity because it simplifies calculations in binary numbers.

• Mario Carneiro: "There is hysteresis between extending and reducing the array. (Offer followed by poll will not extend and reduce immediately after each other.)" Note that this kind of hysteresis is required for resizable array data structures to achieve amortized constant time operation. If you use the same cutoff for growing and shrinking, you can get very bad performance if you wobble around the cutoff.
• Mark Bluemel: "A stack is very common FIFO, where the offer operation is called push and the poll is called pop." - this is simply misinformation. A stack is LIFO (Last In First Out) which is a very different thing.