Circular Queue: Its Operations enQueue and deQueue

by

Circular Queue is a linear data structure that follows FIFO (First In First Out) principle. FIFO means item that inserted first in queue will be taken out first.

Why Circular queue?

There was a limitation in normal Queue that if rear reaches at the end of size of queue and there are some space left in front of queue which cannot be utilized. So, to overcome such limitations the concept of the circular queue has come.

Front: Front is used to get front item from the Queue.

Rear: Rear is used to get rear item from the Queue.

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 in the Queue. The new item will be inserted from the rear only if there is some space available in queue.

There are two scenarios in which queue have some space:

  • If rear != max – 1, then rear will be incremented to mod(maxsize) and the new value will be inserted at the rear end of the queue.
  • If front != 0 and rear = max – 1, it means that the queue is not full, then set the value of rear to 0 and insert the new element there.

There are two cases in which the element cannot be inserted:

  • When front ==0 && rear = max-1, which means that front is at the first position of the Queue and rear is at the last position of the Queue.
  • if front== rear + 1; display Queue is full.

Steps to perform Enqueue Operation

enQueue() is a function which is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at rear position. The enQueue() function takes one integer value as parameter and inserts that value into the circular queue. Below are the following 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()

This function is used to delete an item from the Queue. Item will be delete from the front of a Queue only if there is atleast one item in queue.

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

 deQueue()
 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).