自己动手实现java数据结构（四）双端队列

　　3. 内部数组被看成是一个环，下标移动到边界临界点时，通过取模运算来计算逻辑下标对应的真实下标。

    @Override
     addHead(E e) {
        :::头部插入元素 head下标左移一位
        this.head = getMod(this.head - 1);
        :::存放新插入的元素
        this.elements[this.head] = e;

        :::判断当前队列大小 是否到达临界点
        if(head == tail){
            :::内部数组扩容
            expand();
        }
    }

    @Override
     addTail(E e) {
        this.tail] = e;
        :::尾部插入元素 tail下标右移一位
        this.tail = getMod(this.tail + 1);

                    expand();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
     E removeHead() {
        :::暂存需要被删除的数据
        E dataNeedRemove = (E).head];
        :::将当前头部元素引用释放
        this.head] = null;

        :::头部下标 右移一位
        this.head + 1 dataNeedRemove;
    }

    @Override
    @SuppressWarnings("unchecked" E removeTail() {
        :::获得尾部元素下标(左移一位)
        int lastIndex = getMod(this.tail - 1.elements[lastIndex];

        :::设置尾部下标
        this.tail = lastIndex;

         E peekHead() {
        return (E).head];
    }

    @Override
    @SuppressWarnings("unchecked" E peekTail() {
        .elements[lastIndex];
    }

　　队列常用接口时间复杂度：

　　基于数组的队列在访问头尾元素时，进行了一次取模运算获得真实下标，由于数组的随机访问是常数时间复杂度(O(1))，因此队列常用接口的时间复杂度都为O(1)，效率很高。

3.1.5 扩容操作：

　　可以看到，在入队插入操作结束后，会判断当前队列容量是否已经到达了临界点。

　　前面提到，只有在队列为空时，头部下标才会和尾部下标重合；而当插入新的入队元素之后，使得头部下标等于尾部下标时，说明内部数组的容量已经达到了极限，需要进行扩容才能容纳更多的元素。

我们举一个简单的例子来理解扩容操作：

　　尾部下标为2.头部下标为3，队列内的元素为头部下标到尾部下标(左闭右开)中的元素排布为(1，2，3，4，5，6)。

　　目前队列刚刚在下标为2处的尾部入队元素"7"。尾部下标从2向右移动一位和头部下标重合，此时队列中元素排布为(1，2，3，4，5，6，7)，此时需要进行一次扩容操作。

　　在扩容完成之后，我们希望让队列的元素在内部数组中排列的更加自然：

　　　　1. 队列中元素的顺序不变，依然是(1，2，3，4，5，6，7)，内部数组扩容一定的倍数(两倍)

　　　　2. 队列中第一个元素将位于内部数组的第0位，队列中的元素按照头尾顺序依次排列下去

　　扩容的大概思路：

　　　　1. 将"头部下标"直至"当前内部数组尾部"的元素按照顺序整体复制到新扩容数组的起始位置(红色背景的元素)

　　　　2. 将"当前内部数组头部"直至"尾部下标"的元素按照顺序整体复制到新扩容数组中(位于第一步操作复制的数据区间之后)(蓝色背景的元素)

扩容前：

扩容后：

（编辑：网站开发网_马鞍山站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!