Java Program to Implement Circular Queue

Introduction

A circular queue is a linear data structure that follows the First In, First Out (FIFO) principle, where the last position in the queue connects back to the first position to form a circle. This circular arrangement helps efficiently use memory by reusing previously occupied positions once they are freed. This guide will walk you through writing a Java program that implements a circular queue using an array.

Problem Statement

Create a Java program that:

Implements a circular 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 Circular Queue Structure: Define a CircularQueue 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 Circular Queue
// Author: https://www.rameshfadatare.com/

class CircularQueue {
    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 CircularQueue(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 {
            rear = (rear + 1) % maxSize;  // Circular increment of rear
            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];
            front = (front + 1) % maxSize;  // Circular increment of front
            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 CircularQueueDemo {
    public static void main(String[] args) {
        CircularQueue queue = new CircularQueue(5); // Create a circular 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 CircularQueue Class

The CircularQueue class represents the circular 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. The rear is incremented circularly using the modulo operation to wrap around to the beginning when the end of the array is reached.
Dequeue: Removes and returns the front element of the queue if it’s not empty. The front is incremented circularly using the modulo operation to wrap around to the beginning when the end of the array is reached.
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 the circular nature of 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:

CircularQueue queue = new CircularQueue(3); // Create a circular 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 circular queue using an array, including handling overflow and underflow conditions. The program efficiently manages queue operations, providing a flexible and memory-efficient way to handle queues. This exercise is valuable for understanding how to implement and manipulate circular queues in Java programming.