// 第 8 周 – 用数组实现的简单（非循环）队列：为什么不好？
// 运行：java NaiveQueue.java
public class NaiveQueue {
    private final int[] data;
    private int front = 0, rear = -1;

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

    boolean isEmpty() { return front > rear; }

    // rear 到达数组末尾时队列就“满”了 – 即使前面还有空位！
    boolean isFull() { return rear == data.length - 1; }

    void enqueue(int x) {
        if (isFull()) throw new IllegalStateException("the queue is \"full\" (rear is at the end of the array)");
        data[++rear] = x;
    }

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

    // 修正方法 1：出队后把元素向前移动 – 但这样出队就是 O(n) 了！
    int dequeueWithShift() {
        if (isEmpty()) throw new IllegalStateException("the queue is empty");
        int x = data[front];
        for (int i = front; i < rear; i++) data[i] = data[i + 1];
        rear--;
        return x;
    }

    public static void main(String[] args) {
        NaiveQueue q = new NaiveQueue(5);
        for (int x = 1; x <= 5; x++) q.enqueue(x);
        q.dequeue();
        q.dequeue();
        System.out.println("after 2 dequeues front=" + q.front + ", rear=" + q.rear + " – 2 free slots at the beginning");
        try {
            q.enqueue(6);
        } catch (IllegalStateException e) {
            System.out.println("Error: " + e.getMessage());
        }
        System.out.println("Solution: a circular queue (CircularQueue.java), where rear wraps around.");

        NaiveQueue s = new NaiveQueue(5);
        for (int x = 1; x <= 5; x++) s.enqueue(x);
        System.out.println("\nShifting variant: dequeue = " + s.dequeueWithShift() + ", rear = " + s.rear + " (O(n) steps)");
        s.enqueue(6);
        System.out.println("Now 6 fits in: rear = " + s.rear);
    }
}