Java Program to Implement a Queue Using Array

Introduction

A queue is a linear data structure that follows the First In, First Out (FIFO) principle, where elements are added (enqueued) to the rear and removed (dequeued) from the front. This guide will walk you through writing a Java program that implements a queue using an array. The queue operations include enqueue, dequeue, peek, and checking if the queue is empty or full.

Problem Statement

Create a Java program that:

Implements a queue using an array.
Provides methods to perform standard queue operations: enqueue, dequeue, peek, isEmpty, and isFull.
Displays the queue contents after various operations.

Example:

Input: Enqueue elements: 10, 20, 30
Operations: enqueue(40), dequeue(), peek()
Output:
- After enqueuing 40: [10, 20, 30, 40]
- After dequeuing: [20, 30, 40]
- Peeked element: 20

Solution Steps

Create the Queue Structure: Define a Queue class to represent the queue, including methods for standard queue operations.
Implement Queue Operations: Implement methods to enqueue elements into the queue, dequeue elements from the queue, peek at the front element, and check if the queue is empty or full.
Handle Edge Cases: Ensure the queue handles underflow (dequeuing from an empty queue) and overflow (enqueuing to a full queue) conditions.
Display the Queue: Output the queue’s contents after performing various operations.

Java Program

// Java Program to Implement a Queue Using Array
// Author: https://www.rameshfadatare.com/

class Queue {
    private int maxSize;
    private int front;
    private int rear;
    private int[] queueArray;
    private int nItems;  // Number of items in the queue

    // Constructor to initialize the queue
    public Queue(int size) {
        maxSize = size;
        queueArray = new int[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    // Method to enqueue an element into the queue
    public void enqueue(int value) {
        if (isFull()) {
            System.out.println("Queue is full. Unable to enqueue " + value);
        } else {
            if (rear == maxSize - 1) {
                rear = -1;  // Wrap around to the beginning of the array
            }
            queueArray[++rear] = value;
            nItems++;
            System.out.println("Enqueued " + value + " into the queue.");
        }
    }

    // Method to dequeue an element from the queue
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Unable to dequeue.");
            return -1; // Return a sentinel value indicating the queue is empty
        } else {
            int dequeuedValue = queueArray[front++];
            if (front == maxSize) {
                front = 0;  // Wrap around to the beginning of the array
            }
            nItems--;
            System.out.println("Dequeued " + dequeuedValue + " from the queue.");
            return dequeuedValue;
        }
    }

    // Method to peek at the front element of the queue
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Nothing to peek.");
            return -1; // Return a sentinel value indicating the queue is empty
        } else {
            System.out.println("Peeked at the front element: " + queueArray[front]);
            return queueArray[front];
        }
    }

    // Method to check if the queue is empty
    public boolean isEmpty() {
        return (nItems == 0);
    }

    // Method to check if the queue is full
    public boolean isFull() {
        return (nItems == maxSize);
    }

    // Method to display the contents of the queue
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty.");
        } else {
            System.out.print("Queue contents: ");
            for (int i = 0; i < nItems; i++) {
                int index = (front + i) % maxSize;
                System.out.print(queueArray[index] + " ");
            }
            System.out.println();
        }
    }
}

public class QueueDemo {
    public static void main(String[] args) {
        Queue queue = new Queue(5); // Create a queue with a maximum size of 5

        // Enqueue elements into the queue
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.display();

        // Enqueue another element
        queue.enqueue(40);
        queue.display();

        // Dequeue an element from the queue
        queue.dequeue();
        queue.display();

        // Peek at the front element
        queue.peek();
        queue.display();

        // Attempt to enqueue more elements to test overflow
        queue.enqueue(50);
        queue.enqueue(60);
        queue.enqueue(70); // This enqueue should trigger an overflow condition
        queue.display();

        // Dequeue all elements to test underflow
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue(); // This dequeue should trigger an underflow condition
        queue.display();
    }
}

Explanation

Step 1: Initialize the Queue Class

The Queue class is used to represent a queue, including methods for standard queue operations.
The queue is represented by an integer array (queueArray), with front pointing to the first element and rear pointing to the last element. The maxSize defines the maximum capacity of the queue, and nItems keeps track of the number of elements in the queue.

Step 2: Implement Queue Operations

Enqueue: Adds an element to the rear of the queue if it’s not full. If the rear reaches the end of the array, it wraps around to the beginning.
Dequeue: Removes and returns the front element of the queue if it’s not empty. If the front reaches the end of the array, it wraps around to the beginning.
Peek: Returns the front element without removing it. If the queue is empty, an appropriate message is displayed.
isEmpty: Checks if the queue is empty by verifying if nItems is 0.
isFull: Checks if the queue is full by verifying if nItems is equal to maxSize.
Display: Prints all elements currently in the queue, accounting for wrapping around the array.

Output Example

Enqueued 10 into the queue.
Enqueued 20 into the queue.
Enqueued 30 into the queue.
Queue contents: 10 20 30 
Enqueued 40 into the queue.
Queue contents: 10 20 30 40 
Dequeued 10 from the queue.
Queue contents: 20 30 40 
Peeked at the front element: 20
Queue contents: 20 30 40 
Enqueued 50 into the queue.
Enqueued 60 into the queue.
Queue is full. Unable to enqueue 70
Queue contents: 20 30 40 50 60 
Dequeued 20 from the queue.
Dequeued 30 from the queue.
Dequeued 40 from the queue.
Dequeued 50 from the queue.
Queue is empty. Unable to dequeue.
Queue is empty.

Example with Different Queue Size

If you modify the queue size to 3:

Queue queue = new Queue(3); // Create a queue with a maximum size of 3

The output will adjust accordingly, demonstrating the queue’s overflow condition when more than 3 elements are enqueued.

Conclusion

This Java program demonstrates how to implement a queue using an array, including handling overflow and underflow conditions. The program efficiently manages queue operations, providing fundamental functionality commonly used in various applications. This exercise is valuable for understanding how to implement and manipulate queues in Java programming.