ISC Practicals and Theory - Linear Queue

A queue is a linear data structure in which elements are added at one end, called the rear, and removed from the other end, called the front, so the element added first is the first to be removed. This note implements a linear queue of integers using an array, with a menu to add, remove and display. This is the Classic version: a default constructor, an init method that sets the capacity, and methods that print their own messages.

Definition

A queue follows the FIFO (First In, First Out) rule. The two basic operations are:

• Add (enqueue): insert an element at the rear of the queue.
• Remove (dequeue): delete the element at the front of the queue.

When the queue is implemented with an array, two integers keep track of the ends. In this program the indexes are 0-based and front = -1 and rear = -1 mean that nothing has been added yet. The first add makes front = 0.

• Overflow: trying to add when rear == cap - 1.
• Underflow: trying to remove when the queue has no element, that is front == -1 or front > rear.

Drawback of a linear queue: rear only moves forward and front only moves forward. When an element is removed, the place it occupied is never used again. So the queue can show overflow even though there are free places at the beginning of the array. For example, with capacity 3, add 1, 2, 3 and remove 1: rear is still 2 (cap - 1), so adding 4 gives overflow although que[0] is free. A circular queue removes this drawback.

Algorithm

1. In main, read the capacity c. If it is less than 1 or more than 20, print an error message and stop.
2. Create the object obj with the default constructor Queue() (it sets cap = 0, front = -1 and rear = -1), then call obj.init(c), which sets cap, creates the array que of size cap and sets front = -1 and rear = -1.
3. Repeat the menu (1 Add, 2 Remove, 3 Display, 4 Exit) and read choice until choice is 4:
   • Choice 1: read the element v and call obj.add(v).
   • Choice 2: call obj.remove().
   • Choice 3: call obj.display().
   • Choice 4: print a message and leave the loop.
   • Any other value: print an invalid choice message and show the menu again.
4. Add (add(int v)):
   • If isFull() is true (rear == cap - 1), print the overflow message.
   • Otherwise increase rear by 1 and store v in que[rear]. If front is -1, set front = 0. Print that v was added.
5. Remove (remove()):
   • If isEmpty() is true (front == -1 or front > rear), print the underflow message.
   • Otherwise copy que[front] into v, increase front by 1 and print that v was removed.
6. Display (display()):
   • Print the values of front and rear.
   • If the queue is empty, print that it is empty.
   • Otherwise run i from front to rear and print que[i], so the front element is printed first.

A removed value is not erased from the array. It stays in its old place, but that place lies before front, so it is ignored.

Program

isEmpty and isFull test the two end conditions, add, remove and display carry out the operations and print their messages, and main runs the menu.

import java.util.Scanner;

// Class Queue: implements a linear queue of integers using an array
public class Queue
{
    int que[];    // array that stores the queue elements
    int cap;      // capacity: maximum number of elements the array can hold
    int front;    // index of the front element (-1 until the first element is added)
    int rear;     // index of the rear element (-1 when nothing has been added)

    // Default constructor: no array yet, the queue is marked empty
    Queue()
    {
        cap = 0;
        front = -1;
        rear = -1;
    }

    // Sets the capacity, creates the array and marks the queue empty
    // Parameter c: the capacity entered by the user
    void init(int c)
    {
        cap = c;
        que = new int[cap];
        front = -1;
        rear = -1;
    }

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

    // Returns true if rear is at the last index; freed front places are not reused
    boolean isFull()
    {
        return rear == cap - 1;
    }

    // Adds the value v at the rear of the queue; prints a message on overflow
    // Parameter v: the element to be added
    void add(int v)
    {
        if (isFull())
        {
            System.out.println("Queue Overflow! Cannot add " + v);
        }
        else
        {
            rear++;              // move rear to the next place
            que[rear] = v;       // store the element at the rear
            if (front == -1)
            {
                front = 0;       // first element added: front moves to index 0
            }
            System.out.println(v + " added");
        }
    }

    // Removes the element at the front and prints it; prints a message on underflow
    void remove()
    {
        if (isEmpty())
        {
            System.out.println("Queue Underflow! The queue is empty");
        }
        else
        {
            int v = que[front];  // element being removed
            front++;             // move front to the next place
            System.out.println(v + " removed");
        }
    }

    // Displays the positions of front and rear and the elements from front to rear
    void display()
    {
        System.out.println("Front = " + front + ", Rear = " + rear);
        if (isEmpty())
        {
            System.out.println("The queue is empty");
        }
        else
        {
            System.out.println("Queue (front to rear):");
            for (int i = front; i <= rear; i++)
            {
                System.out.println(que[i]);
            }
        }
    }

    // main: reads the capacity, then runs the menu until the user chooses 4
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);   // single Scanner used for all input
        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;
        }
        Queue obj = new Queue();   // object created with the default constructor
        obj.init(c);               // capacity is set by init
        int choice;                // menu choice entered by the user
        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();   // element to be added
                    obj.add(v);
                    break;
                case 2:
                    obj.remove();
                    break;
                case 3:
                    obj.display();
                    break;
                case 4:
                    System.out.println("Exiting the program");
                    break;
                default:
                    System.out.println("Invalid choice. Enter a number from 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
10 added

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

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

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

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

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

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 3
Front = 2, Rear = 2
Queue (front to rear):
30

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 4
Exiting the program

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: 1
1 added

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

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

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

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 1
Enter the element to add: 4
Queue Overflow! Cannot add 4

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 3
Front = 1, Rear = 2
Queue (front to rear):
2
3

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

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

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

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

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

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 4
Exiting the program

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

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

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 3
Front = -1, Rear = -1
The queue is empty

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

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

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 1
Enter the element to add: 7
Queue Overflow! Cannot add 7

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 3
Front = 0, Rear = 1
Queue (front to rear):
5
6

1. Add
2. Remove
3. Display
4. Exit
Enter your choice: 4
Exiting the program

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

Dry run

Take the second sample, which shows the drawback: capacity 3, add 1, add 2, add 3, remove, add 4, display, remove, remove, remove, display, invalid choice 9, exit. Places not holding a live element are shown as _.

The overflow at "Add 4" happens while que[0] is free. This matches the real run of the second sample, whose last display shows Front = 3, Rear = 2 and an empty queue.

Variations

1. Queue of characters or names "Write a program to implement a queue of characters (or names) using an array."
2. Circular queue "Implement a circular queue using an array so that the freed places at the front are reused."
3. Dequeue "Implement a dequeue (double ended queue) in which elements can be added and removed at both ends."
4. Count of elements "Add a method to count and display the number of elements present in the queue."