Deque（双端队列）详解

---

一、是什么？

Deque（Double Ended Queue）是Java中的双端队列接口（java.util.Deque），支持在队列的头部和尾部同时插入、删除和查看元素。它同时具备栈（Stack）和队列（Queue）的特性，是Queue的子接口。
主要实现类：

• ArrayDeque：基于数组实现，性能高效（JDK推荐使用）。
• LinkedList：基于链表实现，支持更多操作（如索引访问）。

二、解决什么问题

1. 灵活操作两端数据：传统队列（Queue）只能从尾部插入、头部删除；栈（Stack）只能操作顶部。Deque允许在两端操作，适应更复杂的场景。
2. 替代Stack类：Java的Stack类因设计问题（如同步开销）不推荐使用，Deque的ArrayDeque是更好的栈替代品。
3. 高效实现滑动窗口算法：如LeetCode中的子数组问题，需快速操作窗口两端元素。

三、核心方法

方法	头部操作	尾部操作	说明
插入	addFirst(e)	addLast(e)	失败时抛出异常
	offerFirst(e)	offerLast(e)	失败时返回false
删除	removeFirst()	removeLast()	空队列时抛出异常
	pollFirst()	pollLast()	空队列时返回null
查看（不删除）	getFirst()	getLast()	空队列时抛出异常
	peekFirst()	peekLast()	空队列时返回null
栈操作	push(e)	-	等效于addFirst(e)
	pop()	-	等效于removeFirst()

四、应用场景

1. 滑动窗口算法（LeetCode高频考点）

   • 场景：求数组的滑动窗口最大值（如LeetCode 239）。
   • 优势：用pollFirst()移除旧元素，offerLast()添加新元素，peekFirst()获取最大值。

   Deque<Integer> deque = new ArrayDeque<>();  
   for (int i = 0; i < nums.length; i++) {  
       // 移除窗口外元素  
       while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {  
           deque.pollFirst();  
       }  
       // 移除尾部小于当前值的元素（维护单调递减队列）  
       while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {  
           deque.pollLast();  
       }  
       deque.offerLast(i); // 添加当前索引  
       if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];  
   }

2. 实现栈（Stack）

   • 替代Stack类，性能更优（ArrayDeque无同步开销）。

   Deque<Integer> stack = new ArrayDeque<>();  
   stack.push(1); // 压栈  
   stack.push(2);  
   int top = stack.pop(); // 弹栈 → 2

3. 回文检测

   • 场景：检查字符串是否为回文（如“aba”）。
   • 方法：从两端同时取出字符比较。

   Deque<Character> deque = new ArrayDeque<>();  
   for (char c : s.toCharArray()) deque.addLast(c);  
   while (deque.size() > 1) {  
       if (!deque.removeFirst().equals(deque.removeLast())) return false;  
   }

4. BFS（广度优先搜索）

   • 场景：树的层序遍历（如LeetCode 102）。
   • 优势：用pollFirst()取当前层节点，offerLast()存下一层节点。

五、Java示例

import java.util.ArrayDeque;  
import java.util.Deque;  

public class DequeDemo {  
    public static void main(String[] args) {  
        // 1. 作为队列使用（先进先出）  
        Deque<Integer> queue = new ArrayDeque<>();  
        queue.offerLast(1); // 尾部插入  
        queue.offerLast(2);  
        System.out.println(queue.pollFirst()); // 头部移除 → 1  

        // 2. 作为栈使用（后进先出）  
        Deque<Integer> stack = new ArrayDeque<>();  
        stack.push(1); // 等效于 addFirst(1)  
        stack.push(2);  
        System.out.println(stack.pop()); // 等效于 removeFirst() → 2  

        // 3. 双端操作  
        Deque<String> deque = new ArrayDeque<>();  
        deque.offerFirst("A"); // 头部插入  
        deque.offerLast("B");  // 尾部插入  
        System.out.println(deque.pollFirst()); // 头部移除 → "A"  
        System.out.println(deque.pollLast());  // 尾部移除 → "B"  
    }  
}

六、重要注意事项

1. 空队列操作：
   • 使用removeFirst()/getFirst()在空队列时会抛NoSuchElementException，优先用pollFirst()/peekFirst()。
2. 容量限制：
   • ArrayDeque有初始容量（默认16），扩容时性能开销较大，预估数据量可指定初始大小：

     Deque<Integer> deque = new ArrayDeque<>(1000); // 指定容量

3. 线程安全：
   • ArrayDeque和LinkedList均非线程安全，多线程环境用ConcurrentLinkedDeque。
4. 实现类选择：
   • 高频插入/删除 → ArrayDeque（内存连续，CPU缓存友好）。
   • 需要索引访问/频繁中间插入 → LinkedList。

七、总结

Deque是解决双端操作需求的核心工具，尤其适合：

• 算法题：滑动窗口、BFS、栈实现。
• 性能敏感场景：用ArrayDeque替代Stack或LinkedList。
• 代码简洁性：单一接口统一栈和队列操作，减少代码冗余。

📊 Deque操作可视化：