深入理解Java集合框架系列 -第六章 Java集合框架Deque

一、Deque的基本概念

Java集合中Deque是一种接口，定义如下：

public interface Deque<E> extends Queue<E> { }

它是一种支持两端插入和移除的线性集合,Deque是"double ended queue"的简写，通常发音”deck”。deque 即双端队列，是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行，如下方法说明了这一点：

总结 Deque 方法
	从头部操作的方法		从尾部操作的方法
	抛出异常	值	抛出异常	值
插入	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
删除	removeFirst()	pollFirst()	removeLast()	pollLast()
检查	getFirst()	peekFirst()	getLast()	peekLast()

大多数的Deque的实现类对元素的个数没有限制，但是也支持那些在容量上有严格限制的实现类。

Deque接口定义了很多方法，包括insert、remove、 examine等，这些方法可以从Deque两端来访问数据，执行这些方法，最后的结果可以分为两类，一种是value（包括null或者false或者true),另外一种是抛出异常。

Deque实现类通常不定义equals和hashCode方法，而是从Object对象中继承。

Deque接口的实现类虽然可以插入null,但强烈建议插入非null的值，这是因为null常常作为返回值，用来判断该Deque的对象是否为空。

Deque接口不像其他接口，比如List,不支持通过索引或者下标值去访问队列中的元素。

Deque接口可以通过removeFirstOccurrence或者removeLastOccurrence去删除内部的元素。

需要注意的是，当Deque实现类作为queue或者stack使用时，peek 方法一样可以使用，而且从取出队列的头部元素。

Deque可以作为LIFO LIFO(Last-In-First-Out)的stack来使用，元素从队列的头部推入或者取出。

对比 Stack and Deque 方法
Stack 方法	等价的 Deque 的方法
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()

Deque继承Queue接口，当然可以作为FIFO (First-In-First-Out)队列来使用，这时，元素加在队列的最后，从队列的头部取出元素。

对比Queue 和Deque方法
队列方法	双向队列的同等方法
add(e)	addLast(e)
offer(e)	offerLast(e)
emove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()

定义在Deque中所有的方法：

深入理解Java集合框架系列 -第六章 Java集合框架Deque

二、实现Deque接口的类

1、ArrayDeque

public class ArrayDeque<E> extendsAbstractCollection<E>

implements Deque<E>,Cloneable, Serializable{

}

Deque接口的一种可改变大小的实现，数组deque没有容量限制，可以根据需要增加容量，是非线程安全的；如果没有外同步，它不支持多线程的并发访问。不允许元素为null，该类用作栈或队列时，比Stack和LinkedList都要快。ArrayDeque的大多数操作需要分摊的常量时间复杂度(amortezed constanttime)，例外的有remove、removeFirstOccurrence、removeLastOccurrence、contains和iterator.remove()方法。

2、ConcurrentLinkedListDeque

publicclassConcurrentLinkedDeque<E>

extends AbstractCollection<E>

implements Deque<E>,java.io.Serializable {

}

一种基于链表的无边界的并发Deque。并发插入、移除和访问操作通过多线程安全执行。一个ConcurrentLinkedDeque是当多线程共享访问一个公共集合的有效选择。像多数其他并发集合实现一样，该类并不允许元素为null。

3、LinkedList

publicclassLinkedList<E>

extends AbstractSequentialList<E>

implementsList<E>, Deque<E>, Cloneable, java.io.Serializable

List和Deque接口的双向链表列表实现，实现了所有可选列表操作，且允许所有类型的元素（包括null）。所有操作对于一个双向链表列表来说都可以实现，索引到列表中某个元素的操作可以同从列表中距给定索引最近的列表的首或尾开始遍历。注意该实现不是同步的，如果多线程并发地访问一个链表，并且至少有一个线程改变列表结构，则必须增加外部同步。这通常经过同步一些封装该列表的对象来实现。如果没有此类对象，则该列表必须用Collections.synchronizedList来包装，最好在创建时完成，以避免对列表意外的非同步访问。

深入理解Java集合框架系列 -第六章 Java集合框架Deque

相关推荐