Deque 双端队列

Deque是一个双端队列接口，继承自Queue接口，Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque，其中LinkedList是最常用的。在 Collections API 中有下面两种实现：

java.util.LinkedList
java.util.ArrayDeque

LinkedList类是非常标准的Deque和Queue的实现，它在内部使用链接列表来建模queue或deque。
ArrayDeque类内部存储元素是数组，如果元素数超过数组中的空间，则分配一个新的数组，并移动所有元素，换句话说，ArrayDeque根据需要增长，即使它将元素存储在数组中
一般而言，都会选择LinkedList，而非ArrayDeque

Deque的三种用途：

• 普通队列(一端进另一端出):

  Queue queue = new LinkedList()或Deque deque = new LinkedList()

• 双端队列(两端都可进出)

  Deque deque = new LinkedList()

• 堆栈

  Deque deque = new LinkedList()

Deque是一个线性collection，支持在两端插入和移除元素。名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的。
此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是专为使用有容量限制的 Deque 实现设计的；在大多数实现中，插入操作不能失败。

 Deque接口扩展(继承)了 Queue 接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：  

双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

常用方法

addLast()

该方法可以在Deque的尾部添加元素，这与Deque接口从Queue接口继承的add()方法等效：

Deque<String> deque = new LinkedList<>();
deque.addLast("element 1");

如果Deque中不能添加元素则addLast()方法会抛异常， offerLast()方法则会返回false

addFirst()

该方法可以在Deque的头部添加元素

Deque<String> deque = new LinkedList<>();
deque.addFirst("element 1");

如果Deque不能添加元素，addFirst()方法会抛异常， offerFirst()方法则返回 false

push()

push可以在Deque的头部添加元素，效果等同于addFirst()

Deque<String> deque = new LinkedList<>();
deque.push("element 0");

pop()

该方法将移除Deque的头部元素，如果Deque是空则报异常

Deque<String> deque = new LinkedList<>();
deque.add("element 0");
deque.add("element 1");
deque.add("element 2");
String removedElement = deque.removeLast();

peekFirst()

该方法返回Deque的第一个元素，如果Deque是空则返回NULL，不会报异常，同时，它不会破坏Deque结构，只是单纯返回一个值而已

Deque<String> deque = new LinkedList<>();
deque.add("first element");
deque.add("last element");
String firstElement = deque.peekFirst();

peekLast()

该方法与peekFist()相反，它会返回Deque的最后一个元素，同样不会破获其结构，不会报异常

Deque<String> deque = new LinkedList<>();
deque.add("first element");
deque.add("last element");
String firstElement = deque.peekLast();

getFirst()

同peekFirst，获取Deque的第一个元素并且保持Deque结构，但是当Deque为空时，会报异常

Deque<String> deque = new LinkedList<>();
deque.add("first element");
deque.add("last element");
String firstElement = deque.getFirst();

removeFirst()

该方法将删除Deque的头部元素，如果Deque为空则报异常

Deque<String> deque = new LinkedList<>();
deque.add("element 0");
String removedElement = deque.removeFirst();

removeLast()

该方法将删除Deque的尾部元素，如果Deque为空则报异常

Deque<String> deque = new LinkedList<>();
deque.add("element 0");
deque.add("element 1");
deque.add("element 2");
String removedElement = deque.removeLast();

pollFirst() / pollLast()

这两方法和 removeFirst / removeLast 的效果是一样的，只不过，当Deque为空时，不报异常，而是返回NULL

Deque<String> deque = new LinkedList<>();

deque.add("element 0");
deque.add("element 1");
deque.add("element 2");

String removedElement = deque.pollFirst();
String removedElement = deque.pollLast();

检查Deque是否包含某个元素

可以用contains()方法检查Deque中是否包含某个元素，如果包含返回true否则返回false:

Deque<String> deque = new ArrayDeque<>();

deque.add("first element");

boolean containsElement1 = deque.contains("first element");
boolean containsElement2 = deque.contains("second element");

通过For-Each循环迭代Deque

Deque<String> deque = new LinkedList<>();

deque.add("element 0");
deque.add("element 1");
deque.add("element 2");

for(String element : deque) {
    System.out.println(element);
}