Circular Queue: Its Operations enQueue and deQueue

A Circular Queue is a type of linear data structure that works on the FIFO (First In, First Out) principle. It is called circular because the last position in the queue is connected back to the first position, forming a circle. This helps to use memory space efficiently, as when the queue seems full but has empty space at the front, new elements can still be added there.

The basic operations of a circular queue are:

1. enQueue (Insertion): Adds a new element at the rear of the queue. If the rear reaches the end of the array, it wraps around to the beginning if space is available.
2. deQueue (Deletion): Removes an element from the front of the queue. After deletion, the front moves forward, and if it reaches the end, it wraps around to the beginning.

Circular queues are widely used in situations like CPU scheduling, buffer management, and resource sharing, where efficient use of storage and continuous processing is important.

Why Circular queue?

A Circular Queue is used to overcome the limitation of a normal queue. In a normal queue, once the rear reaches the end of the queue, we cannot insert new elements even if there is empty space at the front. This leads to wasted memory. To solve this problem, the circular queue connects the end of the queue back to the front, forming a circle so that the free spaces can be reused. The front shows the first element of the queue, and the rear shows the last element where new data will be added. This makes the circular queue more efficient in using memory.

Operations on Circular Queue

The following are the operations that can be performed on a circular queue:

• enQueue(value)
• deQueue()

enQueue(value)

This function is used to insert an item into the queue. The new item is always added at the rear end if there is space available in the queue.

There are two situations where space is available:

1. If rear is not at the last position, then increase rear using (rear + 1) % maxsize and insert the new item at the rear end.
2. If rear is at the last position but front is not at the first position, it means the queue is not full. In this case, set rear to 0 and insert the new item there.

There are two situations when an item cannot be inserted because the queue is full:

1. When front is at the first position and rear is at the last position.
2. When front is right after rear (front = rear + 1).

This way, the circular queue makes sure elements are only inserted when there is space.

Steps to perform Enqueue Operation

enQueue() is a function used to insert an element into a circular queue. In a circular queue, the new element is always added at the rear position. The enQueue() function takes one integer value as a parameter and inserts that value into the circular queue. Below are the steps to insert an element into the circular queue:

Algorithm to perform enqueue operation in a circular queue

step 1: Check IF FRONT == 0 and REAR == SIZE – 1 or FRONT == REAR + 1 Then Display “Queue is Overflow”
step 2: IF FRONT = -1 and REAR = -1 then SET FRONT = REAR = 0
step 3: Else If rear != SIZE – 1 then set REAR = REAR + 1 goto step 5
step 4: Else If front != 0 and rear = SIZE – 1 then set REAR=0
step 5: Set QUEUE[REAR] = ITEM
step 6: Print: ITEM inserted
step 7: Exit

deQueue()

deQueue() is a function used to remove an element from a circular queue. In a circular queue, the element is always removed from the front position. The deQueue() function does not take any value as a parameter; it simply removes the element at the front of the queue.

There are two situations where an element can be removed:

1. If front is not at the last position, then remove the element at the front and increase front using (front + 1) % maxsize.
2. If front is at the last position, remove the element and set front to 0 to continue the circular process.

There is one situation when an element cannot be removed:

• If the queue is empty (front = -1 or front has crossed rear), no element can be removed.

This way, the circular queue ensures that elements are removed only when the queue is not empty.

Steps to perform Dequeue Operation

• If front = –1, then there are no elements in the queue. So, an underflow condition will be reported.
• If the queue is not empty and front = rear, then after deleting the element at the front the queue becomes empty and the front and rear are set to –1.
• If the queue is not empty and front = MAX–1, then after deleting the element at the front, the front is set to 0.

Algorithm to perform dequeue operation in a circular queue

Step 1: If FRONT = -1 then Display “Queue is Underflow” and Goto step 5
Step 2: Print value QUEUE[FRONT]
Step 3: If REAR == FRONT then set FRONT = -1 and REAR = -1
Step 4: Else If FRONT == SIZE-1 then FRONT = 0 else FRONT = FRONT + 1
Step 5: Exit

C Program to insert the element in circular queue

#include <stdio.h>
#include <stdlib.h>

int cqueue[5];
int front = -1, rear = -1, n=5;

void enqueue(int val) {
    if ((front == 0 && rear == n-1) || (front == rear+1)) {
        printf("Queue Overflow \n");
        return;
    }
    if (front == -1) {
        front = 0;
        rear = 0;
    } else {
        if (rear == n - 1)
            rear = 0;
        else
            rear = rear + 1;
    }
    cqueue[rear] = val;
}

void display() {
    int f = front, r = rear;
    if (front == -1) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements are :\n");
    if (f <= r) {
        while (f <= r) {
            printf("%d ", cqueue[f]);
            f++;
        }
    } else {
        while (f <= n - 1) {
            printf("%d ", cqueue[f]);
            f++;
        }
        f = 0;
        while (f <= r) {
            printf("%d ", cqueue[f]);
            f++;
        }
    }
    printf("\n");
}  

int main() { // Use int main for proper standard compliance
    int value;
    int choice;
    do {
        printf("\n1. Add value to the list");
        printf("\n2. Traverse/View List");
        printf("\n3. Exit");
        printf("\nPlease enter your choice: ");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                printf("Input for insertion: ");
                scanf("%d", &value);
                enqueue(value);
                break;          
            case 2:
                display();
                break;
            case 3:
                printf("Exiting the program.\n");
                exit(0); // Properly exits the program
            default:
                printf("Invalid choice\n");
        }
    } while(choice != 3); // Correctly use the condition to exit loop
    
    return 0; // Return statement for int main
}

Output

1. Add value to the list
2. Traverse/View List
3. Exit
Please enter your choice: 1
Input for insertion: 4

1. Add value to the list
2. Traverse/View List
3. Exit
Please enter your choice: 1
Input for insertion: 5

1. Add value to the list
2. Traverse/View List
3. Exit
Please enter your choice: 1
Input for insertion: 7

1. Add value to the list
2. Traverse/View List
3. Exit
Please enter your choice: 2
Queue elements are :
4 5 7 

1. Add value to the list
2. Traverse/View List
3. Exit
Please enter your choice: 3
Exiting the program.

Explanations

Global Variables

• cqueue[5]: This array represents the Circular Queue with a capacity of 5 elements.
• front and rear: These pointers (indexes, actually) keep track of the first element and the last element in the queue, respectively. Initially, they are set to -1 to indicate that the queue is empty.
• n=5: This is the maximum size of the queue, set to 5 according to the size of cqueue.

Functions

void enqueue(int val)

This function adds a new element, val, to the queue.

• It first checks if the queue is full. The queue is considered full if rear is just before front (in a circular manner), or if rear is at the end (n-1) and front is at the beginning (0). If the queue is full, it prints a message and exits this function.
• If front is -1, it means the queue is empty, so it sets front and rear to 0, indicating the first element is being added.
• It then places the new value in the position pointed to by rear and updates rear accordingly. If rear has reached the end of the queue, it wraps around to 0; otherwise, it just moves to the next position.
• The value is then stored in the queue at the rear position.

void display()

This function shows the current elements in the queue.

• It checks if the queue is empty (front == -1). If so, it prints a message and returns.
• It then prints all elements from front to rear. If front is less than or equal to rear, it prints elements in a straightforward manner. If front is greater than rear, it means the queue is wrapped around, so it first prints from front to the end of the array, and then from the beginning of the array to rear.

The main Function

• This is the entry point of the program. It presents a menu to the user with options to add a value to the queue (enqueue), display the queue, or exit the program.
• The user’s choice is read into the choice variable, and a switch statement is used to execute the appropriate action based on the choice.
• If the user selects to enqueue, they are prompted to enter a value, which is then added to the queue using the enqueue function.
• If the user chooses to display the queue, the display function is called.
• The program exits if the user selects the exit option.
• The loop continues until the user chooses to exit (choice != 3).

Time & Space Complexity

Time Complexity

Space Complexity