641. 设计循环双端队列

难点

1. 如何设计下标循环
   1. 可以想到时钟，每个时间点都代表n个数，例如12点钟，又能代表24点钟。
   2. 为什么12点+1h是1点呢？因为1点也代表13点。
   3. 只要是数值连续的节点，都可以看作类似时钟的一个环，按节点个数取模后，无论数值多大，都会变成0，1，2，3...
2. 头指针、尾指针分别代表什么，才能写出更优雅的代码
   1. 若头尾指针初始化为0，那它们能代表我下一个value就插入在这里吗？肯定不行，不可能让头尾都在同一处插入。
   2. 那让其中一个代表下一个value在当前插入，另一个则在后一位插入。例如front代表下一个value在当前指针位置插入，rear代表下一个value插入在rear+1的位置上。
3. 如何设计判空与判满
   1. 若数组和数据容量大小一样，会出现判空为front == rear，而判满也是同样条件
   2. 为了避免条件冲突，可以让数组多一个空位，这样判满条件就为(rear + 1 + capacity) % capacity。

方法一

class MyCircularDeque {
    int[] data;
    int front = 0, rear = 0;
    int capacity = 0;
    public MyCircularDeque(int k) {
        capacity = k + 1;
        data = new int[k + 1];
    }
    
    public boolean insertFront(int value) {
        if (isFull()) return false;
        data[front] = value;
        front = (front - 1 + capacity) % capacity;
        return true;
    }
    
    public boolean insertLast(int value) {
        if (isFull()) return false;
        rear = (rear + 1) % capacity;
        data[rear] = value;
        return true;
    }
    
    public boolean deleteFront() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        return true;
    }
    
    public boolean deleteLast() {
        if (isEmpty()) return false;
        rear = (rear - 1 + capacity) % capacity;
        return true;
    }
    
    public int getFront() {
        if (isEmpty()) return -1;
        return data[(front + 1) % capacity];
    }
    
    public int getRear() {
        if (isEmpty()) return -1;
        return data[rear];
    }
    
    public boolean isEmpty() {
        return front == rear;
    }
    
    public boolean isFull() {
        return front == (rear + 1) % capacity;
    }
}

方法二（思维上简单）

可以避开方法一的难点

1. 判空和判满通过记录size来判断。
2. 将front设置为0，rear设置为k-1，它们都代表下一个value是插入到front-1或rear+1的位置上。
3. rear向右移动，front向左移动，它们过了边界后都从另一边重新开始，但方向不变。

class MyCircularDeque {
    int[] data;
    int front = 0, last = 0;
    int size = 0;
    int len = 0;
    public MyCircularDeque(int k) {
        data = new int[k];
        len = k;
        last = k - 1;
    }
    
    public boolean insertFront(int value) {
        if (isFull()) return false;
        front = front == 0 ? len - 1 : front - 1;
        size++;
        data[front] = value;
        return true;
    }
    
    public boolean insertLast(int value) {
        if (isFull()) return false;
        last = last == len - 1 ? 0 : last + 1;
        size++;
        data[last] = value;
        return true;
    }
    
    public boolean deleteFront() {
        if (isEmpty()) return false;
        front = front == len - 1 ? 0 : front + 1;
        size--;
        return true;
    }
    
    public boolean deleteLast() {
        if (isEmpty()) return false;
        last = last == 0 ? len - 1 : last - 1;
        size--;
        return true;
    }
    
    public int getFront() {
        if (isEmpty()) return -1;
        return data[front];
    }
    
    public int getRear() {
        if (isEmpty()) return -1;
        return data[last];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == len;
    }
}