算法模板-循环双端队列

循环队列概念很早接触了 但在细节方面一直有些迷糊
正好今天的每日一题是循环队列 总结了一下
关键以下两点:
1.对于front 和 rear的定义要明确

​ font指向的是队头有效元素的位置 而rear则指向的是队尾下一个有效元素的位置 这就导致一些差异

​ 最主要的就是进行队尾插入时 要先进行赋值 q[rear] = value 而后移动rear 指针 因为根据rear指针的定义之前rear指针所指向的位置 正是此时元素应该插入的有效位置

​ 然后根据rear 定义 那么返回队尾元素时 返回应该时rear-1这个位置的元素 而并非rear
2.空出一个有效位置作为哨兵 主要是为了区分队空和队满两种状态

​ 这和rear指针的定义是紧密关联的

​ 当 (rear + 1 % capacity) == front 代表 此时队列已满 可以这样理解 rear 代表下一个元素的有效位置 即下一个元素的有效位置已经是front了那么这样就代表队满了

​ 同时根据上述定义 真正队满是 front != rear 所以队空的情况只能是 front == rear

class MyCircularDeque {
    // front 指向队列头部第1个有效数据的位置
	private int front;
    // rear指向队列尾部(即最后一个有效数据)的下一个位置
    private int rear;
    // capacity = k + 1 取最后多余的一个位置作为哨兵
    // 当 rear 指向这个位置时 代表队列已满  代入循环队列这个条件则为 : (rear + 1) % capacity == front (即rear当前所指向的位置的下一个位置就是front的位置那么就代表队列已经满了)
    // 当 rear == front时 代表队列为空
    // 队头: 插入  (font - 1 + capacity ) % capacity    删除: (front + 1 + capacity) % capacity
    // 队尾: 插入  (rear + 1 + capacity) % capacity     删除: (rear - 1 + capacity) % capacity
    private int capacity;

    private int [] q;

    public MyCircularDeque(int k) {
        capacity = k + 1;
        front = 0;
        rear = 0;
        q = new int[capacity];
    }

    public boolean insertFront(int value) {
        if(isFull() == true )
            return false;
        front = (front - 1 + capacity) % capacity;
        q[front] = value;
        return true;
    }

    public boolean insertLast(int value) {
        if(isFull() == true)
            return false;
        // 这里要注意要先在队尾插入 始终记住 rear指向的是下一个有效位置
        q[rear] = value;
        rear = (rear + 1 + capacity)%capacity;
        return true;
    }

    public boolean deleteFront() {
        if(isEmpty() == true)
            return false;
        front = (front + 1 + capacity) % capacity;
        return true;
    }

    public boolean deleteLast() {
        if(isEmpty() == true)
            return false;
        rear = (rear - 1 + capacity) % capacity;
        return true;
    }

    public int getFront() {
        if(isEmpty() == true)
            return  -1;
        return q[front];
    }

    public int getRear() {
        if (isEmpty() == true)
            return  -1;
        // 这里要注意下 因为rear的定义是指向下一个有效位置 
        // 所以应该返回rear的上一个位置 又因为循环队列所以要注意取模
        return q[(rear - 1 + capacity) % capacity];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (rear + 1) % capacity  == front;
    }
}