Queue with using array in Java-CodePudding

In our midterm exam teacher asked us to do this question below: Write a generic Queue class which uses an array(not a link list) as a memory storage. It should support generic type parameter and array resizing (both growing and shrinking), but it doesn't have to support iterators.Hints:Queue is a FIFO data structure ; the API for a queue contains enqueue, dequeue,size and isEmpty methods in addition to the constructor; you don't have to implement toString.

I tried to write this code and here's what I wrote. But I don't know how should I check this code. Is it correct or how can I check it?

 public class Queue<T> {
 public T[] array;
 public int N;

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

 public int size() {
  return N;
}

public void resize(int max) {
  T[] temp = (T[]) new Object[max];
  for (int i = 0; i < N; i  ) {
     temp[i] = array[i];
   }
   array = temp;
 }

public void enqueue(T item) {
  if (isEmpty()) {
  array[0] = item;
   N  ;
 } else if (N == array.length) {
   resize(array.length * 2);
   array[N] = item;
   N  ;
} else {
  array[N] = item;
  N  ;
 }
}

 public T dequeue() {
  T value = array[0];
  for (int i = 1; i < N; i  ) {
      array[i - 1] = array[i];
  }
     array[--N] = null;
     return value;
 }
}

CodePudding user response：

here is the code with my revisions. I preserved your general approach I just made some fixes.

Of course other optimizations are possible but I'll leave them to you ;)

import java.lang.reflect.Array;

public class Queue<T> {
    //never expose directly as public internal variables of your classes. So they should be private
    private final Class<T> clazz;
    private T[] array;
    private int n;

    //these 2 variables define the expansion and reducing policy so that may be changed dynamically
    private final float policyToExpand = 3.0f/4.0f;
    private final float policyToReduce = 1.0f/4.0f;

//you didn't implement the constructor of your class that was required. This should do the work.
//Just mind that the 4 it's the initial capacity of the array.
public Queue(Class<T> clazz) {
    this.clazz = clazz;
    this.array = (T[]) Array.newInstance(clazz, 4);
    this.n = 0;
}

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

public int size() {
    return n;
}

//cleaned a bit enqueue and dequeue method and extrapolating the logic for resize.
public void enqueue(T item) {
    array[n] = item;
    n  ;
    if(expansionIsNeeded()) performResizeExpanding();
}

public T dequeue() {
    T value = array[0];
    slideBackArray();
    n--;
    if(reduceIsNeeded()) performResizeReducing();
    return value;
}


//logic for sliding back items when dequeueing
private void slideBackArray() {
    for (int i = 1; i < n; i  ) {
        array[i - 1] = array[i];
    }
    array[n] = null;
}


//these 2 methods take care of triggering resize
private boolean expansionIsNeeded() {
    float currentFilling = (float) n / array.length;
    return currentFilling >= policyToExpand;
}
private boolean reduceIsNeeded() {
    float currentFilling = (float) n / array.length;
    return currentFilling <= policyToReduce;
}

//these 2 instead perform the actual resize
private void performResizeExpanding() {
    T[] tempArray = (T[]) Array.newInstance(clazz, this.array.length*2);
    System.arraycopy(this.array, 0, tempArray, 0, n);
    this.array = tempArray;
}

private void performResizeReducing() {
    T[] tempArray = (T[]) Array.newInstance(clazz, this.array.length/2);
    System.arraycopy(this.array, 0, tempArray, 0, n);
    this.array = tempArray;
}

}

CodePudding user response：

Some issues:

The first enqueue call will already produce an Null Pointer Exception. A minimal test would have revealed this. Your array is not initialised and so access to array.length or array[0] or similar will trigger a NPE. You need to initialise the array upon construction.
array.length * 2 will not change the array size when it is 0, it is probably best to initialise your array with a size of at least 1, and never allow it to be come less.
Code that shrinks the array is lacking.
dequeue should not have to move every element every time you call it. Typically, an array-based queue keeps track of the start of the data and the end, so that the used part of the array does not necessarily have to start at index 0. Instead of an N member, define start and end members.

Here is a possible adjustment of your class:

public class Queue<T> {
    private T[] array;
    private int start, end; // Instead of N, so to gain efficiency in dequeue
    
    Queue() {
        array = (T[]) new Object[1]; // Initialise!
    }
     
    public boolean isEmpty() {
        return start == end;
    }
    
    public int size() {
        return (end   array.length - start) % array.length;
    }
     
    public void resize(int max) {
        T[] temp = (T[]) new Object[max];
        if (end > start) {
            end -= start;
            System.arraycopy(array, start, temp, 0, end);
            start = 0;
            end %= max;
        } else {
            System.arraycopy(array, 0, temp, 0, end);
            int size = array.length - start;
            System.arraycopy(array, start, temp, max - size, size);
            start = max - size;
        }
        array = temp;
    }
    
    public void enqueue(T item) {
        array[end] = item;
        end = (end   1) % array.length;
        if (start == end) {
            resize(array.length * 2);
        }
    }

    public T dequeue() {
        if (array.length > 1 && size() <= array.length / 2) {
            resize(array.length / 2); // Shrink
        }
        T value = array[start];
        array[start] = null;
        start = (start   1) % array.length;
        return value;
    }
}