设计循环双端队列

题目描述

设计实现双端队列。

实现 MyCircularDeque 类:

• MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
• boolean insertFront(int value)：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
• boolean insertLast(int value) ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
• boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
• boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
• int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
• int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
• boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false 。
• boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。

代码

1. head 前插索引指向当前位，tail 尾插索引指向待插位
2. 队列初始化大小使用 k+1，方便进行判空和判满

class MyCircularDeque {
    int head;
    int tail;
    int[] elem;

    public MyCircularDeque(int k) {
        elem = new int[k + 1];
    }

    public boolean insertFront(int value) {
            if(!this.isFull()){
                elem[head = (head - 1 + elem.length) % elem.length] = value;
                return true;
            }
            return false;
        }

    public boolean insertLast(int value) {
        if(!this.isFull()){
            elem[tail] = value;
            tail = (tail + 1) % elem.length;
            return true;
        }
        return false;
    }

    public boolean deleteFront() {
        if(!this.isEmpty()){
            head = (head + 1) % elem.length;
            return true;
        }
        return false;
    }

    public boolean deleteLast() {
        if(!this.isEmpty()){
            tail = (tail - 1 + elem.length) % elem.length;
            return true;
        }
        return false;
    }

    public int getFront() {
        if(!this.isEmpty()){
            return this.elem[head];
        }
        return -1;
    }

    public int getRear() {
        if(!this.isEmpty()){
            return this.elem[(tail - 1 + elem.length) % elem.length];
        }
        return -1;
    }

    public boolean isEmpty() {
        return head == tail;
    }

    public boolean isFull() {
        return (tail + 1) % elem.length == head;
    }
}