Question

Data Structures and Algorithms Activity

Requirement: Implement a queue using an array as its underline data structure. Your queue should fully implemnted the following methods: first, push_back (enqueue), pop_front (dequeue), size, and isEmpty. Make sure to include a driver to test your newly implemented queue

Answer 1

Algorithm:

1. First of all, we are creating an array and initializing its front and rear points.
2. Whenever we adding any value to the queue, the rear value gets increased.
3. When we pop any value, front value also gets increased but the difference of rear and front can only be equal to the initialized size of the queue at max.
4. We are using the constructor to initialize the capacity of the Queue.
5. Note: Please take care of the package while running the program on your system.
6. Read the program from the starting line-by-line for better understanding.

Please refer to the comments of the program for more clarity.

Main.java / Driver code:

package com.company;

public class Main {

    public static void main(String[] args) {
        Queue q = new Queue(4);

        // print Queue elements
        q.queueDisplay();

        // inserting elements in the queue
        q.push_back (50);
        q.push_back (10);
        q.push_back (6);
        q.push_back (588);

        // print Queue elements
        q.queueDisplay();

        // insert element in the queue
        q.push_back (60);

        // print Queue elements
        q.queueDisplay();

        q.pop_front();
        q.pop_front();
        System.out.printf("\n\nAfter two node deletion\n\n");

        q.push_back (60); // Adding a new element
        // print Queue elements
        q.queueDisplay();

        // print front of the queue
        q.first();

        // Checking queue is empty or not
        System.out.println("\n\nIs Queue empty: " + q.isEmpty());

        // Checking size of the queue
        System.out.println("nSize of the queue: " + q.size());
    }
}

Queue.java:

package com.company;

// Queue class to implement a queue using array
class Queue {

    // Declaring variables
    private static int front, rear, capacity;
    private static int queue[];


    // Constructor to initialize the value
    Queue(int c) {
        front = rear = 0;
        capacity = c;
        queue = new int[capacity];
    }

    // function to insert an element
    // at the rear of the queue
    static void push_back(int data) {
        // check queue is full or not
        if (capacity == rear) {
            System.out.printf("\nQueue is full\n");
            return;
        }

        // insert element at the rear
        else {
            queue[rear] = data;
            rear++;
        }
        return;
    }

    // function to delete an element
    // from the front of the queue
    static void pop_front() {
        // if queue is empty
        if (front == rear) {
            System.out.printf("\nQueue is empty\n");
            return;
        }

        // shift all the elements from index 2 till rear
        // to the right by one
        else {
            for (int i = 0; i < rear - 1; i++) {
                queue[i] = queue[i + 1];
            }

            // store 0 at rear indicating there's no element
            if (rear < capacity)
                queue[rear] = 0;

            // decrement rear
            rear--;
        }
        return;
    }

    // print queue elements
    static void queueDisplay()
    {
        int i;
        if (front == rear) {
            System.out.printf("\nQueue is Empty\n");
            return;
        }

        // traverse front to rear and print elements
        for (i = front; i < rear; i++) {
            System.out.printf(" %d < ", queue[i]);
        }
        return;
    }

    // print front of queue
    static void first()
    {
        if (front == rear) {
            System.out.printf("\nQueue is Empty\n");
            return;
        }
        System.out.printf("\nFront Element is: %d", queue[front]);
        return;
    }

    // Check if Queue is empty or not

    static boolean isEmpty(){
        if(front == rear)
            return true;
        else
            return false;
    }

    static int size(){
        return rear - front;
    }
}

Sample Input-Output/CodeRun:

Please let me know in the comments in case of any confusion. Also, please upvote if you like.