跳到主要内容

Queue 与 Deque

问题​

Java 中有哪些队列实现？PriorityQueue、ArrayDeque、BlockingQueue 各有什么特点？

答案​

Queue 接口​

Queue 是先进先出（FIFO）的集合，提供两套 API：

操作抛异常返回特殊值
插入add(e) → IllegalStateExceptionoffer(e) → false
移除remove() → NoSuchElementExceptionpoll() → null
查看element() → NoSuchElementExceptionpeek() → null

PriorityQueue（优先队列）​

基于最小堆（数组实现），元素按自然顺序或 Comparator 排序，队首始终是最小元素：

PriorityQueueDemo.java
// 最小堆（默认）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(3);
minHeap.offer(1);
minHeap.offer(2);
minHeap.poll(); // 1（最小的先出）
minHeap.poll(); // 2

// 最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(3);
maxHeap.offer(1);
maxHeap.offer(2);
maxHeap.poll(); // 3（最大的先出）

// 自定义排序
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
操作时间复杂度
offer(e) / add(e)O(log⁡n)O(\log n)
poll() / remove()O(log⁡n)O(\log n)
peek()O(1)O(1)
remove(Object)O(n)O(n)
注意事项
  • PriorityQueue 不是线程安全的，多线程用 PriorityBlockingQueue
  • 不保证迭代顺序：iterator() 遍历不是按优先级顺序
  • 不允许 null 元素

ArrayDeque（双端队列）​

基于循环数组实现，既可以当栈用也可以当队列用，性能优于 LinkedList 和 Stack：

ArrayDequeDemo.java
// 当队列使用（FIFO）
Deque<String> queue = new ArrayDeque<>();
queue.offer("a");       // 入队（尾部）
queue.offer("b");
queue.poll();            // "a"（头部出队）

// 当栈使用（LIFO）— 替代 Stack 类
Deque<String> stack = new ArrayDeque<>();
stack.push("a");         // 入栈（头部）
stack.push("b");
stack.pop();             // "b"（头部出栈）

为什么推荐 ArrayDeque 替代 Stack 和 LinkedList？

维度ArrayDequeLinkedListStack
底层结构循环数组双向链表数组
缓存友好好差好
内存开销低高（每节点两个指针）低
null 支持不允许允许允许
线程安全否否是（synchronized）
推荐度首选仅需 List+Deque 时已废弃

BlockingQueue（阻塞队列）​

线程安全的队列，当队列为空时取操作阻塞，当队列满时放操作阻塞。是生产者-消费者模式的核心：

实现类底层结构有界特点
ArrayBlockingQueue数组必须指定容量公平/非公平锁
LinkedBlockingQueue链表可选（默认 MAX）两把锁（读写分离）
PriorityBlockingQueue堆无界优先级排序
SynchronousQueue无0 容量直接传递（Executors.newCachedThreadPool 使用）
DelayQueue堆无界延迟获取（定时任务）
BlockingQueueDemo.java
// 生产者-消费者模式
BlockingQueue<String> queue = new ArrayBlockingQueue<>(10);

// 生产者线程
new Thread(() -> {
    try {
        queue.put("message"); // 队列满时阻塞
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();

// 消费者线程
new Thread(() -> {
    try {
        String msg = queue.take(); // 队列空时阻塞
        System.out.println("收到: " + msg);
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();

常见面试问题​

Q1: Stack 为什么不推荐使用？用什么替代？​

答案：

Stack 继承自 Vector，所有方法都有 synchronized，单线程使用有不必要的性能开销。且 Stack 继承 Vector 是设计错误（栈不应该有 get(i) 等随机访问方法）。替代方案：Deque<E> stack = new ArrayDeque<>()。

Q2: ArrayBlockingQueue 和 LinkedBlockingQueue 的区别？​

答案：

维度ArrayBlockingQueueLinkedBlockingQueue
底层固定数组链表
容量必须指定可选（默认 Integer.MAX_VALUE）
锁一把锁两把锁（putLock + takeLock）
GC无额外对象每次 put 创建 Node 对象
性能中等高并发下更好（读写分离）

Q3: PriorityQueue 的底层实现？​

答案：

基于数组实现的最小堆（完全二叉树）。对于数组下标 i 的节点：

  • 父节点：(i - 1) / 2
  • 左孩子：2 * i + 1
  • 右孩子：2 * i + 2

插入时将元素放到数组末尾，然后上浮（sift up）；删除堆顶时将末尾元素放到堆顶，然后下沉（sift down）。

Q4: SynchronousQueue 有什么用？​

答案：

SynchronousQueue 不存储元素（容量为 0），每个 put 必须等待对应的 take，反之亦然。相当于一个直接传递的管道。Executors.newCachedThreadPool() 内部使用 SynchronousQueue，新任务到来时直接传递给空闲线程或创建新线程。

相关链接​