Deque

Deque

概述

特点

Deque是一个Queue的子接口，是一个双端队列，支持在两端插入和移除元素
deque支持索引值直接存取。
Deque头部和尾部添加或移除元素都非常快速。但是在中部安插元素或移除元素比较费时。
插入、删除、获取操作支持两种形式：快速失败和返回null或true/false
不推荐插入null元素，null作为特定返回值表示队列为空

常用方法

	抛出异常	特殊值	抛出异常	特殊值
插入	`addFirst(e)`	`offerFirst(e)`	`addLast(e)`	`offerLast(e)`
移除	`removeFirst()`	`pollFirst()`	`removeLast()`	`pollLast()`
检查	`getFirst()`	`peekFirst()`	`getLast()`	`peekLast()`

双向队列操作

插入元素

addFirst(): 向队头插入元素，如果元素为null，则发生空指针异常
addLast(): 向队尾插入元素，如果为空，则发生空指针异常
offerFirst(): 向队头插入元素，如果插入成功返回true，否则返回false
offerLast(): 向队尾插入元素，如果插入成功返回true，否则返回false

移除元素

removeFirst(): 返回并移除队头元素，如果该元素是null，则发生NoSuchElementException
removeLast(): 返回并移除队尾元素，如果该元素是null，则发生NoSuchElementException
pollFirst(): 返回并移除队头元素，如果队列无元素，则返回null
pollLast(): 返回并移除队尾元素，如果队列无元素，则返回null

获取元素

getFirst(): 获取队头元素但不移除，如果队列无元素，则发生NoSuchElementException
getLast(): 获取队尾元素但不移除，如果队列无元素，则发生NoSuchElementException
peekFirst(): 获取队头元素但不移除，如果队列无元素，则返回null
peekLast(): 获取队尾元素但不移除，如果队列无元素，则返回null

栈操作

pop(): 弹出栈中元素，也就是返回并移除队头元素，等价于removeFirst()，如果队列无元素，则发生NoSuchElementException

push(): 向栈中压入元素，也就是向队头增加元素，等价于addFirst()，如果元素为null，则发生NoSuchElementException，如果栈空间受到限制，则发生IllegalStateException

引用场景

满足FIFO场景时
满足LIFO场景时，曾经在解析XML按标签时使用过栈这种数据结构，但是却选择Stack类，如果在进行栈选型时，更推荐使用Deque类，应为Stack是线程同步

ArrayDeque

概述

特点

初始容量为16，每次扩容都会翻倍，并且容量一定是2^n。

public ArrayDeque() {

        elements = new Object[16];

    }

 public ArrayDeque(int numElements) {

        allocateElements(numElements);

    }

 private void allocateElements(int numElements) {

        int initialCapacity = MIN_INITIAL_CAPACITY;

        // Find the best power of two to hold elements.

        // Tests "<=" because arrays aren't kept full.

        if (numElements >= initialCapacity) {

            initialCapacity = numElements;

            initialCapacity |= (initialCapacity >>>  1);

            initialCapacity |= (initialCapacity >>>  2);

            initialCapacity |= (initialCapacity >>>  4);

            initialCapacity |= (initialCapacity >>>  8);

            initialCapacity |= (initialCapacity >>> 16);

            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off

                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements

        }

        elements = new Object[initialCapacity];

    }

>>>是无符号右移操作，|是位或操作，经过五次右移和位或操作可以保证得到大小为 2^n-1 的数。最后在自增一，就是 2^n。

增加或删除（head）

public void addFirst(E e) {

        if (e == null)

            throw new NullPointerException();

        elements[head = (head - 1) & (elements.length - 1)] = e;//注意点

        if (head == tail)

            doubleCapacity();

    }

elements[head = (head - 1) & (elements.length - 1)] = e;

当head为0时，实际上是11111111&00001111，结果是00001111，也就是物理数组的尾部15；当head增长如head+1超过物理数组长度如16时，实际上是00010000&00001111，结果00000000，也就是0，这样就回到了物理数组的头部.

相当于head初始值0时，第一次就将head指针定位到数组末尾了，然后指针从后向前移动。

而addLast就与之相反，控制tail指针，从前向后移动。当tail和head相遇了就说明空间已经满了。（就像一个圆环结构）

以上

@Fzxey

队列

Deque（队列）