// Week 8 – Circular queue (ring buffer) with an array
// Run: java CircularQueue.java
public class CircularQueue {
    private final int[] data;
    private int front = 0; // index of the first element
    private int rear = -1; // index of the last element
    private int count = 0; // number of elements – this decides empty / full

    CircularQueue(int capacity) { data = new int[capacity]; }

    boolean isEmpty() { return count == 0; }
    boolean isFull() { return count == data.length; }

    // Insertion at the rear – O(1)
    //   Pseudocode:  If IsFull then ERROR ; rear ← (rear + 1) mod n ; T[rear] ← x ; count ← count + 1
    void enqueue(int x) {
        if (isFull()) throw new IllegalStateException("the queue is full");
        rear = (rear + 1) % data.length; // wrapping around at the end of the array
        data[rear] = x;
        count++;
    }

    // Removal from the front – O(1)
    //   Pseudocode:  If IsEmpty then ERROR ; x ← T[front] ; front ← (front + 1) mod n ; count ← count − 1
    int dequeue() {
        if (isEmpty()) throw new IllegalStateException("the queue is empty");
        int x = data[front];
        front = (front + 1) % data.length;
        count--;
        return x;
    }

    int peek() {
        if (isEmpty()) throw new IllegalStateException("the queue is empty");
        return data[front];
    }

    public String toString() {
        StringBuilder sb = new StringBuilder("[front] ");
        for (int i = 0; i < count; i++) sb.append(data[(front + i) % data.length]).append(' ');
        return sb.append("[rear]  (front=" + front + ", rear=" + rear + ", count=" + count + ")").toString();
    }

    public static void main(String[] args) {
        CircularQueue q = new CircularQueue(5);
        for (int x = 1; x <= 5; x++) q.enqueue(x * 10);
        System.out.println("5 × enqueue:  " + q);
        try {
            q.enqueue(60);
        } catch (IllegalStateException e) {
            System.out.println("Error: " + e.getMessage());
        }
        System.out.println("dequeue() = " + q.dequeue() + ", dequeue() = " + q.dequeue());
        System.out.println("2 × dequeue:  " + q);
        q.enqueue(60);
        q.enqueue(70); // rear wraps around to the beginning of the array
        System.out.println("2 × enqueue:  " + q);

        System.out.print("emptying (FIFO order): ");
        while (!q.isEmpty()) System.out.print(q.dequeue() + " ");
        System.out.println();

        // Built-in queue: ArrayDeque (circular array) or LinkedList
        java.util.Queue<String> jq = new java.util.ArrayDeque<>();
        jq.offer("Li");
        jq.offer("Wang");
        jq.offer("Chen");
        System.out.println("Queue: peek = " + jq.peek() + ", poll = " + jq.poll() + ", remaining = " + jq);
    }
}