Java队列(Queue)用法详解

队列(Queue)是一种常用的线性数据结构，遵循先进先出(FIFO, First-In-First-Out)的原则，即最先添加的元素最先被移除。本文将详细介绍Java中队列的实现、常用方法以及在ACM算法竞赛中的应用场景。

一、队列的基本概念

1.1 队列的定义

队列是一种特殊的线性表，它只允许在表的前端（队头）进行删除操作，而在表的后端（队尾）进行插入操作。

1.2 队列的特点

  • 先进先出(FIFO): 最先进入队列的元素最先被移除
  • 单向操作: 只能从队尾插入，从队头删除
  • 线性结构: 元素之间是一对一的关系

1.3 队列的基本操作

  • 入队(enqueue): 将元素添加到队列的末尾
  • 出队(dequeue): 从队列的开头移除元素
  • 查看队首元素(peek): 查看队列开头的元素但不移除
  • 判断队列是否为空(isEmpty): 检查队列中是否有元素

1.4 队列的结构示意图

1
2
3
4
5
6
       入队                                出队
        ↓                                  ↑
+-----+-----+-----+-----+-----+-----+
|  6  |  5  |  4  |  3  |  2  |  1  |  -> 队列
+-----+-----+-----+-----+-----+-----+
 队尾                              队头

二、Java中的队列接口与实现

2.1 Queue接口

Java中的Queue是一个接口，位于java.util包中，它扩展了Collection接口。Queue接口定义了队列的基本操作。

2.1.1 Queue接口的主要方法

方法 描述 队列为空时的行为
boolean add(E e) 将元素添加到队列尾部 抛出异常
boolean offer(E e) 将元素添加到队列尾部 返回false
E remove() 移除并返回队列头部的元素 抛出异常
E poll() 移除并返回队列头部的元素 返回null
E element() 返回队列头部的元素但不移除 抛出异常
E peek() 返回队列头部的元素但不移除 返回null

2.2 常用的Queue实现类

2.2.1 LinkedList

LinkedList是Queue接口的一个实现，它基于链表实现，适合频繁的插入和删除操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.LinkedList;
import java.util.Queue;

public class LinkedListQueueExample {
    public static void main(String[] args) {
        // 创建队列
        Queue<String> queue = new LinkedList<>();
        
        // 添加元素
        queue.offer("Java");
        queue.offer("Python");
        queue.offer("C++");
        
        System.out.println("队列: " + queue);
        
        // 查看队首元素
        System.out.println("队首元素: " + queue.peek());
        
        // 移除队首元素
        System.out.println("移除的元素: " + queue.poll());
        
        // 再次查看队列
        System.out.println("移除后的队列: " + queue);
        
        // 判断队列是否为空
        System.out.println("队列是否为空: " + queue.isEmpty());
        
        // 获取队列大小
        System.out.println("队列大小: " + queue.size());
    }
}

输出结果：

1
2
3
4
5
6
队列: [Java, Python, C++]
队首元素: Java
移除的元素: Java
移除后的队列: [Python, C++]
队列是否为空: false
队列大小: 2

2.2.2 ArrayDeque

ArrayDeque是基于可调整大小的数组实现的双端队列，它比LinkedList有更好的性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.ArrayDeque;
import java.util.Queue;

public class ArrayDequeExample {
    public static void main(String[] args) {
        // 创建队列
        Queue<Integer> queue = new ArrayDeque<>();
        
        // 添加元素
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);
        
        System.out.println("队列: " + queue);
        
        // 查看队首元素
        System.out.println("队首元素: " + queue.peek());
        
        // 移除队首元素
        System.out.println("移除的元素: " + queue.poll());
        
        // 再次查看队列
        System.out.println("移除后的队列: " + queue);
    }
}

输出结果：

1
2
3
4
队列: [10, 20, 30]
队首元素: 10
移除的元素: 10
移除后的队列: [20, 30]

2.2.3 PriorityQueue

PriorityQueue是一个基于优先级堆的优先队列实现，元素按照自然顺序或者自定义的Comparator进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建优先队列（小顶堆）
        Queue<Integer> minHeap = new PriorityQueue<>();
        
        // 添加元素
        minHeap.offer(30);
        minHeap.offer(10);
        minHeap.offer(20);
        
        System.out.println("优先队列: " + minHeap);
        
        // 查看队首元素（最小值）
        System.out.println("队首元素: " + minHeap.peek());
        
        // 移除队首元素
        System.out.println("移除的元素: " + minHeap.poll());
        
        // 再次查看队列
        System.out.println("移除后的队列: " + minHeap);
        
        // 创建大顶堆
        Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        
        // 添加元素
        maxHeap.offer(30);
        maxHeap.offer(10);
        maxHeap.offer(20);
        
        System.out.println("\n大顶堆: " + maxHeap);
        
        // 查看队首元素（最大值）
        System.out.println("队首元素: " + maxHeap.peek());
        
        // 移除队首元素
        System.out.println("移除的元素: " + maxHeap.poll());
        
        // 再次查看队列
        System.out.println("移除后的队列: " + maxHeap);
    }
}

输出结果：

1
2
3
4
5
6
7
8
9
优先队列: [10, 30, 20]
队首元素: 10
移除的元素: 10
移除后的队列: [20, 30]

大顶堆: [30, 10, 20]
队首元素: 30
移除的元素: 30
移除后的队列: [20, 10]

2.3 Deque接口（双端队列）

Deque接口扩展了Queue接口，支持在队列的两端进行插入和删除操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.ArrayDeque;
import java.util.Deque;

public class DequeExample {
    public static void main(String[] args) {
        // 创建双端队列
        Deque<String> deque = new ArrayDeque<>();
        
        // 在队尾添加元素
        deque.offerLast("Java");
        deque.offerLast("Python");
        
        // 在队首添加元素
        deque.offerFirst("C++");
        
        System.out.println("双端队列: " + deque);
        
        // 查看队首和队尾元素
        System.out.println("队首元素: " + deque.peekFirst());
        System.out.println("队尾元素: " + deque.peekLast());
        
        // 移除队首和队尾元素
        System.out.println("移除队首元素: " + deque.pollFirst());
        System.out.println("移除队尾元素: " + deque.pollLast());
        
        // 再次查看队列
        System.out.println("移除后的队列: " + deque);
    }
}

输出结果：

1
2
3
4
5
6
双端队列: [C++, Java, Python]
队首元素: C++
队尾元素: Python
移除队首元素: C++
移除队尾元素: Python
移除后的队列: [Java]

三、队列在ACM算法中的应用

3.1 广度优先搜索(BFS)

BFS是图论中的一种搜索算法，它从图的某一节点开始，先访问该节点的所有邻接节点，然后再按照同样的方法访问这些邻接节点的邻接节点。队列是实现BFS的核心数据结构。

3.1.1 迷宫问题

以下是一个使用BFS解决迷宫最短路径问题的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.LinkedList;
import java.util.Queue;

public class MazeBFS {
    // 四个方向：上、右、下、左
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
    public static int shortestPath(char[][] maze, int[] start, int[] end) {
        int rows = maze.length;
        int cols = maze[0].length;
        
        // 标记已访问的位置
        boolean[][] visited = new boolean[rows][cols];
        
        // 创建队列，存储位置和距离
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{start[0], start[1], 0}); // {行, 列, 距离}
        visited[start[0]][start[1]] = true;
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];
            int distance = current[2];
            
            // 如果到达终点
            if (row == end[0] && col == end[1]) {
                return distance;
            }
            
            // 尝试四个方向
            for (int[] dir : DIRECTIONS) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                
                // 检查新位置是否有效
                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols 
                    && maze[newRow][newCol] == '.' && !visited[newRow][newCol]) {
                    visited[newRow][newCol] = true;
                    queue.offer(new int[]{newRow, newCol, distance + 1});
                }
            }
        }
        
        return -1; // 无法到达终点
    }
    
    public static void main(String[] args) {
        char[][] maze = {
            {'.', '.', '#', '#', '.'},
            {'#', '.', '.', '#', '.'},
            {'.', '#', '.', '.', '.'},
            {'.', '.', '#', '#', '.'},
            {'#', '.', '.', '.', '.'}
        };
        
        int[] start = {0, 0};
        int[] end = {4, 4};
        
        int shortestDistance = shortestPath(maze, start, end);
        System.out.println("从起点到终点的最短距离: " + shortestDistance);
    }
}

3.2 优先队列在贪心算法中的应用

优先队列常用于贪心算法中，可以高效地获取当前最优选择。

3.2.1 Dijkstra算法

Dijkstra算法是一种求解单源最短路径的经典算法，它使用优先队列来选择当前距离最小的节点进行扩展。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.util.*;

public class DijkstraAlgorithm {
    static class Edge {
        int to, weight;
        
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    
    static class Node {
        int vertex, distance;
        
        Node(int vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
    }
    
    public static int[] dijkstra(List<List<Edge>> graph, int start) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        // 使用优先队列，按照距离排序
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.distance - b.distance);
        pq.offer(new Node(start, 0));
        
        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int u = current.vertex;
            int d = current.distance;
            
            // 如果当前距离大于已知最短距离，跳过
            if (d > dist[u]) continue;
            
            // 遍历所有邻接节点
            for (Edge edge : graph.get(u)) {
                int v = edge.to;
                int weight = edge.weight;
                
                // 如果找到更短的路径
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new Node(v, dist[v]));
                }
            }
        }
        
        return dist;
    }
    
    public static void main(String[] args) {
        int n = 5; // 节点数量
        List<List<Edge>> graph = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 添加边
        graph.get(0).add(new Edge(1, 10));
        graph.get(0).add(new Edge(2, 5));
        graph.get(1).add(new Edge(3, 1));
        graph.get(1).add(new Edge(2, 2));
        graph.get(2).add(new Edge(1, 3));
        graph.get(2).add(new Edge(3, 9));
        graph.get(2).add(new Edge(4, 2));
        graph.get(3).add(new Edge(4, 4));
        graph.get(4).add(new Edge(3, 6));
        
        int start = 0;
        int[] distances = dijkstra(graph, start);
        
        System.out.println("从节点 " + start + " 到各节点的最短距离：");
        for (int i = 0; i < n; i++) {
            System.out.println("节点 " + i + ": " + distances[i]);
        }
    }
}

3.2.2 贪心算法解决会议室安排问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;

public class MeetingRooms {
    static class Meeting {
        int start, end;
        
        Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    
    public static int minMeetingRooms(Meeting[] meetings) {
        if (meetings == null || meetings.length == 0) return 0;
        
        // 按照开始时间排序
        Arrays.sort(meetings, (a, b) -> a.start - b.start);
        
        // 使用优先队列（小顶堆）跟踪当前会议室的结束时间
        PriorityQueue<Integer> rooms = new PriorityQueue<>();
        
        for (Meeting meeting : meetings) {
            // 如果当前最早结束的会议室已经结束，可以重用
            if (!rooms.isEmpty() && rooms.peek() <= meeting.start) {
                rooms.poll();
            }
            
            // 分配一个会议室（添加结束时间到队列）
            rooms.offer(meeting.end);
        }
        
        // 队列大小即为所需的会议室数量
        return rooms.size();
    }
    
    public static void main(String[] args) {
        Meeting[] meetings = {
            new Meeting(0, 30),
            new Meeting(5, 10),
            new Meeting(15, 20)
        };
        
        int rooms = minMeetingRooms(meetings);
        System.out.println("需要的会议室数量: " + rooms);
    }
}

3.3 双端队列在滑动窗口问题中的应用

双端队列（Deque）在处理滑动窗口问题时非常有用，可以在O(1)时间内获取窗口中的最大值或最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.*;

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) return new int[0];
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        int ri = 0;
        
        // 使用双端队列存储元素的索引
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < nums.length; i++) {
            // 移除队列中所有小于当前元素的值（它们不可能是最大值）
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            // 添加当前元素索引到队列
            deque.offerLast(i);
            
            // 移除超出窗口范围的元素
            if (deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            
            // 当窗口大小达到k时，记录最大值
            if (i >= k - 1) {
                result[ri++] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        
        int[] result = maxSlidingWindow(nums, k);
        
        System.out.println("滑动窗口最大值: " + Arrays.toString(result));
    }
}

四、队列的性能比较与选择

4.1 不同队列实现的性能特点

实现类 底层数据结构 特点 适用场景
LinkedList 双向链表 插入和删除操作O(1)，但需要额外的内存开销 频繁插入删除，不关心随机访问性能
ArrayDeque 循环数组 比LinkedList更高效，没有链表的额外开销 一般用途的队列，双端队列操作
PriorityQueue 二叉堆 插入和删除操作O(log n)，但能保证取出的是优先级最高的元素 需要按优先级处理元素的场景

4.2 队列选择建议

  1. 一般用途：使用ArrayDeque，它比LinkedList有更好的性能，除非需要频繁在队列中间进行操作。
  2. 需要优先级：使用PriorityQueue，它能自动按照优先级排序。
  3. 双端操作：使用ArrayDeque作为Deque的实现，它在两端的操作都很高效。
  4. 线程安全：考虑使用ConcurrentLinkedQueue或BlockingQueue的实现类，如LinkedBlockingQueue。

五、总结

队列是一种重要的数据结构，在Java中有多种实现方式，每种实现都有其特点和适用场景。在ACM算法竞赛中，队列常用于BFS、贪心算法和滑动窗口等问题的解决。掌握队列的使用方法和选择合适的队列实现，对提高算法效率和代码质量有很大帮助。

在实际应用中，应根据具体需求选择合适的队列实现，并注意队列操作的时间复杂度和空间复杂度，以优化程序性能。