java – Implementing Queue using Dynamic Circular Array

I am going through a course and after learning the theory I decided to implement the DS on my own. I write a few test cases and all operations seem to be working fine but once I tried to double check with the course’s solution, it is not clear if I am missing anything since my logic is not line by line the same 🙁

Resizing approach I took:

  • Doubling once full capacity is reach
  • Halving once number of items in the Queue decrease to 1/4 of capacity

Operations:

public E dequeue()
public void enqueue(E item)
public int size()
private boolean isFullCapacity()
private boolean isFourthCapacity()
private void resize(int newSize)
public boolean isEmpty()

If anyone can point me to where I can more thoroughly test, I would also appreciate it. I could not find any test suite on the internet. Would also appreciate general good practices feed back 🙂

public class QueueResizingArray <E> implements Queue<E> {

    private E() arr;
    private int size;
    private int front;
    private int end;

    private static final int INITIAL_CAPACITY = 6;
    private static final int INCREASE_FACTOR = 2;


    public QueueResizingArray(){
        this.arr = (E()) new Object(INITIAL_CAPACITY);
    }

    @Override
    public void enqueue(E item) {
        if(item == null)
            throw new IllegalArgumentException("item entered cannot be null");

        this.arr(front) = item;
        this.front = getNextPointerInCircularArray(this.front);
        this.size ++;


        if(isFullCapacity())
            resize(INCREASE_FACTOR * this.arr.length);

    }

    @Override
    public E dequeue() {
        if(this.isEmpty())
            throw new NoSuchElementException("Queue is empty when trying to dequeue");

        E item = this.arr(end);
        this.arr(end) = null;
        this.end = getNextPointerInCircularArray(this.end);
        this.size--;

        /*
        first condition added otherwise following will happen.
         , lets take as an example an array of length, arr.length = 3,
         and there is one item in array, size = 1, and we decide to dequeue this single item.
         size = 1 will decrement to 0 in the dequeue() method and the reach isFourthCapacity().
          at this point, the following check occurs. if ( size == arr.length/4) in this case
          since size = 1 and arr.length = 4, the check evaluates to if ( 0 == 0), triggering a resize even with no items present.
          if (0 == 0)
         incorrectly triggering shrinking even with no items present
         0 (size)/3 (array.length) = 0 (
         */
        if(this.size > 0 && isFourthCapacity())
            resize(this.arr.length/2);

        return item;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    @Override
    public int size() {
        return this.size;
    }

    private boolean isFullCapacity(){
        return this.size == this.arr.length;
    }

    private boolean isFourthCapacity(){
        return this.size == this.arr.length/4;
    }


    private void resize(int newArrLength){
        E() newArr = (E()) new Object(newArrLength);
        int insertIndex = 0;
        int tempEnd = this.end;

        do{
            newArr(insertIndex) = this.arr(tempEnd);
            tempEnd = getNextPointerInCircularArray(tempEnd);
            insertIndex++;
        }while(this.front != tempEnd);

        //the reason why i move end is because  if halving, end will lag front and we can increment end to touch all items we need to copy. I think we could also decrement front
        //TODO we need a do while to move end one away from front, below does not work because when full, end will equal front not triggering copying of elements
//        while(this.front != tempEnd){
//            newArr(insertIndex) = this.arr(tempEnd);
//            tempEnd = getNextPointerInCircularArray(tempEnd);
//            insertIndex++;
//        }

        //resetting indexes after resizing
        this.front = this.size;
        this.end = 0;
        //setting new array
        this.arr = newArr;
    }

    private int getNextPointerInCircularArray(int reference){
        return (reference + 1) % this.arr.length;
    }
}

Tests:

public class Test {

    @org.junit.Test
    public void testMyCircularResizingArraySolution(){
        Queue<Integer> queue = new QueueResizingArray<>();

        //enqueue
        queue.enqueue(1);

        //assert
        Assert.assertEquals(1, queue.size());

        //dequeue
        int item1 = queue.dequeue();
        Assert.assertEquals(1, item1);
        Assert.assertEquals(0, queue.size());


        //6 enqueues
        queue.enqueue(1);
        queue.enqueue(1);
        queue.enqueue(1);
        queue.enqueue(-9);
        queue.enqueue(2);
        queue.enqueue(7);

        //last enqueue should have triggered doubling of circular array

        int item2 = queue.dequeue();
        Assert.assertEquals(1, item2);

        Assert.assertEquals(5, queue.size());


        int item3 = queue.dequeue();
        Assert.assertEquals(1, item3);

        Assert.assertEquals(4, queue.size());


        //will trigger halving
        int item4 = queue.dequeue();
        Assert.assertEquals(1, item4);

        Assert.assertEquals(3, queue.size());



        int item5 = queue.dequeue();
        Assert.assertEquals(-9, item5);

        Assert.assertEquals(2, queue.size());


        int item6 = queue.dequeue();
        Assert.assertEquals(2, item6);

        Assert.assertEquals(1, queue.size());



        int item7 = queue.dequeue();
        Assert.assertEquals(7, item7);

        Assert.assertEquals(0, queue.size());

   }

}