Introduction of Circular

Introduction​

A circular array (or circular buffer) is a linear data structure that wraps around to the beginning once it reaches the end. It is used in scenarios where we need a fixed-size buffer that can overwrite old data with new data, such as in queue operations or buffering systems.

Video Explanation​

Watch

Key Features​

• Fixed Size: The array has a fixed capacity.
• Circular Nature: When you reach the end, the next element is placed at the beginning of the array.
• Efficient Usage: Enables optimal memory usage by reusing space without reallocating the array.

Use Cases​

• Circular Queue Implementations: Useful for implementing queue structures where the oldest data gets replaced by new entries when capacity is full.
• Buffering Systems: Common in audio/video buffering or any system that needs constant data flow with limited memory.

Basic Operations​

1. Initialization: Setting up the array with a fixed size and pointers for start (front) and end (rear).
2. Insertion (Enqueue): Adding an element at the rear and updating the position circularly.
3. Deletion (Dequeue): Removing an element from the front and updating the position circularly.
4. Check Full/Empty Status: Methods to check if the array is full or empty.

Implementation Example (Python)​

Here is an example in Python to demonstrate the circular array:

class CircularArray:
    def __init__(self, size):
        self.size = size
        self.array = [None] * size
        self.front = -1
        self.rear = -1
    
    def is_empty(self):
        return self.front == -1
    
    def is_full(self):
        return (self.rear + 1) % self.size == self.front
    
    def enqueue(self, value):
        if self.is_full():
            print("The circular array is full. Cannot enqueue.")
            return
        if self.front == -1:
            self.front = 0
        self.rear = (self.rear + 1) % self.size
        self.array[self.rear] = value
        print(f"Enqueued: {value}")
    
    def dequeue(self):
        if self.is_empty():
            print("The circular array is empty. Cannot dequeue.")
            return None
        value = self.array[self.front]
        if self.front == self.rear:
            self.front = -1
            self.rear = -1
        else:
            self.front = (self.front + 1) % self.size
        print(f"Dequeued: {value}")
        return value
    
    def display(self):
        if self.is_empty():
            print("The circular array is empty.")
            return
        index = self.front
        print("Circular Array Elements: ", end="")
        while True:
            print(self.array[index], end=" ")
            if index == self.rear:
                break
            index = (index + 1) % self.size
        print()

Java Implementation​

public class CircularArray {
    private int[] array;
    private int front;
    private int rear;
    private int size;

    public CircularArray(int size) {
        this.size = size;
        array = new int[size];
        front = -1;
        rear = -1;
    }

    public boolean isEmpty() {
        return front == -1;
    }

    public boolean isFull() {
        return (rear + 1) % size == front;
    }

    public void enqueue(int value) {
        if (isFull()) {
            System.out.println("The circular array is full. Cannot enqueue.");
            return;
        }
        if (front == -1) {
            front = 0;
        }
        rear = (rear + 1) % size;
        array[rear] = value;
        System.out.println("Enqueued: " + value);
    }

    public int dequeue() {
        if (isEmpty()) {
            System.out.println("The circular array is empty. Cannot dequeue.");
            return -1;
        }
        int value = array[front];
        if (front == rear) {
            front = -1;
            rear = -1;
        } else {
            front = (front + 1) % size;
        }
        System.out.println("Dequeued: " + value);
        return value;
    }

    public void display() {
        if (isEmpty()) {
            System.out.println("The circular array is empty.");
            return;
        }
        System.out.print("Circular Array Elements: ");
        int index = front;
        while (true) {
            System.out.print(array[index] + " ");
            if (index == rear) {
                break;
            }
            index = (index + 1) % size;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        CircularArray ca = new CircularArray(5);
        ca.enqueue(10);
        ca.enqueue(20);
        ca.enqueue(30);
        ca.display();
        ca.dequeue();
        ca.display();
    }
}

C++ Implementation​

#include <iostream>
using namespace std;

class CircularArray {
private:
    int *array;
    int front, rear, size;

public:
    CircularArray(int s) {
        size = s;
        array = new int[size];
        front = -1;
        rear = -1;
    }

    ~CircularArray() {
        delete[] array;
    }

    bool isEmpty() {
        return front == -1;
    }

    bool isFull() {
        return (rear + 1) % size == front;
    }

    void enqueue(int value) {
        if (isFull()) {
            cout << "The circular array is full. Cannot enqueue." << endl;
            return;
        }
        if (front == -1) {
            front = 0;
        }
        rear = (rear + 1) % size;
        array[rear] = value;
        cout << "Enqueued: " << value << endl;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "The circular array is empty. Cannot dequeue." << endl;
            return -1;
        }
        int value = array[front];
        if (front == rear) {
            front = -1;
            rear = -1;
        } else {
            front = (front + 1) % size;
        }
        cout << "Dequeued: " << value << endl;
        return value;
    }

    void display() {
        if (isEmpty()) {
            cout << "The circular array is empty." << endl;
            return;
        }
        cout << "Circular Array Elements: ";
        int index = front;
        while (true) {
            cout << array[index] << " ";
            if (index == rear) {
                break;
            }
            index = (index + 1) % size;
        }
        cout << endl;
    }
};

int main() {
    CircularArray ca(5);
    ca.enqueue(10);
    ca.enqueue(20);
    ca.enqueue(30);
    ca.display();
    ca.dequeue();
    ca.display();
    return 0;
}

Complexity Analysis​

• Time Complexity:
  • Enqueue/Dequeue: $O(1)$ for insertion and deletion.
• Space Complexity: $O(n)$, where $n$ is the fixed size of the circular array.

Potential Issues and Solutions​

• Overflow: Can occur if elements are added without checking if the array is full.
  • Solution: Implement the is_full() method to prevent enqueueing when the array is at capacity.
• Underflow: Attempting to dequeue from an empty array.
  • Solution: Implement the is_empty() method to handle this gracefully.