Queue with using array in Java

Question

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;
 }
}

To check, write tests. A test may be trying to fill the queue such that it will resize, empty the queue, verify that everything pushed in it can be extracted from, etc. — Jean-Baptiste Yunès
– Jean-Baptiste Yunès, Commented Jan 5, 2023 at 14:33
Write a unit test for it. Enque a single element, assert that it contains what is expected. Enqueue a few elements, assert. Dequeue from empty, assert that exception is thrown. Enqueue a few, then dequeue, assert that elements are correct and in expected order. Finally, write a test that checks for resizing. That should cover it, no? — Shark
– Shark, Commented Jan 5, 2023 at 14:34
I recommend a tutorial on unit testing, e.g. this one over at vogella.com. --- A remark I would just use an Object[] instead of a T[]. This is how ArrayList (github.com) does things. Mixing arrays and generics is always a pain since arrays are covariant and retained, while generics are invariant and erased — Turing85
– Turing85, Commented Jan 5, 2023 at 14:35
One more hint: System.arrayCopy is your friend... docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/… — Taylor
– Taylor, Commented Jan 5, 2023 at 14:58
"both growing and shrinking": you didn't do the shrinking part. — trincot
– trincot, Commented Jan 5, 2023 at 15:07

Zartof · Accepted Answer · 2023-01-05 19:42:22Z

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;
}
}

trincot · Accepted Answer · 2023-01-05 16:50:31Z

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;
    }
}

Collectives™ on Stack Overflow

Queue with using array in Java

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related