Java 队列（Queue）简介与经典例子

在这里插入图片描述

队列（Queue）是一种常见的数据结构，它按照先进先出（FIFO）的原则管理元素。在Java中，队列是一种广泛使用的数据结构，用于处理多种实际问题。本篇博客将介绍Java中的队列及其基本操作，并通过三个经典例子来说明队列的应用场景。

队列基本概念

队列是一种线性数据结构，其元素按照顺序排列。在队列中，新元素从一端（尾部）入队，而从另一端（头部）出队。这种操作顺序确保了先进入队列的元素先被取出，符合FIFO原则。

在Java中，队列的常见实现类包括LinkedList和ArrayDeque。Java提供了Queue接口，定义了队列的基本操作，例如enqueue（入队）、dequeue（出队）、peek（查看队头元素）等。

Queue<String> queue = new LinkedList<>(); // 使用LinkedList实现队列
queue.offer("Element1");
queue.offer("Element2");
String head = queue.poll(); // 出队

经典例子

1. 任务调度

在多线程环境中，任务调度通常使用队列来管理待执行的任务。新任务被加入队列尾部，而工作线程则从队列头部取出任务执行。这种方式能够确保任务按照提交的顺序依次执行，有效避免了线程竞争问题。

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class TaskScheduler {
    private final BlockingQueue<Runnable> taskQueue;

    public TaskScheduler() {
        this.taskQueue = new LinkedBlockingQueue<>();
    }

    public void submitTask(Runnable task) {
        taskQueue.offer(task);
    }

    public void start() {
        while (true) {
            try {
                Runnable task = taskQueue.take(); // 阻塞直到队列非空
                new Thread(task).start(); // 执行任务
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }
}

2. 广度优先搜索（BFS）

在图的广度优先搜索中，队列同样扮演重要角色。从起始节点开始，依次将相邻未访问过的节点加入队列，然后从队列中取出节点进行访问。这样可以确保按照层次遍历图的节点，找到最短路径等问题。

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

public class BreadthFirstSearch {
    public void bfs(Graph graph, int start) {
        boolean[] visited = new boolean[graph.getVertexCount()];
        Queue<Integer> queue = new LinkedList<>();

        visited[start] = true;
        queue.offer(start);

        while (!queue.isEmpty()) {
            int currentVertex = queue.poll();
            System.out.print(currentVertex + " ");

            for (int neighbor : graph.getNeighbors(currentVertex)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }
}

3. 缓存管理

队列也常用于实现缓存，特别是在限制缓存大小时。新数据被加入队尾，而当缓存达到最大容量时，最老的数据从队头被移除，确保缓存大小始终受限。

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

public class CacheManager<T> {
    private final Queue<T> cache;
    private final int maxSize;

    public CacheManager(int maxSize) {
        this.cache = new LinkedList<>();
        this.maxSize = maxSize;
    }

    public void addToCache(T item) {
        if (cache.size() >= maxSize) {
            cache.poll(); // 移除队头元素
        }
        cache.offer(item); // 入队
    }
}