Question

QUEUEBOX:

Using an Array of initial size of five (5) for storage, start with the following generic class declaration for QueueBox:

public class QueueBox<E> {
private E[] elements = (E[])( new Object[5] );
private int front_idx = 0;
private int rear_idx = 0;
private int count = 0;
}

Hint: use the count variable to keep track of how many elements are in the queue (increment count when enqueing and decrement when dequeing). Makes it a lot easier to determine if the array is full and for the other functions as well.

Of course you may add or modify variables to this class BUT you MUST use a GENERIC array of initial size 5 and your queue MUST be a circular queue. Ensure your QueueBox can do the following:

boolean add(E e)
Adds e to the queue (enqueue). returns true. Throws NullPointerException if e is null.

E remove()
Removes element in the front of the queue (dequeue) and returns it. NoSuchElementException is thrown if this queue is empty

E element()
Retrieves, but does not remove, the head of the queue. Throws NoSuchElementException - if the queue is empty.

boolean isEmpty()
returns true if queue is empty.

int size()
returns number of elements held in the queue.

Create a driver class QueueBoxDriver that creates an instance of QueueBox<Integer> then fills it with 60,000 integers numbered from 0 to 59999 (in that order). Your QueueBox must be able to resize itself (double in size) when needed to accomodate. Everytime your queue auto-resizes it must display that it has done so (see output below). After you create your queue and populate it, dequeue the first 50000 elements.

Now dequeue the remaining 10000 elements and display them to the screen. Continue until the queue is empty. Your output should look as close as possible to this:

OUTPUT:
Array resized to 10
Array resized to 20
Array resized to 40
Array resized to 80
Array resized to 160
Array resized to 320
Array resized to 640
Array resized to 1280
Array resized to 2560
Array resized to 5120
Array resized to 10240
Array resized to 20480
Array resized to 40960
Array resized to 81920
50000
50001
50002
50003
50004
50005
50006
...

...

...
59997
59998
59999

Marking Criteria

Correct implementation of a queue with generic queue methods ... 5

Working implementation of a circular queue ... 10

Automatic resizing of the queue ... 3

Correct output ... 2

Answer 1

/////////////////////    QueueBox class     /////////////////////////

/**

*

* Queue Box class to implement resizable circular array

*/

import java.util.NoSuchElementException;

public class QueueBox<E> {

    private E[] elements = (E[])( new Object[5] );

    private int front_idx = 0;

    private int rear_idx = 0;

    private int count = 0;

    private int size=5;

    

    /** Defining constructor to set front and rear indexes are -1 to notify that there are no elements initially*/

QueueBox(){

    front_idx =-1;     

    rear_idx=-1;

}    

boolean add  (E e){

    /** Throws null pointer exception if e is null */

    if(e==null){

        throw new NullPointerException();

    }

    /** check if whether elements are filled to maximum capacity

     * if yes increase the size of array by twice

     */

    if((rear_idx==size-1 && front_idx==0)||(rear_idx==front_idx-1)){

        size=2*size;

        E[] temp = (E[])( new Object[2*size]);

        for(int i=0;i<count;i++){                                  // moving elements of old array to new array

            temp[i]=elements[i];

        }

        elements =temp;                                           // pointing element to new array

        System.out.println("Array resized to " + size);             //printing out that array is resized

    }

    

    if(front_idx==-1){                  // if initially the array is empty set front index to zero

        front_idx=0;

    }

    elements[++rear_idx]=e;

    count++;

    return true;

}

E remove(){

    /** throw exception if array is empty

     *  we can use either front_idx ==-1 or count==0 or isempty to check if the array is empty

     */

    if(front_idx==-1){

        throw new NoSuchElementException();

    }

    E temp = elements[front_idx];

    /**

     * if front_idx == rear_idx set them to -1 stating that no elemnt is there in array

     */

    if(front_idx == rear_idx){

        front_idx=-1;

        rear_idx=-1;

    }

    else if(front_idx == size-1){

    front_idx=0;

    }

    else{

        front_idx++;     // increment front index after every dequeue to point to next element in queue

    }

    count--;

    return temp;

}

E element(){

    /**

     * if there is an element returns element

     * if not throws exception

     */

    if(count==0){

        throw new NoSuchElementException();

    }

    return elements[front_idx];

}

boolean isEmpty(){

    if(count==0){

        return true;

    }

    return false;

}

int size(){

    return count;

}

}

//////////////////////////////////////// tester code   ///////////////////////

public class tester {

    public static void main(String[] args ) {

        QueueBox<Integer> queue= new QueueBox<Integer>();    // creating an instance of QueueBox and naming it as queue

        for(int i=0;i<60000;i++){                           // adding 60000 elements to queue

            queue.add(i);

        }

        for(int i=0;i<50000;i++){           //removing 50000 elements from queue

            queue.remove();

        }

        while(!queue.isEmpty()){

            System.out.println(queue.remove());      // printing remaining elements of queue by dequeue

        }

        

    }

    

}