Use Dynamic Circulate Array to Implement Deque

Question

实现Deque的方法：get(), insert from front or end（add or push）, delete from front or end（pop or poll）, 同时当添加元素数量超过原始数组长度时，数组可以动态扩张。所有方法的时间复杂度为 O(1)。

Solution

要在前后两端插入和删除，考虑使用循环数组结构。用front记录数组头（不为null），用end记录数组尾（为null），数组可以插入数组长度－1个元素，用end+1 % size == front来判断队列是否full，用end == front来判断对列是否空。当数组为full时还要插入元素则需要将数组扩展为原来的两倍。

同时使用数组动态扩展的方法System.arraycopy()。

Reference:

Java数组实现可以动态增长的队列

java队列实现（顺序队列、链式队列、循环队列

代码如下：

class Mydequeue<E>{
    int front;
    int end;
    Object[] storage;
    int initialLen = 5;

    public Mydequeue(){
        this.front = this.end = 0;
        storage = new Object[initialLen];
    }

    //判断数组是否满
    public boolean isFull(){
        if((end + 1) % storage.length == front || (front - 1) % storage.length == end){
            return true;
        }
        return false;
    }
    //判断数组是否空
    public boolean isEmpty(){
        if(front == end){
            return true;
        }
        return false;
    }
    //从数组头加入元素
    public void enqueueFromFront(E elem){
        if(isFull){
            enLarge();
            System.out.println("队列容量不够，已动态增加数组容量到："+storage.length); 
        }

        front = (front - 1) % storage.length;
        storage[front] = elem;
    }
    //从数组尾加入元素
    public void enqueueFromEnd(E elem){
        if(isFull){
            enLarge();
            System.out.println("队列容量不够，已动态增加数组容量到："+storage.length); 
        }

        storage[end] = elem;
        end = (end + 1) % storage.length;
    }
    //从数组头删除元素
    public Object dequeueFromFront(){
        if(isEmpty()){
            System.out.println("队列为空，无法出队"); 
        }

        storage[front] = null;
        front = (front + 1) % storage.length;
    }
    //从数组尾删除元素
    public Object dequeueFromEnd(){
        if(isEmpty()){
            System.out.println("队列为空，无法出队"); 
        }

        end = (end - 1) % storage.length;
        storage[end] = null;
    }
    //获取下标为index的元素
    public Object get(int index){
        return storage[index];
    }
    //打印数组
    public void printAll(){
        for(Object i : storage){
            System.out.print(i + " ");
        }
        System.out.println();
    }
    //扩张数组
    public void enLarge(){
        //新数组为原数组的两倍
        Object a = new Object[storage.length * 2];
        //当未填充位置在最后时，直接将前面的元素复制给新数组
        if(end == storage.length - 1){
            System.arraycopy(storage, 0, a, 0, storage);
        }else{
        //当未填充位置在end和front之间时，原数组分为两段，将0~end的元素直接复制到新数组，将front和之后的元素复制到新数组的尾部，这样end和front之间又有了可以填充的空间，实现了数组的扩张。最后记得要更新front在新数组中的index（end不变）。
            System.arraycopy(storage, 0, a, 0, end + 1);
            System.arraycopy(storage, front, a, a.length - storage.length + front, storage.length - front);
            front = a.length - storage.length + front;
        }

        storage = a;
    }
}