Lecture 255:- Circular Queue

A circular queue is a variant of the standard queue data structure where the last element of the queue is connected to the first element, forming a circle. This circular arrangement allows efficient use of the underlying array and eliminates the need for shifting elements during enqueue and dequeue operations.

Circular queues have the following characteristics:

1. Fixed size: Like a regular queue using an array, a circular queue also has a fixed size. Once the circular queue becomes full, it can no longer accommodate more elements.
2. Circular nature: The front and rear pointers wrap around the array in a circular fashion. When the rear pointer reaches the end of the array, it wraps around to the beginning to continue adding elements.
3. Efficient enqueue and dequeue: Since the circular queue uses a circular arrangement, the enqueue and dequeue operations are generally more efficient than those in a regular array-based queue. There is no need to shift elements during dequeue operations, and the rear pointer can wrap around to the beginning for enqueuing new elements.
4. Better memory utilization: Circular queues can provide better memory utilization compared to regular queues, especially in situations where there is a mix of enqueue and dequeue operations. The circular arrangement allows the queue to reuse space efficiently.

Here's a basic C++ implementation of a Circular Queue:

cppCopy code

#include <iostream> const int MAX_SIZE = 5; class CircularQueue { private:    int arr[MAX_SIZE];    int frontIdx;    int rearIdx; public:    CircularQueue() {        frontIdx = -1;        rearIdx = -1;    }    bool isEmpty() {        return frontIdx == -1 && rearIdx == -1;    }    bool isFull() {        return (rearIdx + 1) % MAX_SIZE == frontIdx;    }    void enqueue(int element) {        if (isFull()) {            std::cout << "Queue is full. Cannot enqueue." << std::endl;            return;        }        if (isEmpty()) {            frontIdx = 0;        }        rearIdx = (rearIdx + 1) % MAX_SIZE;        arr[rearIdx] = element;    }    void dequeue() {        if (isEmpty()) {            std::cout << "Queue is empty. Cannot dequeue." << std::endl;            return;        }        if (frontIdx == rearIdx) {            frontIdx = -1;            rearIdx = -1;        } else {            frontIdx = (frontIdx + 1) % MAX_SIZE;        }    }    int front() {        if (isEmpty()) {            std::cout << "Queue is empty." << std::endl;            return -1; // Assuming -1 is not a valid element in the queue.        }        return arr[frontIdx];    }    int size() {        if (isEmpty()) {            return 0;        }        return (rearIdx >= frontIdx) ? (rearIdx - frontIdx + 1) : (MAX_SIZE - frontIdx + rearIdx + 1);    } }; int main() {    CircularQueue queue;    queue.enqueue(10);    queue.enqueue(20);    queue.enqueue(30);    std::cout << "Front element: " << queue.front() << std::endl;    queue.dequeue();    std::cout << "Front element after dequeue: " << queue.front() << std::endl;    std::cout << "Queue size: " << queue.size() << std::endl;    return 0; }

In this implementation, we use an array to store the elements of the circular queue. The frontIdx and rearIdx pointers wrap around the array in a circular fashion using the modulo operator %. The circular nature of the queue allows for efficient enqueue and dequeue operations without the need for shifting elements. The member functions isEmpty() and isFull() check if the queue is empty or full, respectively. The enqueue() function adds an element to the rear of the queue, the dequeue() function removes the front element from the queue, and the front() function returns the front element without removing it. The size() function returns the number of elements in the queue.

In the main function, we demonstrate how to use the Circular Queue by enqueueing and dequeueing elements and checking the front element and queue size.