【详解】Java中的queue和deque、ArrayDeque

一 、队列(queue)简述

队列(queue)是一种常用的数据结构，在Java里面Queue是一个接口，它只是定义了一个基本的Queue应该有哪些功能规约。可以将队列看做是一种特殊的线性表，该结构遵循的先进先出原则。

Java中，LinkedList实现了Queue接口,因为LinkedList进行插入、删除操作效率较高。

//将元素插入队列
boolean add(E e);
//将元素插入队列，与add相比，在容量受限时应该使用这个
boolean offer(E e);
//将队首的元素删除，队列为空则抛出异常
E remove( );
//将队首的元素删除，队列为空则返回null
E poll();

//获取队首元素，但不移除，队列为空则抛出异常
E element(;
//获取队首元素，但不移除，队列为空则返回nu11E 
peek()
1
2
3
4
5
6
7
8
9
10
11
12
13

二、双端队列（Deque）简述

双向队列(Deque) 全称为 double ended queue，是Queue的一个子接口，双向队列是指该队列两端的元素既能入队(offer)也能出队(poll)，除此之外，其余特性则和父级 Queue 类似。如果将Deque限制为只能从一端入队和出队，则可实现栈的数据结构。对于栈而言，有入栈(push)和出栈(pop)，遵循先进后出原则。

Deque 中定义的方法主要分为四部分，

1. 第一部分就如 Deque 定义所言，提供两侧插入或删除的方法。
2. 第二部分是继承自 Queue 的实现。
3. 第三部分表示如果要基于此实现一个stack需要实现的方法。
4. 最后一部分是继承自 collection 的方法。

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。
每种方法都存在两种形式：

• 一种形式在操作失败时抛出异常。
• 另一种形式返回一个特殊值（null 或 false，具体取决于操作）。
• 插入操作的后一种形式是专为使用有容量限制的 Deque 实现设计的；在大多数实现中，插入操作不能失败。

//在队首添加元素
void addFirst(E e);
boolean offerFirst(E e);

//在队尾添加元素
void addLast(E e);
boolean offerLast(E e);

//删除队首元素
E removeFirst();
E pollFirst();

//删除队尾元素
E removeLast();
E pollLast();

//获取队首元素
E getfirst();
E peekFirst();

//获取队尾元素
E getLast();
E peekLast();

//删除第一个事件，大多数指的是删除第一个和 o equals的元素
boolean removeFirstoccurrence(object o);
//删除最后一个事件，大多数指的是删除最后一个和 o equals的元素
boolean removeLastoccurrence(object o);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

当作为队列使用时，我们会将它与LinkedList 类来做对比。因为 Deque接口继承自 Queue接口，在这里，分别列出两者接口所定义的方法，两者内容区别如下:

当作为找使用时，难免会将它与 Stack 的类做比较，Stack类的数据结构也是后进先出，可以作为栈来使用，分别列出 Stack 类和 Deque 接口所定义的方法，两者内容区别如下:

三、ArrayDeque

ArrayDeque类是 双端队列的线性实现类。
虽然，ArrayDeque 和 Stack类都可以作为 来使用，但是 ArrayDeque 的效率要高于 Stack类，并且功能也比 Stack类丰富的多，当需要使用栈时，Java 已不推荐使用 Stack，而是推荐使用更高效的 ArrayDeque，次选LinkedList.

ArrayDeque 通过循环数组的方式实现的循环队列，并通过位运算来提高效率，容量大小始终是2的次幂。当数据充满数组时，它的容量将翻倍。
作为 stack ，因为其非线程安全所以效率高于java.util.stack，
而作为队列，因为其不需要结点支持所以更快 (LinkedList使用Node存储数据，这个对象频繁的new与clean，使得其效率略低于ArrayDeque) 。