// 第 8 周 – 用循环数组实现的双端队列（deque）
// 运行：java CircularDeque.java
public class CircularDeque {
    private final int[] data;
    private int front = 0, count = 0;

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

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

    private int index(int i) { return (front + i) % data.length; } // 第 i 个元素的位置

    // 在队头插入：front 后退一位（绕回）– O(1)
    void addFirst(int x) {
        if (isFull()) throw new IllegalStateException("full");
        front = (front - 1 + data.length) % data.length; // 这样 -1 mod n 才能正确地得到 n-1
        data[front] = x;
        count++;
    }

    void addLast(int x) {
        if (isFull()) throw new IllegalStateException("full");
        data[index(count)] = x;
        count++;
    }

    int removeFirst() {
        if (isEmpty()) throw new IllegalStateException("empty");
        int x = data[front];
        front = (front + 1) % data.length;
        count--;
        return x;
    }

    int removeLast() {
        if (isEmpty()) throw new IllegalStateException("empty");
        int x = data[index(count - 1)];
        count--;
        return x;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < count; i++) sb.append(i > 0 ? " " : "").append(data[index(i)]);
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        CircularDeque d = new CircularDeque(6);
        d.addLast(3);
        d.addLast(4);
        d.addFirst(2);
        d.addFirst(1);
        d.addLast(5);
        System.out.println("deque: " + d);
        System.out.println("removeFirst = " + d.removeFirst() + ", removeLast = " + d.removeLast() + " -> " + d);

        // 栈和队列合二为一：只用一端是栈，用两端是队列
        java.util.ArrayDeque<Character> dq = new java.util.ArrayDeque<>();
        for (char c : "racecar".toCharArray()) dq.addLast(c);
        boolean pal = true;
        while (dq.size() > 1) if (dq.pollFirst() != dq.pollLast()) pal = false;
        System.out.println("\"racecar\" is a palindrome (with a deque)? " + pal);
    }
}