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

发布时间：2021-04-02 08:20:39 所属栏目：站长百科来源：网络整理

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

扩容代码的实现：　　

   
     * 内部数组扩容
     *  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();
    }