Java 双端队列 Deque

Deque 简介

Deque 双端队列（deque，全名 double-ended queue）接口位于 java.util 包中，它是 Queue 队列接口的子类型。

Deque 支持从数据结构的两端添加和删除元素，因此可以用作栈或队列。

栈支持后进先出（LIFO）操作，队列支持先进先出（FIFO）操作。而双端队列中的元素可以从两端入队、出队，即可以同时在队头和队尾添加和移除元素。

作用

在日常开发中经常会用到队列和栈的数据结构。

在 Java 中表示队列和栈的有 Queue 和 Stack，而 Java 中的 Stack 具有设计上的缺陷，滥用了继承，继承了 Vector（ Vector 很多方法都用了 synchronized 修饰，线程安全，但效率太低，已被弃用），暴露了 set/get 方法，导致 Stack 可以进行随机位置的访问，与 Stack 的设计理念相冲突。

而 Deque 双端队列这种数据结构就很灵活了，即可以满足队列的 FIFO 特性，又可以满足栈的 LIFO 特性，官方也推荐使用 Deque 代替 Stack。

Deque 有两个重要的实现类 ArrayDeque 和 LinkedList ，分别对应 顺序存储结构 及 链式存储结构。

ArrayDeque

• 数组结构：可变数组来实现
• 因为双端队列只能在头部和尾部插入或者删除元素，所以时间复杂度为 O(1)，但是在扩容的时候需要批量移动元素，其时间复杂度为 O(n)
• 扩容的时候，将数组长度扩容为原来的 2 倍，即 n << 1
• 数组采用连续的内存地址空间，所以查询的时候，时间复杂度为 O(1)
• 它是非线程安全的集合
• 不支持插入 null 元素

LinkedList

• 基于双向链表的结构，所以长度没有限制，因此不存在扩容机制
• 由于链表的内存地址是非连续的，所以只能从头部或者尾部查找元素，查询的时间复杂为 O(n)，但是 JDK 对 LinkedList 做了查找优化，当我们查找某个元素时，若 index < (size / 2)，则从 head 往后查找，否则从 tail 开始往前查找 , 但是我们在计算时间复杂度的时候，常数项可以省略，故时间复杂度 O(n)
• 链表通过指针去访问各个元素，所以对于插入、删除元素只需要更改指针指向即可，时间复杂度为 O(1)
• 它是非线程安全的集合
• 支持插入 null 元素

ArrayDeque 比 LinkedList 效率高：

• 从速度的角度：ArrayDeque 基于数组实现双端队列，而 LinkedList 基于双向链表实现双端队列，数组采用连续的内存地址空间，通过下标索引访问，链表是非连续的内存地址空间，通过指针访问，所以在寻址方面数组的效率高于链表。

• 从内存的角度：虽然 LinkedList 没有扩容的问题，但是插入元素的时候，需要创建一个 Node 对象, 换句话说每次都要执行 new 操作，当执行 new 操作的时候，其过程是非常慢的，会经历两个过程：类加载过程 、对象创建过程。

常用方法

方法	作用
boolean add(E e)	往队列尾部加入元素
void addFirst(E e)	往队列首部加入元素
void addFirst(E e)	往队列尾部加入元素
boolean offer(E e)	将指定元素插入该队列的尾部。与 add 的区别是 add 当没有可用空间时会抛异常，而 offer 会返回 false
boolean offerFirst(E e)	往队列首部加入元素
boolean offerLast(E e)	往队列尾部加入元素
E peek()	返回但不删除双端队列的首元素
E peekFirst()	返回但不删除双端队列的首元素
E peekLast()	返回但不删除双端队列的尾元素
E poll()	返回且删除双端队列的首元素
E pollFirst()	返回且删除双端队列的首元素
E pollLast()	返回且删除双端队列的尾元素
E pop()	从由双端队列表示的堆栈中弹出一个元素
void push(E e)	将一个元素推入由双端队列表示的堆栈中
int size()	返回队列中的元素个数