C Program to Implement Circular Queue

Introduction

A circular queue is a linear data structure that follows the First In, First Out (FIFO) principle, but unlike a standard queue, the last position is connected back to the first position to make a circle. This allows efficient use of space by reusing previously used slots once they are freed. The circular queue avoids the "wasting space" issue of the linear queue by connecting the rear end back to the front.

Example:

• Enqueue Operation: Adding elements [10, 20, 30, 40] to the queue.
• Dequeue Operation: Removing elements from the front and allowing the rear to wrap around to the front.

Problem Statement

Create a C program that:

• Implements a circular queue using an array.
• Performs queue operations such as enqueue, dequeue, and peek.
• Displays the queue contents after each operation.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions.
2. Define Constants and Global Variables: Define the maximum size of the queue, the queue array, and variables to keep track of the front and rear of the queue.
3. Implement the Circular Queue Operations:

• Enqueue: Add an element to the rear of the queue.
• Dequeue: Remove and return the front element from the queue.
• Peek/Front: Return the front element without removing it.
• IsEmpty: Check if the queue is empty.
• IsFull: Check if the queue is full.

4. Create a Main Function: In the main() function, allow the user to perform queue operations interactively.

C Program to Implement Circular Queue

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

// Step 2: Define Constants and Global Variables
#define MAX 5  // Maximum size of the circular queue

int queue[MAX];
int front = -1;  // Initialize front to -1 to indicate an empty queue
int rear = -1;   // Initialize rear to -1 to indicate an empty queue

// Function to check if the queue is empty
int isEmpty() {
    return front == -1;
}

// Function to check if the queue is full
int isFull() {
    return (rear + 1) % MAX == front;
}

// Function to add an element to the queue (enqueue)
void enqueue(int value) {
    if (isFull()) {
        printf("Queue overflow! Cannot enqueue %d.\n", value);
        return;
    }
    if (isEmpty()) {
        front = 0;
    }
    rear = (rear + 1) % MAX;
    queue[rear] = value;
    printf("%d enqueued to the queue.\n", value);
}

// Function to remove and return the front element from the queue (dequeue)
int dequeue() {
    if (isEmpty()) {
        printf("Queue underflow! Cannot dequeue from an empty queue.\n");
        return -1;  // Return -1 to indicate queue underflow
    }
    int dequeued_value = queue[front];
    if (front == rear) {
        // The queue is now empty after dequeuing the last element
        front = rear = -1;
    } else {
        front = (front + 1) % MAX;
    }
    return dequeued_value;
}

// Function to return the front element of the queue without removing it
int peek() {
    if (isEmpty()) {
        printf("Queue is empty! Cannot peek.\n");
        return -1;  // Return -1 to indicate an empty queue
    }
    return queue[front];
}

// Function to display the queue elements
void display() {
    if (isEmpty()) {
        printf("Queue is empty!\n");
        return;
    }

    printf("Queue elements: ");
    int i = front;
    while (1) {
        printf("%d ", queue[i]);
        if (i == rear) {
            break;
        }
        i = (i + 1) % MAX;
    }
    printf("\n");
}

int main() {
    int choice, value;

    while (1) {
        // Step 4: Provide a Menu for Queue Operations
        printf("\nCircular Queue Operations Menu:\n");
        printf("1. Enqueue\n");
        printf("2. Dequeue\n");
        printf("3. Peek\n");
        printf("4. Display\n");
        printf("5. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter value to enqueue: ");
                scanf("%d", &value);
                enqueue(value);
                break;
            case 2:
                value = dequeue();
                if (value != -1) {
                    printf("Dequeued value: %d\n", value);
                }
                break;
            case 3:
                value = peek();
                if (value != -1) {
                    printf("Front value: %d\n", value);
                }
                break;
            case 4:
                display();
                break;
            case 5:
                exit(0);
            default:
                printf("Invalid choice! Please enter a valid option.\n");
        }
    }

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Step 2: Define Constants and Global Variables

• The maximum size of the circular queue (MAX) is defined as 5.
• The queue is implemented as an array queue[MAX], and the variables front and rear are initialized to -1 to indicate that the queue is initially empty.

Function to Check if the Queue is Empty

• The isEmpty function returns 1 if front is -1, indicating the queue is empty, otherwise returns 0.

Function to Check if the Queue is Full

• The isFull function returns 1 if the next position after rear is equal to front, indicating the queue is full, otherwise returns 0.

Function to Enqueue an Element into the Queue

• The enqueue function adds an element to the rear of the queue if the queue is not full. If the queue was initially empty (front == -1), front is set to 0. The rear is updated using (rear + 1) % MAX, and the element is added to queue[rear].

Function to Dequeue an Element from the Queue

• The dequeue function removes and returns the front element from the queue if the queue is not empty. If the queue has only one element, both front and rear are reset to -1 after dequeuing. Otherwise, front is updated using (front + 1) % MAX.

Function to Peek the Front Element of the Queue

• The peek function returns the front element of the queue without removing it. It is useful for viewing the element at the front of the queue.

Function to Display the Queue Elements

• The display function prints all the elements in the queue from front to rear. The loop runs until it reaches the rear of the queue, wrapping around if necessary using (i + 1) % MAX.

Main Function

• The main function provides a menu-driven interface allowing the user to perform various queue operations interactively.

Output Example

Example Output:

Circular Queue Operations Menu:
1. Enqueue
2. Dequeue
3. Peek
4. Display
5. Exit
Enter your choice: 1
Enter value to enqueue: 10
10 enqueued to the queue.

Circular Queue Operations Menu:
1. Enqueue
2. Dequeue
3. Peek
4. Display
5. Exit
Enter your choice: 1
Enter value to enqueue: 20
20 enqueued to the queue.

Circular Queue Operations Menu:
1. Enqueue
2. Dequeue
3. Peek
4. Display
5. Exit
Enter your choice: 4
Queue elements: 10 20 

Circular Queue Operations Menu:
1. Enqueue
2. Dequeue
3. Peek
4. Display
5. Exit
Enter your choice: 2
Dequeued value: 10

Conclusion

This C program demonstrates how to implement a circular queue using an array. It includes basic queue operations such as enqueue, dequeue, peek, and display, making it a useful example for beginners learning about data structures in C programming.