使用Deque

共计 1857 个字符，预计需要花费 5 分钟才能阅读完成。

我们知道，Queue是队列，只能一头进，另一头出。

如果把条件放松一下，允许两头都进，两头都出，这种队列叫双端队列（Double Ended Queue），学名Deque。

Java 集合提供了接口 Deque 来实现一个双端队列，它的功能是：

• 既可以添加到队尾，也可以添加到队首；
• 既可以从队首获取，又可以从队尾获取。

我们来比较一下 Queue 和Deque出队和入队的方法：

对于添加元素到队尾的操作，Queue提供了 add()/offer() 方法，而 Deque 提供了 addLast()/offerLast() 方法。添加元素到队首、取队尾元素的操作在 Queue 中不存在，在 Deque 中由 addFirst()/removeLast() 等方法提供。

注意到 Deque 接口实际上扩展自Queue：

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

因此，Queue提供的 add()/offer() 方法在 Deque 中也可以使用，但是，使用Deque，最好不要调用offer()，而是调用offerLast()：

import java.util.Deque;
import java.util.LinkedList;

public class Main {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, 剩下 A <- B
        System.out.println(deque.pollLast()); // B, 剩下 A 
        System.out.println(deque.pollFirst()); // A
        System.out.println(deque.pollFirst()); // null
    }
}

如果直接写 deque.offer()，我们就需要思考，offer() 实际上是offerLast()，我们明确地写上offerLast()，不需要思考就能一眼看出这是添加到队尾。

因此，使用 Deque，推荐总是明确调用offerLast()/offerFirst() 或者 pollFirst()/pollLast() 方法。

Deque是一个接口，它的实现类有 ArrayDeque 和LinkedList。

我们发现 LinkedList 真是一个全能选手，它即是List，又是Queue，还是Deque。但是我们在使用的时候，总是用特定的接口来引用它，这是因为持有接口说明代码的抽象层次更高，而且接口本身定义的方法代表了特定的用途。

// 不推荐的写法:
LinkedList<String> d1 = new LinkedList<>();
d1.offerLast("z");
// 推荐的写法：
Deque<String> d2 = new LinkedList<>();
d2.offerLast("z");

可见面向抽象编程的一个原则就是：尽量持有接口，而不是具体的实现类。

小结

Deque实现了一个双端队列（Double Ended Queue），它可以：

• 将元素添加到队尾或队首：addLast()/offerLast()/addFirst()/offerFirst()；
• 从队首/队尾获取元素并删除：removeFirst()/pollFirst()/removeLast()/pollLast()；
• 从队首/队尾获取元素但不删除：getFirst()/peekFirst()/getLast()/peekLast()；
• 总是调用 xxxFirst()/xxxLast() 以便与 Queue 的方法区分开；
• 避免把 null 添加到队列。