17370845950

Deque支持两端操作，可高效实现栈和队列功能。常用方法包括addFirst/removeFirst、addLast/removeLast等，提供异常处理与null返回两种模式。ArrayDeque基于数组，性能优但不支持null；LinkedList基于链表，支持null且功能更广。适用于滑动窗口、回文判断、表达式求值及撤销机制等场景。使用时需注意空集合操作的安全性选择。

Deque（Double-ended Queue）是Java中一种支持在两端高效插入和删除元素的线性数据结构。它结合了栈和队列的特点，既能实现先进先出（FIFO），也能实现后进先出（LIFO）。理解Deque的关键在于掌握它的操作方向和使用场景。

支持两端操作

与普通队列只能在一端插入、另一端删除不同，Deque允许在队首和队尾同时进行添加和移除操作。

• addFirst(e)/offerFirst(e)：在队首插入元素
• addLast(e)/offerLast(e)：在队尾插入元素
• removeFirst()/pollFirst()：移除并返回队首元素
• removeLast()/pollLast()：移除并返回队尾元素
• getFirst()/peekFirst()：获取但不移除队首元素
• getLast()/peekLast()：获取但不移除队尾元素

这些方法提供了灵活的操作方式，可根据需要选择是否抛出异常或返回null。

可作为栈或队列使用

Deque能替代Stack类来实现栈功能，推荐使用push()、pop()、peek()方法模拟入栈、出栈和查看栈顶。

它也可以当作普通队列使用，通过add()（等价于addLast）入队，remove()（等价于removeFirst）出队。

Deque deque = new ArrayDeque<>();
deque.push("A"); // 入栈
deque.push("B");
System.out.println(deque.pop()); // 输出 B，符合LIFO

实现类选择：ArrayDeque 和 LinkedList

Java中常用的Deque实现有ArrayDeque和LinkedList。

• ArrayDeque：基于动态数组，随机访问效率高，不允许null元素，通常作为栈或双端队列的首选
• LinkedList：基于双向链表，支持null元素，除了Deque操作外还能作为List使用，但内存开销略大

如果只用于双端操作，优先考虑ArrayDeque，性能更优。

典型应用场景

Deque的灵活性使其适用于多种算法和业务场景。

• 滑动窗口问题：配合单调队列找出最大/最小值
• 回文判断：从两端逐个比较字符
• 表达式求值：用作操作符或操作数的临时存储
• 撤销机制：保存历史操作，支持前后导航

比如实现一个简单的浏览器前进后退功能，就可以用两个Deque分别保存“后退”和“前进”历史。

基本上就这些。掌握Deque的核心在于理解“双端”带来的操作自由度，以及根据需求选择合适的方法和实现类。不复杂但容易忽略细节，比如空集合调用removeFirst()会抛异常，而pollFirst()返回null。实际使用时注意判空即可。