Deque

## Deque 双端队列接口
主要用于两端插入删除数据的功能，想用堆栈一般找它。
他并不禁止null元素，但建议别这么干，有些函数是通过返回是否null来判断栈是否为空的
你可以把它当队列用

| 队首操作 | 函数 |
| --- | --- |
| 添加队首 | add(e)、offer(e)、addFirst(e) |
| 删除队首，空队列时抛异常 | pop()、remove()、removeFirst() |
| 删除队首，空队列时返回null |poll()、pollFirst()|
| 获取队首，空队列抛异常|element()、getFirst()|
| 获取队首，空队列返回null | peek()、peekFirst()|

| 队尾操作 | 函数 |
| --- | --- |
| 添加队尾 | push(e)、addLast(e)、offerLast(e)|
| 删除队尾，空队列抛异常 | removeLast() |
| 删除队尾，空队列返回null | pollLast() |
| 获取队尾，空队列抛出异常| getLast() |
| 获取队尾，空队列返回null| peekLast() |

比较有趣的是，双端队列定义了删除中间的数据，所以他可以做到超出堆栈的事情。
```
// 从头遍历，删遇到的第一个目标对象
boolean removeFirstOccurrence(Object o);
// 从尾遍历，删遇到的第一个目标对象
boolean removeLastOccurrence(Object o);
```

继承自Queue队列接口，
实现有LinkedList、ArrayDeque、BlockingDeque、ConcurrentLinkedDeque、

1. LinkedList
底层是双向链表，一般堆栈的实现找他就行

2. ArrayDeque
底层是数组，和ArrayList一样有频繁写时扩容带来的损耗，却没提供对中间数据的高效读。

3. BlockingDeque
阻塞的双端队列，读的时候会等两端数据非空，写时会等中间数据有空白可写
他自己也是个接口，实现由LinkedBlockingDeque提供，底层是双向链表和ReentrantLock
容量如果不指定的话就是Integet.MAX

4. ConcurrentLinkedDeque
并发包提供的实现，允许无限并发。底层是双向链表 + CAS思想实现的。
与大多数其他并发集合实现一样，此类不允许使用空元素。
不用sync关键字和java的goto语法，值得纪念

```
    private void linkFirst(E e) {
        checkNotNull(e);
        final Node<E> newNode = new Node<E>(e);

// 标识goto的位置
        restartFromHead:
        for (;;)
            for (Node<E> h = head, p = h, q;;) {
                if ((q = p.prev) != null && (q = (p = q).prev) != null)
                    // 每次步入循环都检查一次，p是不是最新的head (head.prev == null)
					// 说明head被更新了，p指向新的head
                    p = (h != (h = head)) ? h : q;
                else if (p.next == p)
				    // p指向head了，但是数据异常咯
					// 类似goto的跳跃，重新开始
                    continue restartFromHead;
                else {
                    // p终于是head了，newNode.next = p;
                    newNode.lazySetNext(p);
					// CAS 交换 p.prev和目标节点
                    if (p.casPrev(null, newNode)) {
                        // 交换成功，CAS把newNode设置成head
                        if (p != h)
                            casHead(h, newNode);
                        return;
                    }
                   // CAS没抢过其他线程，再抢一遍
                }
            }
    }
```