Deque
约 500 字大约 2 分钟
2024-08-08
我们知道,Queue 是队列,只能一头进,另一头出
如果把条件放松一下,允许两头都进,两头都出,这种队列叫双端队列(Double Ended Queue),学名 Deque
Java 集合提供了接口 Deque 来实现一个双端队列,它的功能是
既可以添加到队尾,也可以添加到队首
既可以从队首获取,又可以从队尾获取
Queue 和 Deque 出队和入队的方法比较
| Queue | Deque | |
|---|---|---|
| 添加元素到队尾 | add(E e) / offer(E e) | addLast(E e) / offerLast(E e) |
| 取队首元素并删除 | E remove() / E poll() | E removeFirst() / E pollFirst() |
| 取队首元素但不删除 | E element() / E peek() | E getFirst() / E peekFirst() |
| 添加元素到队首 | 无 | addFirst(E e) / offerFirst(E e) |
| 取队尾元素并删除 | 无 | E removeLast() / E pollLast() |
| 取队尾元素但不删除 | 无 | E getLast() / E peekLast() |
Deque 接口实际上扩展自 Queue
public interface Deque<E> extends Queue<E> {
}栗子
Queue 提供的 add()/offer() 方法在 Deque 中也可以使用,但是直接写 deque.offer(),我们就需要思考,offer() 实际上是 offerLast(),我们明确地写上 offerLast(),不需要思考就能一眼看出这是添加到队尾
public static void main(String[] args) {
Deque<String> deque = new LinkedList<>();
deque.offerLast("A"); // A
deque.offerLast("B"); // A <- B
deque.offerFirst("C"); // C <- A <- B
System.out.println(deque.pollFirst()); // C
System.out.println(deque.pollLast()); // B
System.out.println(deque.pollFirst()); // A
System.out.println(deque.pollFirst()); // null
}我们发现 LinkedList 真是一个全能选手,它即是 List,又是 Queue,还是 Deque。但是我们在使用的时候,总是用特定的接口来引用它,这是因为持有接口说明代码的抽象层次更高,而且接口本身定义的方法代表了特定的用途
// 不推荐的写法:
LinkedList<String> d1 = new LinkedList<>();
d1.offerLast("z");
// 推荐的写法:
Deque<String> d2 = new LinkedList<>();
d2.offerLast("z");可见面向抽象编程的一个原则就是:尽量持有接口,而不是具体的实现类