CircularArrayQueue implementation Java

Question

I am trying to implement a CircularArrayQueue. I've been given a JUnit test which my queue must pass.I suppose I am doing something wrong with the front and rear pointers. How should i approach learning data structures and algorithms ?

import java.util.NoSuchElementException;

public class CircularArrayQueue implements MyQueue {
    private Integer[] array;
    // initial size of the array
    private int N;
    private int front;
    private int rear;

    public CircularArrayQueue() {
        this.N = 10;
        array = new Integer[N];
        front = rear = 0;
    }

    public CircularArrayQueue(int size) {
        this.N = size;
        array = new Integer[N];
        front = rear = 0;
    }

    // enqueues an element at the rear of the queue
    // if the queue is already full it is resized, doubling its size
    @Override
    public void enqueue(int in) {
        if (rear == N) {
            if (front == 0) {
                resize();
                array[rear] = in;
                rear++;
            } else {
                array[rear] = in;
                rear = 0;
            }
        } else {
            array[rear] = in;
            rear++;
        }

    }

    public void resize() {
        Integer[] temp = new Integer[array.length * 2];

        for (int i = 0; i < array.length; i++) {
            temp[i] = array[i];
        }

        temp = array;
    }

    // dequeues an element
    // if the queue is empty a NoSuchElement Exception is thrown
    @Override
    public int dequeue() throws NoSuchElementException {
        if (isEmpty()) {
            throw new NoSuchElementException("The queue is full");
        }

        int headElement = array[front];

        if (front == N) {
            array[front] = null;
            front = 0;
        } else {
            array[front] = null;
            front++;
        }

        return headElement;
    }

    @Override
    public int noItems() {
        return N - getCapacityLeft();
    }

    @Override
    public boolean isEmpty() {
        return (getCapacityLeft() == N);
    }

    // return the number of indexes that are empty
    public int getCapacityLeft() {
        return (N - rear + front) % N;
    }
}

Answer 1

Your initialization is absolutely fine, and we do start with:

front = rear = 0;

Befor adding an item to the Q, we modify rear as

rear = (rear + 1) % N;

The % allows us to maintain the circular property of the queue. Also you must be wondering that if we modify rear before adding any item, then 0 index is left empty, well we have to compromise here with one array item being left blank, in order to have correct implementations for checking of isEmpty() and isFull() functions:

That said, the correct code for isEmpty() is:

@Override
public boolean isEmpty()
{
    return front == rear;
}

You should also have a function isFull() like:

@Override
public boolean isFull()
{
    return front == ((rear + 1) % N);
}

Also the line temp = array; in your resize() should be array = temp; and you must also update the value of N after calling resize().

Hence, the correct code is:

import java.util.NoSuchElementException;

public class CircularArrayQueue implements MyQueue 
{
private Integer[] array;
//initial size of the array
private int N;
private int front;
private int rear;
private int count = 0;//total number of items currently in queue.
public CircularArrayQueue()
{
    this.N = 10;
    array = new Integer[N];
    front = rear = 0;
}

public CircularArrayQueue(int size)
{
    this.N = size;
    array = new Integer[N];
    front = rear = 0;
}


//enqueues an element at the rear of the queue
// if the queue is already full it is resized, doubling its size
@Override
public void enqueue(int in) 
{
    count++;
    if (isFull())
    {
       resize();
       rear = (rear + 1) % N;
       array[rear] = in;
    }
    else
    {
       rear = (rear + 1) % N;
       array[rear] = in;
    }            
}

public void resize()
{
    Integer[] temp = new Integer[array.length*2];
    N = array.length*2;
    for(int i=0; i<array.length; i++)
    {
        temp[i] = array[i];
    }

    array = temp;
}


//dequeues an element
// if the queue is empty a NoSuchElement Exception is thrown
@Override
public int dequeue() throws NoSuchElementException 
{
    if(isEmpty())
    {
        throw new Exception("The queue is empty");
    }

    front = (front + 1) % N;
    int headElement = array[front];   
    count--;
    return headElement;
}

@Override
public int noItems() 
{   
    return count;
}

@Override
public boolean isEmpty()
{
    return front == rear;
}

@Override
public boolean isFull()
{
    return front == ((rear + 1) % N);
}

//return the number of indexes that are empty
public int getCapacityLeft()
{
    return N - 1 - count;
}   
}