Question

TestQueue.java

Design a class named Queue for storing integers. Like a stack, a queue holds elements. But in a queue, the elements are retrieved in a first-in first-out fashion. The class contains:

An int[] data field named elements that stores the int values in the queue.

A data field named size that stores the number of elements in the queue.

A constructor that creates a Queue object with default capacity 8.

The method enqueue(int v) that adds v into the queue.

The method dequeue() that removes and returns the element from the queue.

The method empty() that returns true if the queue is empty.

The method getSize() that returns the size of the queue.

Implement the class with the initial array size set to 8. The array size will be doubled once the number of elements exceeds the size. After an element is removed from the beginning of the array, you need to shift all the elements in the array one position to the left.

Write a test program that adds 20 numbers from 1 to 20 into the queue then removes these numbers and displays them.

Answer 1

Summary:

Below Java program is an implementation of Queue with an dynamic array that doubles it size when the array capacity is reached. We have implemented queue operations like enqueue, dequeue, empty and getSize methods.

enqueue adds the given element to the queue.

dequeue removes the element from the queue.

empty checks if the queue is empty or not.

getSize returns the current size of the queue.

Java Program:

--------------------------------------------------------------TestQueue.java-----------------------------------------------------

public class TestQueue {

    private int capacity = 8;
    private int data[];
    private int front = 0;
    private int rear = -1;
    private int size = 0;

    public TestQueue() {
        data = new int[this.capacity];
    }

    /**
     * this method adds element at the end of the queue.
     *
     * @param v new value to add into queue
     */
    public void enqueue(int v) {

        if (isQueueFull()) {
            System.out.println("Queue is full, increasing capacity by double...");
            increaseQueueCapacity();
        }
        rear++;
        if (rear >= data.length && size != data.length) {
            rear = 0;
        }
        data[rear] = v;
        size++;
        System.out.println("Adding: " + v);
    }

    /**
     * this method removes an element from the top of the queue
     */
    public int dequeue() {
        int temp = 0;
        if (empty()) {
            System.out.println("Queue is empty!");
        }
        front++;
        if (front > data.length - 1) {
            temp = data[front - 1];
            size--;
            front = 0;
            return temp;
        }
        temp = data[front - 1];
        size--;
        return temp;

    }

    /**
     * This method checks whether the queue is empty or not
     *
     * @return
     */
    public boolean empty() {
        boolean status = false;
        if (size == 0) {
            status = true;
        }
        return status;
    }

    /**
     *
     * @return the current size of the Queue.
     */
    public int getSize(){
        return this.size;
    }



    /**
     * This method checks whether the queue is full or not
     *
     * @return boolean
     */
    public boolean isQueueFull() {
        boolean status = false;
        if (size == data.length) {
            status = true;
        }
        return status;
    }



    private void increaseQueueCapacity() {

        //create new array with double size as the current one.
        int newCapacity = this.data.length * 2;
        int[] newArr = new int[newCapacity];
        //copy elements to new array, copy from rear to front
        int tmpFront = front;
        int index = -1;
        while (true) {
            newArr[++index] = this.data[tmpFront];
            tmpFront++;
            if (tmpFront == this.data.length) {
                tmpFront = 0;
            }
            if (size == index + 1) {
                break;
            }
        }
        //make new array as queue
        this.data = newArr;
        System.out.println("New array capacity: " + this.data.length);
        //reset front & rear values
        this.front = 0;
        this.rear = index;
    }

    public static void main(String a[]) {

        TestQueue queue = new TestQueue();
        // Adding first 8 elements to the queue
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.enqueue(4);
        queue.enqueue(5);
        queue.enqueue(6);
        queue.enqueue(7);
        queue.enqueue(8);


        // Checking the current size of the queue and printing it.
        System.out.println("\nThe current size of Queue: " + queue.getSize());
        System.out.println();

        // Adding one new element to check if queue size doubles.
        queue.enqueue(9);
        queue.enqueue(10);
        queue.enqueue(11);
        queue.enqueue(12);
        queue.enqueue(13);
        queue.enqueue(14);
        queue.enqueue(15);
        queue.enqueue(16);
        queue.enqueue(17);
        queue.enqueue(18);
        queue.enqueue(19);
        queue.enqueue(20);

        // Removing 3 elements from queue.
        System.out.println( "Removed: " +queue.dequeue());
        System.out.println( "Removed: " +queue.dequeue());
        System.out.println( "Removed: " +queue.dequeue());

        // Checking current size
        System.out.println("\nThe current size of Queue: " + queue.getSize());
        System.out.println();

        // Removed remaining elements
        System.out.println( "Removed: " +queue.dequeue());
        System.out.println( "Removed: " +queue.dequeue());
        System.out.println( "Removed: " +queue.dequeue());
        System.out.println( "Removed: " +queue.dequeue());
        System.out.println( "Removed: " +queue.dequeue());
        System.out.println( "Removed: " +queue.dequeue());

        // Checking current size
        System.out.println("\nThe current size of Queue: " + queue.getSize());
        System.out.println();
    }
}

Output:

Hope this will help you. Enjoy!!!