ISC Practicals and Theory - Circular Queue (OOP)

A circular queue is a queue stored in an array in which the position after the last index is the first index, so the space freed by removed elements is used again. This version is written in the object-oriented style: the capacity is passed to a parameterised constructor, add returns true or false, remove returns the removed element, and main prints the messages.

Definition

A queue works on the first-in first-out (FIFO) rule: elements are added at the rear and removed from the front. In a circular queue the array is treated as a ring: after index cap - 1 the next index is 0, found with the remainder operator:

$next = (index + 1) \% cap$

For a capacity of 5, if rear is 4 then (4 + 1) % 5 = 0, so the next element goes to index 0.

Convention used in this program:

• front = -1 and rear = -1 mean the queue is empty.
• The first element is stored at index 0, so front = rear = 0.
• The queue is full when (rear + 1) % cap == front. All cap slots can be used.
• When the last element is removed (front == rear), both are set back to -1.

Return values: add returns false on overflow. remove returns -1 when the queue is empty, but -1 can also be a stored value, so main calls isEmpty() first and only then calls remove().

Capacity: it must be from 1 to 20.

Algorithm

1. In main, read the capacity c. If c < 1 or c > 20, print an error message and stop. Otherwise create obj = new CircularQueue(c); the constructor creates the array q of size c and sets front = rear = -1.
2. Repeat the menu until the choice is 4: print the menu, read choice and act on it. Any other number prints Invalid choice. Enter 1 to 4.
3. Choice 1: read v and call obj.add(v).
   • In add, if isFull() return false.
   • If the queue is empty set front = 0 and rear = 0; else set rear = (rear + 1) % cap.
   • Store v in q[rear] and return true.
   • main prints the added message for true and the overflow message for false.
4. Choice 2: if obj.isEmpty() print the underflow message. Otherwise call obj.remove():
   • Take v = q[front]. If front == rear set front = -1 and rear = -1; else set front = (front + 1) % cap. Return v, which main prints.
5. Choice 3: call obj.display().
   • If the queue is empty, print a message.
   • Otherwise start with i = front, print q[i], move i = (i + 1) % cap, and repeat until i becomes (rear + 1) % cap.
6. Choice 4 prints Program ended. and the loop stops.

Program

The constructor creates the array, isEmpty and isFull test the two limits, add and remove return their results, display prints from front to rear going round, and main reads the input with one Scanner, prints the messages and runs the menu.

import java.util.Scanner;

public class CircularQueue
{
    int q[];      // array that holds the elements of the queue
    int cap;      // capacity (maximum number of elements)
    int front;    // index of the front element; -1 when the queue is empty
    int rear;     // index of the rear element; -1 when the queue is empty

    // Parameterised constructor: creates an empty queue of the given capacity
    // Parameter c: the capacity
    CircularQueue(int c)
    {
        cap = c;
        q = new int[cap];
        front = -1;
        rear = -1;
    }

    // Returns true if the queue has no element
    boolean isEmpty()
    {
        return front == -1;
    }

    // Returns true if the next position after rear (going round) is front
    boolean isFull()
    {
        return (rear + 1) % cap == front;
    }

    // Adds v at the rear.
    // Returns true if added, false if the queue is full (overflow)
    boolean add(int v)
    {
        if (isFull())
        {
            return false;
        }
        if (isEmpty())
        {
            front = 0;                 // first element goes to index 0
            rear = 0;
        }
        else
        {
            rear = (rear + 1) % cap;   // move rear one step, going back to 0 after cap - 1
        }
        q[rear] = v;
        return true;
    }

    // Removes and returns the element at the front.
    // Returns -1 if the queue is empty (the caller checks isEmpty() first, as -1 can also be a stored value)
    int remove()
    {
        if (isEmpty())
        {
            return -1;
        }
        int v = q[front];
        if (front == rear)
        {
            front = -1;                // the last element is removed: queue becomes empty
            rear = -1;
        }
        else
        {
            front = (front + 1) % cap; // move front one step, going back to 0 after cap - 1
        }
        return v;
    }

    // Displays the elements from front to rear, going round the array
    void display()
    {
        if (isEmpty())
        {
            System.out.println("The queue is empty.");
        }
        else
        {
            System.out.print("Queue (front to rear): ");
            int i = front;
            do
            {
                System.out.print(q[i] + " ");
                i = (i + 1) % cap;
            } while (i != (rear + 1) % cap);
            System.out.println();
        }
    }

    // main: reads the capacity, creates the object and runs the menu until Exit is chosen
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);   // the only Scanner of the program
        System.out.print("Enter the capacity of the queue (1 to 20): ");
        int c = sc.nextInt();
        if (c < 1 || c > 20)
        {
            System.out.println("Invalid capacity. It must be from 1 to 20.");
            return;
        }
        CircularQueue obj = new CircularQueue(c);
        int choice;
        do
        {
            System.out.println();
            System.out.println("1. Add");
            System.out.println("2. Remove");
            System.out.println("3. Display");
            System.out.println("4. Exit");
            System.out.print("Enter your choice: ");
            choice = sc.nextInt();
            switch (choice)
            {
                case 1:
                    System.out.print("Enter the element to add: ");
                    int v = sc.nextInt();
                    if (obj.add(v))
                    {
                        System.out.println("Element added: " + v);
                    }
                    else
                    {
                        System.out.println("Overflow: the queue is full.");
                    }
                    break;
                case 2:
                    if (obj.isEmpty())
                    {
                        System.out.println("Underflow: the queue is empty.");
                    }
                    else
                    {
                        System.out.println("Removed element: " + obj.remove());
                    }
                    break;
                case 3:
                    obj.display();
                    break;
                case 4:
                    System.out.println("Program ended.");
                    break;
                default:
                    System.out.println("Invalid choice. Enter 1 to 4.");
            }
        } while (choice != 4);
    }
}

Variable description table

Sample input and output

Enter the capacity of the queue (1 to 20): 3

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 1
Enter the element to add: 10
Element added: 10

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 1
Enter the element to add: 20
Element added: 20

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 1
Enter the element to add: 30
Element added: 30

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 1
Enter the element to add: 40
Overflow: the queue is full.

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 3
Queue (front to rear): 10 20 30 

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 2
Removed element: 10

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 2
Removed element: 20

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 1
Enter the element to add: 50
Element added: 50

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 1
Enter the element to add: 60
Element added: 60

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 3
Queue (front to rear): 30 50 60 

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 4
Program ended.

Enter the capacity of the queue (1 to 20): 1

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 2
Underflow: the queue is empty.

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 1
Enter the element to add: 5
Element added: 5

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 1
Enter the element to add: 6
Overflow: the queue is full.

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 3
Queue (front to rear): 5 

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 2
Removed element: 5

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 3
The queue is empty.

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 9
Invalid choice. Enter 1 to 4.

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 4
Program ended.

Enter the capacity of the queue (1 to 20): 0
Invalid capacity. It must be from 1 to 20.

Enter the capacity of the queue (1 to 20): 4

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 2
Underflow: the queue is empty.

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 3
The queue is empty.

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 1
Enter the element to add: 8
Element added: 8

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 3
Queue (front to rear): 8 

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 2
Removed element: 8

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 2
Underflow: the queue is empty.

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 4
Program ended.

Dry run

Take the first sample with capacity 3. The array is shown with _ for an empty slot.

Display: i = 2 prints 30; i = 0 prints 50; i = 1 prints 60; then i = 2 equals (rear + 1) % cap = 2, so the loop stops. The output is 30 50 60, which matches the first sample run.

Variations

1. Count variable "Write a circular queue program that keeps a count of the elements instead of testing front and rear for fullness."
2. Dequeue "Write a menu driven program for a dequeue that allows insertion and deletion at both ends."
3. Queue of names "Implement a circular queue of names using a String array."