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

发布时间：2021-04-04 12:14:33 所属栏目：电商来源：网络整理

导读：1.双端队列介绍在介绍双端队列之前，我们需要先介绍队列的概念。和栈相对应，在许多算法设计中，需要一种" 先进先出(First Input First Output) "的数据结构，因而一种被称为" 队列(Queue) "的数据结构被抽象了出来(因为现实中的队列,就是先进先出的)。队

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

扩容前：

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

扩容后：

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

扩容代码的实现：　　

   
     * 内部数组扩容
     *  expand(){
        :::内部数组 扩容两倍
        int elementsLength = .elements.length;
        Object[] newElements = new Object[elementsLength * EXPAND_BASE];

        :::将"head -> 数组尾部"的元素 复制在新数组的前面 (tips：使用System.arraycopy效率更高)
        for(int i=this.head,j=0; i<elementsLength; i++,j++){
            newElements[j] = .elements[i];
        }

        :::将"0 -> head"的元素 复制在新数组的后面 (tips：使用System.arraycopy效率更高)
        int i=0,j=elementsLength-this.head; i<this.head; i++,1)">:::初始化head,tail下标
        this.tail = :::内部数组指向 新扩容的数组
        this.elements = newElements;
    }

　　扩容操作时间复杂度：

　　动态扩容的操作由于需要进行内部数组的整体copy，其时间复杂度是O(n)。

　　但是站在全局的角度，动态扩容只会在入队操作导致空间不足时偶尔的被触发，整体来看，动态扩容的时间复杂度为O(1)。

3.1.6 其它接口实现：

 size() {
        return getMod(tail - head);
    }

    @Override
     isEmpty() {
        :::当且仅当 头尾下标相等时 队列为空
        return (head == tail);
    }

    @Override
     clear() {
        int head = .head;
        int tail = .tail;

        while(head !=this.elements[head] = ;
            head = getMod(head + 1);
        }

        ;
    }

    @Override
    public Iterator<E> iterator() {
        return  Itr();
    }