2021 - 9 -下旬 数据结构- 线性表 -双端循环队列 - java实现

//循环双端队列：Circle Double Ended Queue
//本质是对动态数组的优化
//队头队尾都可以添加或删除元素
//相比于普通循环队列需要注意的点是在队头插入元素时的对front前移的处理

public class CircleDequeZH {
    private int size;
    private int front;
    private  E elements[];
    private static final int DEFAULT_CAPACITY = 10;

    public CircleDequeZH() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    private int getMo(int a, int b){
        return a > b ? (a-b) : a;
        //%运算效率太低，当a<2b时可以用这个表达式替代取模，而循环队列front+index最大等于2*length-1，恰好符合要求
    }

    //计算队头队尾元素下标可以写一个函数，用来映射循环队列中的真实索引
    public int realIndexCaculate(int index){
        if (index<0){
            return getMo((index + front + elements.length), elements.length);
            //当front=0时，我们在队头插入元素，front要前移，也就是到整个数组的末尾，所以单独写一个if应对这种情况
            //这时候front的新位置为（front-1+length）%length
        }
        return getMo((index+front),elements.length);//!!!
        //就是要找队列中的下标为index的（第index+1个）元素，返回它在我们数组里的真实下标
        //我觉得影响以后的可读性就没用
    }


    private void ifNeedEnLarge(int needCapacity){
        int oldcapacity = elements.length;
        if (needCapacity<=oldcapacity){
            return;
        }else{
            int newcapacity = oldcapacity + (oldcapacity>>1);
            E[] newElements = (E[]) new Object[newcapacity];
            for (int i=0;i