Let's implement a circular queue in Java. A circular queue, also known as a ring buffer, is a fixed-size data structure that operates as if the end is connected to the beginning. This is particularly useful in scenarios where you want to maintain a history of the most recent 'n' elements, such as in real-time data processing or managing tasks in an operating system. Your implementation should include the following functionalities:

Initialization: The queue should be initialized with a specified capacity.
Enqueue (Insertion): Add an element to the rear of the queue. If the queue is full, the insertion should fail, and an appropriate message should be returned.
Dequeue (Deletion): Remove an element from the front of the queue. If the queue is empty, the deletion should fail, and an appropriate message should be returned.
Peek: Return the element at the front of the queue without removing it. Return null if the queue is empty.
isEmpty: Check if the queue is empty.
isFull: Check if the queue is full.
Size: Return the current number of elements in the queue.
Print Queue: Implement a method to print the current elements in the queue. This is useful for debugging and visualization.

For example, if the queue has a capacity of 5, and you enqueue elements 1, 2, 3, 4, and 5, the queue is full. If you then dequeue one element, the element 1 is removed, and you can enqueue a new element, say 6. The queue now contains 2, 3, 4, 5, and 6. Make sure your implementation handles the circular nature correctly, meaning the rear pointer should wrap around to the beginning of the array when it reaches the end, and the front pointer should wrap around similarly when dequeuing.

Provide a complete, runnable Java code solution with comments to explain the logic behind each method. Also include a simple main method demonstrating the usage of your circular queue with some enqueue and dequeue operations.

Circular Queue Implementation in Java

Naive Implementation

First, here's a straightforward implementation of a circular queue in Java. This will serve as our base, which we can then optimize.

public class CircularQueue {
    private int[] queue;
    private int head;
    private int tail;
    private int size;
    private int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.head = 0;
        this.tail = 0;
        this.size = 0;
    }

    public boolean enqueue(int data) {
        if (isFull()) {
            System.out.println("Queue is full. Cannot enqueue.");
            return false;
        }
        queue[tail] = data;
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }

    public Integer dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Cannot dequeue.");
            return null;
        }
        int data = queue[head];
        head = (head + 1) % capacity;
        size--;
        return data;
    }

    public Integer peek() {
        if (isEmpty()) {
            return null;
        }
        return queue[head];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public int size() {
        return size;
    }

    public void printQueue() {
        if (isEmpty()) {
            System.out.println("Queue is empty.");
            return;
        }
        System.out.print("Queue: ");
        int i = head;
        int count = 0;
        while (count < size) {
            System.out.print(queue[i] + " ");
            i = (i + 1) % capacity;
            count++;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        CircularQueue cq = new CircularQueue(5);
        cq.enqueue(1);
        cq.enqueue(2);
        cq.enqueue(3);
        cq.printQueue();  // Output: Queue: 1 2 3
        cq.dequeue();
        cq.printQueue();  // Output: Queue: 2 3
        cq.enqueue(4);
        cq.enqueue(5);
        cq.enqueue(6);
        cq.printQueue();  // Output: Queue: 2 3 4 5 6
        cq.enqueue(7);  // Output: Queue is full. Cannot enqueue.
        cq.printQueue(); // Output: Queue: 2 3 4 5 6
        cq.dequeue();
        cq.enqueue(7);
        cq.printQueue(); // Output: Queue: 3 4 5 6 7
    }
}

Optimized Implementation

The naive implementation is already quite efficient for basic operations. However, a slight optimization can be introduced to make the isFull check more efficient by tracking the number of elements directly, as shown in the initial implementation. There isn't a drastically different approach that would yield significantly better performance due to the fundamental nature of the circular queue.

public class CircularQueueOptimized {
    private int[] queue;
    private int head;
    private int tail;
    private int size;
    private int capacity;

    public CircularQueueOptimized(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.head = 0;
        this.tail = 0;
        this.size = 0;
    }

    public boolean enqueue(int data) {
        if (isFull()) {
            System.out.println("Queue is full. Cannot enqueue.");
            return false;
        }
        queue[tail] = data;
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }

    public Integer dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Cannot dequeue.");
            return null;
        }
        int data = queue[head];
        head = (head + 1) % capacity;
        size--;
        return data;
    }

    public Integer peek() {
        if (isEmpty()) {
            return null;
        }
        return queue[head];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public int size() {
        return size;
    }

    public void printQueue() {
        if (isEmpty()) {
            System.out.println("Queue is empty.");
            return;
        }
        System.out.print("Queue: ");
        int i = head;
        int count = 0;
        while (count < size) {
            System.out.print(queue[i] + " ");
            i = (i + 1) % capacity;
            count++;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        CircularQueueOptimized cq = new CircularQueueOptimized(5);
        cq.enqueue(1);
        cq.enqueue(2);
        cq.enqueue(3);
        cq.printQueue();
        cq.dequeue();
        cq.printQueue();
        cq.enqueue(4);
        cq.enqueue(5);
        cq.enqueue(6);
        cq.printQueue();
        cq.enqueue(7);
        cq.printQueue();
        cq.dequeue();
        cq.enqueue(7);
        cq.printQueue();
    }
}

Big(O) Run-Time Analysis

Enqueue: O(1) - Adding an element involves a fixed number of operations regardless of the queue size.
Dequeue: O(1) - Removing an element involves a fixed number of operations regardless of the queue size.
Peek: O(1) - Accessing the front element takes constant time.
isEmpty: O(1) - Checking if the queue is empty is a constant-time operation.
isFull: O(1) - Checking if the queue is full is a constant-time operation.
Size: O(1) - Getting the size of the queue is a constant-time operation.
Print Queue: O(N) - Printing the queue iterates through each element currently in the queue, where N is the number of elements in the queue.

Big(O) Space Usage Analysis

CircularQueue: O(N) - The space complexity is determined by the size of the queue, which is fixed at initialization. The queue uses an array of size N, where N is the capacity of the queue.

Edge Cases and How to Handle Them

Empty Queue:
- Scenario: Attempting to dequeue or peek from an empty queue.
- Handling: Methods dequeue and peek should check if the queue is empty and return null or an appropriate error message.
Full Queue:
- Scenario: Attempting to enqueue into a full queue.
- Handling: The enqueue method should check if the queue is full and return false or an error message.
Queue Overflow:
- Scenario: The capacity is reached and further insertions are attempted.
- Handling: Prevent insertions beyond the capacity by correctly implementing the isFull check.
Queue Underflow:
- Scenario: Attempting to dequeue more elements than available.
- Handling: Prevent dequeues when the queue is empty by correctly implementing the isEmpty check.
Zero Capacity:
- Scenario: Initializing the queue with a capacity of zero.
- Handling: Throw an IllegalArgumentException if the capacity is zero or negative.
Integer Overflow/Underflow:
- Scenario: head or tail might overflow if the queue is used for a very long time.
- Handling: While not commonly handled explicitly, using modular arithmetic % capacity inherently handles the wrap-around, preventing integer overflow issues.
Null Elements:
- Scenario: The queue is intended to store objects and null objects are enqueued.
- Handling: The implementation should allow null elements if the use case requires it, or explicitly check for null elements before enqueueing and throw an exception if nulls are not allowed.

How do you implement a circular queue in Java?