Java Queue接口

概述

Queue（队列）是Java集合框架中定义在java.util包下的接口，代表一种先进先出（FIFO）的线性数据结构。队列通常用于处理需要按顺序执行的任务，例如任务调度、消息传递等场景。Queue接口扩展了Collection接口，并添加了特定的插入、删除和检查操作。

队列的主要特点包括：

• 元素从队列尾部（rear）插入，从队列头部（front）移除。
• 支持多种实现，如LinkedList、PriorityQueue、ArrayDeque等。
• 提供两组方法：一组在操作失败时抛出异常，另一组返回特殊值（如null或false）。

Queue接口的核心方法

Queue接口定义了以下关键方法：

方法	描述	抛出异常	返回特殊值
add(e)	插入元素	队列满时抛出IllegalStateException	offer(e)返回false
remove()	移除并返回头部元素	队列空时抛出NoSuchElementException	poll()返回null
element()	返回头部元素（不移除）	队列空时抛出NoSuchElementException	peek()返回null

代码示例：基本操作

以下示例展示如何使用LinkedList实现Queue：

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        
        // 插入元素
        queue.add("A");
        queue.offer("B"); // 推荐使用offer避免异常
        
        // 获取头部元素
        System.out.println("头部元素（element）: " + queue.element()); // A
        System.out.println("头部元素（peek）: " + queue.peek());      // A
        
        // 移除元素
        System.out.println("移除元素（remove）: " + queue.remove()); // A
        System.out.println("移除元素（poll）: " + queue.poll());     // B
        
        // 空队列操作
        System.out.println("poll空队列: " + queue.poll());          // null
        // queue.remove(); // 抛出NoSuchElementException
    }
}

输出：

头部元素（element）: A
头部元素（peek）: A
移除元素（remove）: A
移除元素（poll）: B
poll空队列: null

Queue的实现类

Java提供了多种Queue的实现类，适用于不同场景：

1. LinkedList

• 基于链表实现，支持List和Deque接口。
• 允许null元素。
• 示例：见上文基本操作示例。

2. PriorityQueue

• 基于优先级堆（通常是最小堆）实现。
• 元素按自然顺序或Comparator排序。
• 示例：任务调度系统。

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        Queue<Integer> pq = new PriorityQueue<>();
        pq.offer(5);
        pq.offer(1);
        pq.offer(3);
        
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 输出：1, 3, 5
        }
    }
}

3. ArrayDeque

• 基于可调整大小的数组实现，性能优于LinkedList。
• 不支持null元素。
• 示例：实现栈或双端队列。

实际应用场景

案例1：任务调度

队列常用于按顺序处理任务。例如，打印任务队列：

Queue<String> printQueue = new LinkedList<>();
printQueue.offer("Document1.pdf");
printQueue.offer("Document2.pdf");

while (!printQueue.isEmpty()) {
    System.out.println("正在打印: " + printQueue.poll());
}

案例2：广度优先搜索（BFS）

在算法中，队列是BFS的核心数据结构：

import java.util.LinkedList;
import java.util.Queue;

public class BFSTraversal {
    public static void bfs(int[][] graph, int start) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.length];
        
        queue.offer(start);
        visited[start] = true;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.println("访问节点: " + node);
            
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    queue.offer(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }
}

队列类型对比

classDiagram Queue <|-- Deque Queue <|-- BlockingQueue Queue <|-- AbstractQueue Deque <|-- ArrayDeque Deque <|-- LinkedList AbstractQueue <|-- PriorityQueue

常见问题

1. Queue和Deque的区别？

• Queue是严格的FIFO结构。
• Deque（双端队列）允许从两端插入/删除，可实现栈或队列。

2. 如何选择实现类？

• 需要普通队列：LinkedList或ArrayDeque。
• 需要优先级：PriorityQueue。
• 需要线程安全：BlockingQueue实现类（如ArrayBlockingQueue）。

总结

• Queue是FIFO数据结构，核心方法包括offer/poll/peek。
• 主要实现类有LinkedList、PriorityQueue、ArrayDeque。
• 应用场景包括任务调度、BFS算法等。