ISC Practicals and Theory - Circular Queue

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 is the classic ISC form: a default constructor, an init method that sets the capacity, void methods that print their own messages, and a menu in main to add, remove and display elements.

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 simple array queue, the slots at the start of the array are wasted once elements are removed. In a circular queue the array is treated as a ring: after index cap - 1 the next index is 0. This is done 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 the position after rear is front, that is (rear + 1) % cap == front. All cap slots can be used.
• When the last element is removed (front == rear), both are set back to -1.

Capacity: it must be from 1 to 20. Any other value is rejected with a message.

Algorithm

1. In main, create the object obj (the default constructor sets front = rear = -1). Read the capacity c. If c < 1 or c > 20, print an error message and stop. Otherwise call obj.init(c), which creates the array q of size c.
2. Repeat the menu until the choice is 4: print the menu, read choice and call the matching method. For any other number print Invalid choice. Enter 1 to 4.
3. add(): read v.
   • If isFull() is true, print an overflow message.
   • Otherwise, if the queue is empty, set front = 0 and rear = 0; else set rear = (rear + 1) % cap.
   • Store v in q[rear] and print a message.
4. remove():
   • If isEmpty() is true, print an underflow message.
   • Otherwise take v = q[front]. If front == rear it was the last element, so set front = -1 and rear = -1; else set front = (front + 1) % cap. Print v.
5. 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. This do-while loop also works when the queue is full, and when rear is before front after wrap-around.
6. When choice 4 is entered, print Program ended. and the loop stops.

Program

init creates the array, isEmpty and isFull test the two limits, add and remove change rear and front, display prints from front to rear going round, and main runs the menu. One Scanner is created as a data member and shared by main and add, because two Scanners on the same input can lose typed data.

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
    Scanner sc = new Scanner(System.in);   // the only Scanner of the program, shared by all methods

    // Default constructor: sets the data members to empty values
    CircularQueue()
    {
        q = null;
        cap = 0;
        front = -1;
        rear = -1;
    }

    // Creates the array of the given capacity and marks the queue empty
    // Parameter c: the capacity
    void init(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;
    }

    // Reads an element and adds it at the rear; prints a message
    void add()
    {
        System.out.print("Enter the element to add: ");
        int v = sc.nextInt();
        if (isFull())
        {
            System.out.println("Overflow: the queue is full.");
        }
        else
        {
            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;
            System.out.println("Element added: " + v);
        }
    }

    // Removes the element at the front and prints it; prints a message if empty
    void remove()
    {
        if (isEmpty())
        {
            System.out.println("Underflow: the queue is empty.");
        }
        else
        {
            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
            }
            System.out.println("Removed element: " + 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, then runs the menu until Exit is chosen
    public static void main(String[] args)
    {
        CircularQueue obj = new CircularQueue();
        System.out.print("Enter the capacity of the queue (1 to 20): ");
        int c = obj.sc.nextInt();
        if (c < 1 || c > 20)
        {
            System.out.println("Invalid capacity. It must be from 1 to 20.");
            return;
        }
        obj.init(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 = obj.sc.nextInt();
            switch (choice)
            {
                case 1: obj.add(); break;
                case 2: 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): 25
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 = (2 + 1) % 3 = 0 prints 50; i = 1 prints 60; then i = 2, which 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. Free slots "Modify the circular queue program to also display the number of free slots after every operation."
3. Dequeue "Write a menu driven program for a dequeue that allows insertion and deletion at both ends."
4. Queue of names "Implement a circular queue of names using a String array."