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位。

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

?　　

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下标左移一位。

（编辑：黄山站长网）

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