使用Deque
如果把条件放松一下,允许两头都进,两头都出,这种队列叫双端队列(Double Ended Queue),学名Deque
。
Java集合提供了接口Deque
来实现一个双端队列,它的功能是:
- 既可以添加到队尾,也可以添加到队首;
我们来比较一下Queue
和Deque
出队和入队的方法:
对于添加元素到队尾的操作,Queue
提供了add()
/offer()
方法,而Deque
提供了addLast()
/offerLast()
方法。添加元素到对首、取队尾元素的操作在Queue
中不存在,在Deque
中由addFirst()
/removeLast()
等方法提供。
因此,Queue
提供的add()
/offer()
方法在Deque
中也可以使用,但是,使用,最好不要调用offer()
,而是调用offerLast()
:
如果直接写deque.offer()
,我们就需要思考,offer()
实际上是offerLast()
,我们明确地写上offerLast()
,不需要思考就能一眼看出这是添加到队尾。
因此,使用Deque
,推荐总是明确调用offerLast()
/offerFirst()
或者pollFirst()
/pollLast()
方法。
我们发现LinkedList
真是一个全能选手,它即是List
,又是Queue
,还是Deque
。但是我们在使用的时候,总是用特定的接口来引用它,这是因为持有接口说明代码的抽象层次更高,而且接口本身定义的方法代表了特定的用途。
// 不推荐的写法:
LinkedList<String> d1 = new LinkedList<>();
// 推荐的写法:
d2.offerLast("z");
可见面向抽象编程的一个原则就是:尽量持有接口,而不是具体的实现类。
Deque
实现了一个双端队列(Double Ended Queue),它可以:
- 将元素添加到队尾或队首:
addLast()
/offerLast()
/addFirst()
/offerFirst()
; - 从队首/队尾获取元素并删除:
removeFirst()
/pollFirst()
/removeLast()
/pollLast()
; - 从队首/队尾获取元素但不删除:
getFirst()
/peekFirst()
/getLast()
/peekLast()
; - 避免把
null
添加到队列。