JDK的deque接口

JDK1.6提供了双向队列的接口，它规定了一种双向队列的行为例如：头部插入/删除、尾部插入/删除。如果我们仅仅看deque接口的话（不看collection继承下来的方法），你会发现提供的方法都是基于头尾的。
这个特点可以直接用于实现栈与队列。
Deque接口继承自queue接口，特提供了更多指明方向的方法例如offerFirst、offerLast，如果仅使用Queue接口去接收一个实现类（如LinkedList），那么默认的先进先出就是尾插头删，而deque既然是双端队列接口，那么不论是头还是尾都可以实现先进先出的特点。

deque有四个常用实现类：
【1】linkedList，基于双向队列实现
【2】arrayDeque，基于循环数组实现
【3】concurrentLinkedDeque，线程安全，非阻塞
【4】linkedBlockingDeque，线程安全，空队列获取元素时阻塞

实现循环双端队列

力扣地址
我们要设计一个循环的双端队列，有以下特点：
【1】满了就不能再插入了。（不是无限插入的，有上限值）
【2】空了不能够获得。
（上面直接return false，如果放在阻塞队列则应该被阻塞直到队列不满或不空）

基于双向链表实现

其实本题更适合使用循环数组实现，双向链表实现比较简单，就是常规的双向链表，并且通过首尾指针进行一些查询、删除、插入操作。（注意:本题的容量是限定死的，不是无限插入的）

    class Node{
        Node pre;
        Node next;
        int val;
        public Node(int val) {
            this.val = val;
        }
    }

如果使用链表实现，其实问题退化为了设计链表，并实现一些头插尾插的方法，都是O（1），但是需要额外维护链表的成员头结点和尾结点。

    int size;
    int cap;
    Node head;
    Node tail;

    public MyCircularDeque(int k) {
        cap=k;
        head=new Node(-1);
        tail=new Node(-1);
        head.next=tail;
        tail.pre=head;
    }

    public boolean insertFront(int value) {
        if(isFull())return false;
        Node node = new Node(value);
        node.next=head.next;
        head.next.pre=node;
        head.next=node;
        node.pre=head;
        size++;
        return true;
    }

拿到首元素，然后进行插入操作，需要同时维护next和pre的关系。其中insertLast和insertFront代码基本就是把头结点换成尾结点，不再额外展示。

    public boolean deleteFront() {
        if(isEmpty())return false;
        head.next=head.next.next;
        head.next.pre=head;
        size--;
        return true;
    }

删除操作，无非就是通过哨兵节点拿到首节点或尾结点，然后转接相应的pre和next关系

    public int getFront() {
        if(isEmpty())return -1;
        return head.next.val;
    }

    public int getRear() {
        if(isEmpty())return -1;
        return tail.pre.val;
    }

    public boolean isEmpty() {
        return size==0;
    }

    public boolean isFull() {
        return size == cap;
    }

本题更令人满意的实现还是基于循环数组。

基于循环数组实现

因为我们要实现的是双端队列，不管插入还是删除操作，都仅发生在队列的首部或者尾部，因此使用数组实现效率甚至更高（因为不需要创建和删除节点对象，仅需要修改某个位置的字面量）。
比起基于链表的实现中，通过修改链表节点的指针，使得被删除节点对象称为“不可达对象”，数组更新像是通过移动指针实现的逻辑删除。

    private int capacity;
    private int[] arr;
    private int front;
    private int rear;

底层使用固定大小的数组，并且使用双指针限定数组的访问范围，[front…rear]之间就是不可用的位置，而[rear…front]之间则是剩余的位置。

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

这里k+1是一个核心，这里通过使用一个哨兵位来区分空和满两种状态。

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

我们使用两个指针重合，用于判断队列为空。
注意两个指针移动的规则：
【1】初始时，两个指针重合
【2】当插入一个元素，arr[rear++]=x 。 也就是说插入完毕后，rear指针会指向队尾（即最新插入的元素）元素的下一个位置。
【3】当删除一个元素时则是front++，因此front总是指向队首（最晚插入的元素）（除了初始阶段）

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

因此，如果当前状态是满，那么rear此时的位置便是哨兵位，加一取模后将与front指针重合再次（这也是为什么要单独设置哨兵位的原因）

本题的核心就是通过设置哨兵位区别满和空两种状态，其他的方法的实现都很简单。（注意，循环数组实现的循环队列中，每个位置都是相对的，包括哨兵位）

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

从front删除对应front++，那么从front插入就是对应(front - 1 + capacity) % capacity对应的位置

    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        arr[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

要注意从rear插入是先赋值再修改rear指针（++），而front插入则是先修改指针（–）再赋值，这是由两个指针的移动特点决定的。

    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 arr[front];
    }

    public int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return arr[(rear - 1 + capacity) % capacity];
    }