Java 队列（Queue）简介与经典例子-拓冰建站

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); // 入队}
}