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

In above problem statement we are required to create and implemet a Dequeue, which is a double ended queue which has a front and a rear.

Whenever an element is suppose to be added to this queue it will be added at the end of the queue and whenever an element is poped it will be from the rear.

Lets first complete class QuueBox(refer below code snippet):

public class QueueBox<E> {
    private int QUEUE_SIZE = 5;
    private Object[] elements;
    private int front_idx, rear_idx, count;

    public QueueBox() {
        elements = new Object[QUEUE_SIZE];
        this.front_idx = 0;
        this.rear_idx = QUEUE_SIZE -1;
        this.count = 0;
    }

    //checks whether queue is empty or not
    public boolean isEmpty(){
        return count == 0;
    }

    //checks whether queue is full or not
    public boolean isFull(){
        return count == QUEUE_SIZE;
    }

    //adds an element to rear
    public void add(Object newItem) {
        if (!isFull()) {
            rear_idx = (rear_idx + 1) % QUEUE_SIZE;
            elements[rear_idx] = newItem;
            count++;
            return;
        }
        else {
            System.out.println("Queue is full. Doubling the size.");
            QUEUE_SIZE = (QUEUE_SIZE * 2); // double queue size not count 
            System.out.println("New max size is: " + QUEUE_SIZE);
            Object[] temp = new Object[QUEUE_SIZE]; // temp array
            System.arraycopy(elements, front_idx, temp, front_idx, elements.length - front_idx); // copy the elements from front_idx index to elements.length-front_idx
            if (front_idx != 0) {
                System.arraycopy(elements, 0, temp, elements.length, front_idx); // copy the elements in the range elements[0] to elements[rear_idx] into the new array
            }
            elements = temp; // set elements to temp array
            rear_idx = front_idx + count;
            elements[rear_idx] = newItem; // set new item 
            count++; // increment count
        }

    }

    //removes an element from front_idx
    public Object remove(){
        if (!isEmpty()){
            Object queuefront_idx = elements[front_idx];
            System.out.println("Element removed after DeQueuing: " + queuefront_idx.toString());
            front_idx = (front_idx+1) % QUEUE_SIZE;
            count--;
            return front_idx;
        }else
            System.out.println("Trying to dequeue from empty queue");
        return null;
    }

    //returns the head of the queue
    public Object element(){
        if (!isEmpty()) {
            return elements[front_idx];
        }
        else
            System.out.println("Trying to peek with empty queue");
        return null;
    }

    //returns size of the queue
    public int size(){
        return count;
    }

}

Now lets complete class QueueBoxDriver(refer below code snippet):

public class QueueBoxDriver {
    public static void main(String[] args) {
        QueueBox q = new QueueBox();
        createQueue(q);
        destroyQueue(q);

        while (!q.isEmpty()){
            q.remove();
        }
    }

    //adds 60,000 integers
    public static QueueBox createQueue(QueueBox q){
        for (int i=0; i<60000; i++){
            q.add(i);
        }
        return q;
    }

    public static QueueBox destroyQueue(QueueBox q){
        for (int i=0; i<50000; i++){
            q.remove();
        }
        return q;
    }
}