Java 队列介绍：从基础到高级应用 – wiki基地

作者： /

Java 队列介绍：从基础到高级应用

在 Java 编程中，队列（Queue）是一种重要的数据结构，它遵循“先进先出”（FIFO – First-In, First-Out）的原则。这意味着第一个进入队列的元素也将是第一个离开队列的。这种特性使得队列在许多场景中都非常有用，例如任务调度、消息传递和数据缓冲。本文将从基础概念出发，逐步深入到 Java 中队列的高级应用。

1. 队列的基础概念

1.1 什么是队列？

队列是一种线性数据结构，其操作被限制在两端：一端用于添加元素（入队，enqueue），称为队尾（rear）；另一端用于移除元素（出队，dequeue），称为队头（front）。

1.2 队列的基本操作

  • 入队 (enqueue)：将一个元素添加到队尾。
  • 出队 (dequeue)：从队头移除一个元素。
  • 查看队头 (peek/front)：查看队头元素，但不将其移除。
  • 判空 (isEmpty)：检查队列是否为空。
  • 判满 (isFull)：检查队列是否已满（通常在固定大小的队列中）。

2. Java 中的 Queue 接口

Java 集合框架提供了 java.util.Queue 接口，它定义了队列的通用行为。Queue 接口继承自 java.util.Collection 接口，并添加了专门用于队列操作的方法：

方法 抛出异常版本（失败时） 返回特殊值版本（失败时） 描述
添加元素 add(E e) offer(E e) 将元素插入到队列的尾部
移除元素 remove() poll() 移除并返回队列的头部
检查元素 element() peek() 返回队列的头部，但不移除

选择 add/remove/element 还是 offer/poll/peek？

  • 抛出异常版本 (add, remove, element)：当操作失败（例如，在容量受限的队列中添加元素但队列已满，或从空队列中移除/检查元素）时，会抛出异常。
  • 返回特殊值版本 (offer, poll, peek)：当操作失败时，不会抛出异常，而是返回一个特殊值（offer 返回 false，poll 和 peek 返回 null）。
  • 通常，在不希望因队列满或空而中断程序执行时，推荐使用 offer, poll, peek。

3. Queue 接口的常见实现类

Queue 是一个接口，不能直接实例化。Java 提供了多种实现，每种都有其特定的用途和性能特征。

3.1 LinkedList (作为 Queue 使用)

LinkedList 类实现了 List 和 Deque 接口，而 Deque 接口又扩展了 Queue 接口。因此，LinkedList 可以作为队列使用。

“`java
import java.util.LinkedList;
import java.util.Queue;

public class LinkedListQueue {
public static void main(String[] args) {
Queue queue = new LinkedList<>();

    queue.offer("Apple");
    queue.offer("Banana");
    queue.offer("Cherry");

    System.out.println("Queue: " + queue); // Output: Queue: [Apple, Banana, Cherry]
    System.out.println("Head of queue: " + queue.peek()); // Output: Head of queue: Apple

    System.out.println("Removed: " + queue.poll()); // Output: Removed: Apple
    System.out.println("Queue after poll: " + queue); // Output: Queue after poll: [Banana, Cherry]
}

}
“`
特点：
* 基于双向链表实现，因此在插入和删除操作上效率较高（O(1)）。
* 容量无限（受限于 JVM 内存）。
* 非线程安全。

3.2 ArrayDeque (作为 Queue 使用)

ArrayDeque 是一个双端队列（Deque），它提供了一种在两端高效插入和删除元素的方式。它比 LinkedList 在作为队列使用时更高效，因为它是基于数组实现的，并且避免了链表节点的开销。

“`java
import java.util.ArrayDeque;
import java.util.Queue;

public class ArrayDequeQueue {
public static void main(String[] args) {
Queue queue = new ArrayDeque<>();

    queue.offer(10);
    queue.offer(20);
    queue.offer(30);

    System.out.println("Queue: " + queue); // Output: Queue: [10, 20, 30]
    System.out.println("Head of queue: " + queue.peek()); // Output: Head of queue: 10

    System.out.println("Removed: " + queue.poll()); // Output: Removed: 10
    System.out.println("Queue after poll: " + queue); // Output: Queue after poll: [20, 30]
}

}
``
**特点：**
* 基于可变大小的数组实现，在大多数操作中提供 O(1) 的时间复杂度。
* 容量无限。
* 非线程安全。
* 推荐作为普通队列或栈使用，通常比LinkedList` 更优。

3.3 PriorityQueue (优先级队列)

PriorityQueue 实现了 Queue 接口，但它不是严格意义上的 FIFO 队列。它根据元素的自然顺序或构造时提供的 Comparator 来对元素进行排序，每次出队时总是移除优先级最高的元素（最小的或最大的）。

“`java
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueDemo {
public static void main(String[] args) {
Queue pq = new PriorityQueue<>(); // 默认是小顶堆

    pq.offer(5);
    pq.offer(1);
    pq.offer(10);
    pq.offer(3);

    System.out.println("PriorityQueue: " + pq); // Output might vary due to internal heap structure, e.g., [1, 3, 10, 5]

    while (!pq.isEmpty()) {
        System.out.println("Polling: " + pq.poll());
    }
    // Output:
    // Polling: 1
    // Polling: 3
    // Polling: 5
    // Polling: 10
}

}
``
**特点：**
* 基于二叉堆实现。
*offer和poll` 操作的时间复杂度为 O(log N)。
* 容量无限。
* 非线程安全。
* 适用于需要按优先级处理元素的场景。

4. BlockingQueue 接口 (并发队列)

在多线程环境中，普通的 Queue 实现（如 LinkedList 和 ArrayDeque）不是线程安全的。Java 的并发包 java.util.concurrent 提供了 BlockingQueue 接口，它扩展了 Queue 接口，并增加了阻塞操作。当队列满时，尝试入队的线程会阻塞；当队列空时，尝试出队的线程会阻塞。这在生产者-消费者模式中非常有用。

BlockingQueue 的主要方法：

| 方法

滚动至顶部