深入了解双端队列Deque

时间:2021-02-14 19:24:53

本文出自博客Vander丶CSDN博客,如需转载请标明出处,尊重原创谢谢

博客地址:http://blog.csdn.net/l540675759/article/details/62893335

Deque的类图

深入了解双端队列Deque

由上图可知Deque在Java中以接口的形式存在,同时Deque还继承Queue(队列)的接口。


Queue队列

队列是一种特殊的线性容器,它是一种先进先出(FIFO)的数据结构。

它只允许在容器的头部进行删除操作,而在表的后端进行插入操作。进行插入操作的端成为队尾,进行删除操作的端称为队头。

当队列中没有元素时,被称为空队列。

同理当插入元素已经充满队列,被称为满队列.

深入了解双端队列Deque


Queue队列的源码解析

Queue的插入操作

/**
* 相同点:
* 插入为null的元素,会报空指针
* 插入与执行泛型不符的类型会报类型转换异常
* 插入某些不允许插入的元素,会阻止其插入,IDE会提示非法参数
*
* 不同点:
* 在满队列状态下:
* 使用add()方法会报IllegalStateException异常,提示队列已满.
* 使用offer()方法在此情况下不会报异常而返回false.
*/

boolean add(E e);
boolean offer(E e);

上述两种方法都是插入操作,当插入元素成功时,会返回true.
不同点:

注意 : 队列中不允许插入为null的元素,否则会报空指针.

在进行插入操作时,一般情况推荐使用offer()来插入元素.


Queue的取出操作

/**
* 相同点:
* 都是Queue的取出操作,返回值为队列容器头部元素.
*
* 不同点:
* 当处于空队列状态时,remove()方法会抛出队列为空,没有匹配元素的的异常
* 而poll()方法则会返回null值,不会报异常.
*/

E remove();
E poll();

在进行删除操作时,一般情况推荐使用poll()来取出元素


Queue的检索操作

/**
* 相同点:
* 都是Queue的检索操作,返回值为队列容器头部元素,但是不会删除元素.
*
* 不同点:
* 当处于空队列状态时,element()方法会抛出队列为空,没有匹配元素的的异常
* 而peek()方法则会返回null值,不会报异常.
*/

E element();
E peek();

在进行检索操作时,一般情况推荐使用peek()来取出元素


下图将队列(Queue)的操作进行了总结 :
深入了解双端队列Deque


Deque(双端队列)的介绍

Deque的含义是“double ended queue”,即双端队列.

Deque是一种具有队列和栈的性质的数据结构.双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行.

通过开始的类图可以发现,Deque继承了Queue(队列)的接口,它的直接实现有ArrayDeque、LinkedList等。

Deque的容量有两种模式,一种是固定长度,另一种是容量无限。

同Queue一样,Deque也定义了两套操作访问元素的方法,比如在头部和尾部进行插入、删除、检索元素、同样的,一种是在满队列或者空队列的操作元素时,会报异常,而另一种则会return null或者return false。

这里引用了博主“疯子123”的博文,对于Deque介绍的示意图

Java 集合深入理解(10):Deque 双端队列

深入了解双端队列Deque

由于Deque接口继承Queue接口,当Deque当做队列使用时(FIFO),只需要在头部删除,尾部添加即可。

深入了解双端队列Deque

除此之外,Deque也可以当做栈(后进先出)使用,这时入栈,出栈的元素都在双端队列的头部进行。

深入了解双端队列Deque

看图在结合Queue的分析,大家就会明白Deque方法的含义。


Deque的实现类

Deque的使用场景

在一般情况,不涉及到并发的情况下,有两个实现类,可根据其自身的特性进行选择,分别是:

LinkedList 大小可变的链表双端队列,允许元素为 null
ArrayDeque 大下可变的数组双端队列,不允许 null

注意:LinkedList 和ArrayDeque是线程不安全的容器。

在并发场景下,推荐使用LinkedBlockingDeque:

LinkedBlockingDeque(阻塞的双向队列)

因为LinkedBlockingDeque在队列为空的情况下,获取操作将会阻塞,直到有元素添加。


关于ArrayDeque、LinkedList

因为网上对于ArrayDeque已经有详细的介绍,这里就不打算在进行重复的去翻译API,直接附上链接。

这里推荐的是博主czj4451的源码分析:

内含LinkedList和ArrayDeque。


参考文章:

1.Java 集合深入理解(10):Deque 双端队列
http://www.cnblogs.com/hehehaha/p/6147206.html

2.同步容器、并发容器、阻塞队列、双端队列与工作密取
http://www.tuicool.com/articles/jE3IV3