C++ Program to Implement a Circular Queue Using Arrays

A circular queue is a type of queue in which the last position is connected back to the first position to make a circle. It operates on a First In First Out (FIFO) principle, similar to a regular queue, but allows for more efficient use of space by reusing the positions of dequeued elements. This article will guide you through the implementation of a circular queue using arrays in C++, including multiple examples to demonstrate various operations and their outputs.

Table of Contents

Prerequisites

Before diving into the implementation, you should have:

Basic understanding of C++ programming.
Familiarity with arrays.
Knowledge of queue operations.

With these prerequisites, you will be able to grasp the concepts and code implementations discussed here.

1. Circular Queue Implementation Using Arrays

1.1 Circular Queue Structure and Initialization

Let’s start by defining the structure of a circular queue and initializing it.

C++

#include <iostream>
#define MAX_SIZE 5

class CircularQueue {
public:
    CircularQueue() : front(-1), rear(-1) {}

    void enqueue(int data) {
        if ((front == 0 && rear == MAX_SIZE - 1) || (rear == (front - 1) % (MAX_SIZE - 1))) {
            std::cout << "Queue is full" << std::endl;
            return;
        } else if (front == -1) {
            front = rear = 0;
        } else if (rear == MAX_SIZE - 1 && front != 0) {
            rear = 0;
        } else {
            rear++;
        }
        queue[rear] = data;
    }

    void dequeue() {
        if (front == -1) {
            std::cout << "Queue is empty" << std::endl;
            return;
        }
        int data = queue[front];
        queue[front] = -1;
        if (front == rear) {
            front = rear = -1;
        } else if (front == MAX_SIZE - 1) {
            front = 0;
        } else {
            front++;
        }
    }

    void display() {
        if (front == -1) {
            std::cout << "Queue is empty" << std::endl;
            return;
        }
        std::cout << "Circular Queue: ";
        if (rear >= front) {
            for (int i = front; i <= rear; i++) {
                std::cout << queue[i] << " ";
            }
        } else {
            for (int i = front; i < MAX_SIZE; i++) {
                std::cout << queue[i] << " ";
            }
            for (int i = 0; i <= rear; i++) {
                std::cout << queue[i] << " ";
            }
        }
        std::cout << std::endl;
    }

private:
    int queue[MAX_SIZE];
    int front, rear;
};

int main() {
    CircularQueue cq;
    cq.enqueue(10);
    cq.enqueue(20);
    cq.enqueue(30);
    cq.enqueue(40);
    cq.enqueue(50);

    std::cout << "Initial Circular Queue: ";
    cq.display();

    return 0;
}

1.2 Output Explanation

In this example, the circular queue is structured as follows:

C++

Circular Queue: 10 20 30 40 50

The output will display: Initial Circular Queue: 10 20 30 40 50

2. Advanced Circular Queue Operations

2.1 Enqueue and Dequeue Operations

Let’s demonstrate the enqueue and dequeue operations with more details.

C++

int main() {
    CircularQueue cq;
    cq.enqueue(10);
    cq.enqueue(20);
    cq.enqueue(30);
    cq.enqueue(40);
    cq.enqueue(50);

    std::cout << "Circular Queue after enqueuing 10, 20, 30, 40, 50: ";
    cq.display();

    cq.dequeue();
    cq.dequeue();
    std::cout << "Circular Queue after dequeuing two elements: ";
    cq.display();

    cq.enqueue(60);
    cq.enqueue(70);
    std::cout << "Circular Queue after enqueuing 60, 70: ";
    cq.display();

    return 0;
}

2.2 Output Explanation

In this example, the circular queue undergoes the following transformations:

After enqueuing 10, 20, 30, 40, 50:Circular Queue: 10 20 30 40 50 The output will display: Circular Queue after enqueuing 10, 20, 30, 40, 50: 10 20 30 40 50
After dequeuing two elements:Circular Queue: 30 40 50 The output will display: Circular Queue after dequeuing two elements: 30 40 50
After enqueuing 60, 70:Circular Queue: 30 40 50 60 70 The output will display: Circular Queue after enqueuing 60, 70: 30 40 50 60 70

3. Handling Edge Cases

3.1 Full and Empty Queue

Let’s handle the edge cases where the queue is full or empty.

C++

int main() {
    CircularQueue cq;

    cq.dequeue();  // Attempting to dequeue from an empty queue

    cq.enqueue(10);
    cq.enqueue(20);
    cq.enqueue(30);
    cq.enqueue(40);
    cq.enqueue(50);
    cq.enqueue(60);  // Attempting to enqueue in a full queue

    cq.display();

    return 0;
}

3.2 Output Explanation

In this example, attempting to dequeue from an empty queue and enqueue in a full queue will produce the following output:

C++

Queue is empty
Queue is full
Circular Queue: 10 20 30 40 50

This ensures that the program handles edge cases gracefully without crashing.

Conclusion

A C++ program to implement a circular queue using arrays involves defining the queue structure and implementing various operations such as enqueue, dequeue, and display. This article provided a detailed implementation of these operations along with multiple examples to illustrate their functionality. Circular queues are efficient data structures that make optimal use of space by reusing positions