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

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

导读：副标题#e# 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)，效率很高。