设为首页 - 加入收藏 华夏网 ()- 云主机,资讯,互联网,人工智能,云计算,大赢家论坛,区块链,VR,站长网!
热搜: 平台 google 2019 中国
当前位置: 主页 > 电商 > 正文

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

发布时间:2021-04-04 12:14 所属栏目:[电商] 来源:网络整理
导读:1.双端队列介绍 在介绍双端队列之前,我们需要先介绍队列的概念。和栈相对应,在许多算法设计中,需要一种" 先进先出(First Input First Output) "的数据结构,因而一种被称为" 队列(Queue) "的数据结构被抽象了出来(因为现实中的队列,就是先进先出的)。 队

1.双端队列介绍

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

  队列是一种线性表,将线性表的一端作为队列的头部,而另一端作为队列的尾部。队列元素从尾部入队,从头部出队(尾进头出,先进先出)。

  双端队列(Double end Queue)是一种特殊的队列结构,和普通队列不同的是,双端队列的线性表两端都可以进行出队和入队操作。当只允许使用一端进行出队、入队操作时,双端队列等价于一个栈;当限制一端只能出队,另一端只能入队时,双端队列等价于一个普通队列。

  简洁起见,下述内容的"队列"默认代表的就是"双端队列"。

2.双端队列ADT接口

/**
 * 双端队列 ADT接口
 * */
public interface Deque<E>{

    
     * 头部元素插入
     * */
    void addHead(E e);

    
     * 尾部元素插入
     *  addTail(E e);

    
     * 头部元素删除
     * */
    E removeHead();

    
     * 尾部元素删除
     * 
    E removeTail();

    
     * 窥视头部元素(不删除)
     * 
    E peekHead();

    
     * 窥视尾部元素(不删除)
     * 
    E peekTail();

    
     * @return 返回当前队列中元素的个数
     int size();

    
     * 判断当前队列是否为空
     *  如果当前队列中元素个数为0,返回true;否则,返回false
     boolean isEmpty();

    
     * 清除队列中所有元素
     *  clear();

    
     * 获得迭代器
     * 
    Iterator<E> iterator();
}

3.双端队列实现细节

3.1 双端队列基于数组的实现(ArrayDeque)

  双端队列作为一个线性表,一开始也许会考虑能否像栈一样,使用向量作为双端队列的底层实现。

  但是仔细思考就会发现:在向量中,头部元素的插入、删除会导致内部元素的整体批量的移动,效率很差。而队列具有"先进先出"的特性,对于频繁入队,出队的队列容器来说,O(n)时间复杂度的单位操作效率是无法容忍的。因此我们必须更进一步,从更为基础的数组结构出发,实现我们的双端队列。

3.1.1 数组双端队列实现思路:

  在进行代码细节的展开之前,让我们先来理解以下基本思路:

  1.和向量一样,双端队列在内部数组容量不足时,能和向量一样动态的扩容。

  2.双端队列内部维护着"头部下标"、"尾部下标"。头部下标指向的是队列中第一位元素,尾部下标指向的是下一个尾部元素插入的位置。

  ? ?从头部下标起始,到尾部下标截止(左闭右开区间),连续保存着队列中的全部元素。在元素出队,入队时,通过移动头尾下标,进行队列中元素的插入、删除,从而避免了类似向量中大量内部元素的整体移动。

  ? ?当头部元素入队时,头部下标向左移动一位;头部元素出队时,头部下标向右移动一位。

  ? ?当尾部元素入队时,尾部下标向右移动一位;尾部元素出队时,尾部下标向左移动一位。

  3.当元素下标的移动达到了边界时,需要将数组从逻辑上看成一个环,其头尾是相邻的:

    下标从数组第0位时,向左移动一位,会跳转到数组的最后一位。

    下标从数组最后一位时,向右移动一位,会跳转到数组的第0位。

   下标越界时的跳转操作,在细节上是通过下标取模实现的。

?  

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

3.1.2 队列的基本属性:

  只有当队列为空时,头部节点和尾部节点的下标才会相等。

 * 基于数组的 双端队列
 * class ArrayDeque<E> implements Deque<E>
     * 内部封装的数组
     * private Object[] elements;

    
     * 队列默认的容量大小
     * private static final int DEFAULT_CAPACITY = 16;

    
     * 扩容翻倍的基数
     * int EXPAND_BASE = 2
     * 队列头部下标
     *  head;

    
     * 队列尾部下标
     *  tail;


    
     * 默认构造方法
     * public ArrayDeque() {
        //:::设置数组大小为默认
        this.elements = new Object[DEFAULT_CAPACITY];

        :::初始化队列 头部,尾部下标
        this.head = 0;
        this.tail = 0;
    }
}

3.1.3 取模计算:

  在jdk基于数组的双端队列实现中,强制保持内部数组容量为2的平方(初始化时容量为2的平方,每次自动扩容容量 * 2),因此其取模运算可以通过按位与(&)运算来加快计算速度。

  取模运算在双端队列的基本接口实现中无处不在,相比jdk的双端队列实现,我们实现的双端队列实现更加原始,效率也较差。但相对的,我们的双端队列实现也较为简洁和易于理解。在理解了基础的实现思路之后,可以在这个初始版本的基础上进一步优化。

   
     * 取模运算
     * int getMod( logicIndex){
        int innerArrayLength = this.elements.length;

        :::由于队列下标逻辑上是循环的

        :::当逻辑下标小于零时
        if(logicIndex < 0){
            :::加上当前数组长度
            logicIndex += innerArrayLength;
        }
        :::当逻辑下标大于数组长度时
        if(logicIndex >= innerArrayLength){
            :::减去当前数组长度
            logicIndex -= innerArrayLength;
        }

        :::获得真实下标
        return logicIndex;
    }

  取模运算时间复杂度:

  取模运算中只是进行了简单的整数运算,时间复杂度为O(1),而在jdk的双端队列实现中,使用位运算的取模效率还要更高。

3.1.4 基于数组的双端队列常用操作接口实现:

  结合代码,我们再来回顾一下前面提到的基本思路:

  1.?头部下标指向的是队列中第一位元素,尾部下标指向的是下一个尾部元素插入的位置。

  2. 头部插入元素时,head下标左移一位;头部删除元素时,head下标右移一位。

  ? ? 尾部插入元素时,tail下标右移一位;尾部删除元素时,tail下标左移一位。

【免责声明】本站内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。

网友评论
推荐文章