4- 队列（Queue）

队列的核心原则是 先进先出（First-in First-out, FIFO），即第一个进入队列的元素将是第一个被移除的元素。这类似于排队等候的情况，第一个排队的人最先得到服务。

队列的主要操作

1. enqueue: 将元素添加到队列的末尾。
2. dequeue: 移除并返回队列的第一个元素。

队列的附加操作

1. front: 返回队列的第一个元素但不移除它。
2. size: 返回队列中元素的数量。
3. isEmpty: 判断队列是否为空。

Java中的Queue接口

Java提供了一个Queue接口，该接口在java.util包中定义。常用的实现类包括LinkedList和PriorityQueue。该接口定义了上述的主要和附加操作。

LinkedList 类

LinkedList 是一个双向链表实现，它实现了 List 和 Deque 接口，后者是 Queue 接口的一个扩展。这意味着 LinkedList 不仅提供了队列的标准操作，还支持栈操作（如 push、pop）和双端队列操作（如双向入队和出队）。因此，LinkedList 是一种非常灵活的数据结构，可以用作普通队列、双端队列或栈。

PriorityQueue 类

PriorityQueue 是基于优先级堆实现的，它只实现了 Queue 接口。它通过元素的自然排序或者构造时指定的 Comparator 来决定元素的优先级。在 PriorityQueue 中，队列的头部是按指定排序准则最小（或最高优先级）的元素。每次出队（poll）操作都会移除这个最小元素。这种实现适合于需要按特定顺序处理元素的应用场景，如任务调度。

• 实现方式：LinkedList 基于链表，而 PriorityQueue 基于优先级堆。

• 性能：LinkedList 在入队（offer）、出队（poll）和获取队首元素（peek）操作上具有 O(1) 的时间复杂度。 PriorityQueue 在入队（offer）和出队（poll）操作上具有平均 O(log n) 的时间复杂度，其中 n 是队列中的元素数量。获取队首元素（peek）操作的时间复杂度为 O(1)。

• 用途：LinkedList 可用作普通队列、栈或双端队列，而 PriorityQueue 主要用于实现需要元素优先级的队列。

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

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1); // enqueue 入队
        queue.add(2);
        queue.add(3);

        System.out.println("Front element: " + queue.peek()); // front
        System.out.println("Queue size: " + queue.size()); // size

        while (!queue.isEmpty()) {
            System.out.println("Dequeued: " + queue.remove()); // dequeue 出队
        }
    }
}

队列的应用

1. 资源共享: 如打印机队列，多个任务按照先来先服务的顺序打印。
2. 多程序设计: 在操作系统中，进程调度通常使用队列来管理等待运行的进程。
3. 算法和数据结构: 队列在许多算法中作为基础组件，例如广度优先搜索（BFS）。

基于数组的队列实现（循环队列）

循环队列使用数组以循环的方式存储元素。它通过两个索引（front和rear）来跟踪队列的头和尾，并使用取模运算符（modulo operator）实现索引的环绕。

public class CircularQueue {
    private int[] data;
    private int front;
    private int rear;
    private int size;

    public CircularQueue(int capacity) {
        data = new int[capacity];
        front = 0;
        rear = 0;
        size = 0;
    }

    public boolean enqueue(int value) {
        if (size == data.length) {
            return false; // Queue is full
        }
        data[rear] = value;
        rear = (rear + 1) % data.length;
        size++;
        return true;
    }

    public Integer dequeue() {
        if (size == 0) {
            return null; // Queue is empty
        }
        int value = data[front];
        front = (front + 1) % data.length;
        size--;
        return value;
    }

    public int front() {
        if (size == 0) {
            return -1; // Queue is empty
        }
        return data[front];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

基于链表的队列实现

链表队列使用链表来存储元素，并通过头节点（head）和尾节点（tail）来跟踪队列的首尾。

public class LinkedListQueue {
    private static class Node {
        int value;
        Node next;
        Node(int value) {
            this.value = value;
        }
    }

    private Node head;
    private Node tail;
    private int size;

    public void enqueue(int value) {
        Node newNode = new Node(value);
        if (tail != null) {
            tail.next = newNode;
        }
        tail = newNode;
        if (head == null) {
            head = tail;
        }
        size++;
    }

    public Integer dequeue() {
        if (head == null) {
            return null; // Queue is empty
        }
        int value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }

    public int front() {
        if (head == null) {
            return -1; // Queue is empty
        }
        return head.value;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return head == null;
    }
}

轮转调度器（Round Robin Schedulers）

队列在任务调度中的应用

轮转调度器（Round Robin Schedulers）是操作系统中常用的一种任务调度算法，特别适用于时间共享系统。它的核心思想是将CPU时间片分配给每个任务，使得每个任务都有机会执行。轮转调度器使用队列来管理等待执行的任务，从而实现先进先出（FIFO）的处理顺序。

工作原理

1. 时间片分配: 系统给每个任务分配一个固定长度的时间片（Time Quantum），在该时间片内，任务可以独占CPU。
2. 队列管理: 所有的任务按照到达的顺序排入队列。调度器从队列的头部取出第一个任务，分配CPU时间片。
3. 执行与再入队: 如果任务在时间片内完成，则从队列中移除；否则，任务在时间片结束时被挂起，并重新加入队列的末尾，等待下一次分配时间片。

优点

• 公平性: 每个任务都有机会获得CPU时间，不会出现某些任务长期占用CPU的情况。
• 响应时间短: 适用于交互式系统，能够快速响应用户请求。

缺点：

• 上下文切换开销: 进程切换时需要保存和恢复上下文，频繁切换会导致系统开销增加。
• 不适用于实时系统: 无法保证高优先级任务的及时执行。

示例代码

以下是一个模拟轮转调度器的Java示例：

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

public class RoundRobinScheduler {
    private static class Task {
        String name;
        int burstTime;

        Task(String name, int burstTime) {
            this.name = name;
            this.burstTime = burstTime;
        }
    }

    public static void main(String[] args) {
        Queue<Task> queue = new LinkedList<>();
        queue.add(new Task("Task1", 4));
        queue.add(new Task("Task2", 3));
        queue.add(new Task("Task3", 2));

        int timeQuantum = 2; // Time slice

        while (!queue.isEmpty()) {
            Task currentTask = queue.poll();
            System.out.println("Executing " + currentTask.name);
            if (currentTask.burstTime > timeQuantum) {
                currentTask.burstTime -= timeQuantum;
                System.out.println(currentTask.name + " needs more time, re-adding to queue");
                queue.add(currentTask);
            } else {
                System.out.println(currentTask.name + " completed");
            }
        }
    }
}

在这个示例中，每个任务被分配了一个时间片，如果任务在时间片内未完成，则将其重新加入队列末尾。

迷宫探索算法

使用队列探索迷宫路径

迷宫探索算法使用队列来实现广度优先搜索（BFS），以系统地探索迷宫中的所有可能的路径。BFS能够找到从起点到终点的最短路径，适用于迷宫或图中的路径搜索。

工作原理

1. 初始化：从起点开始，标记起点为“已发现”并将其加入队列。
2. 探索队列：只要队列不为空，就从队列中取出一个位置进行检查。如果该位置是终点，则算法终止。
3. 扩展节点：对于当前位置的每个相邻位置，如果未被发现，则标记为“已发现”并加入队列。
4. 标记状态：继续从队列中取出下一个位置，重复步骤2和3。每个探索过的位置都标记为“已发现”，并不再进一步处理。
5. 终止条件：当队列为空或已找到终点时，算法结束。

标记状态

• 未知: 位置尚未被探索。
• 已发现: 位置已被发现并加入队列，但尚未完全处理。
• 已探索: 位置已被完全处理，不再需要处理。

特点

• 层次性探索: 通过队列管理，算法一层一层地扩展，直至找到目标或探索完所有可能路径，这有助于快速找到最短路径。
• 无回溯: 与深度优先搜索（DFS）不同，BFS在寻找路径时不会回溯，每个位置只被探索一次，这使得它在寻找最短路径问题中非常有效。
• 完备性: 只要存在从起点到终点的路径，BFS 一定能找到。
• 最优性: BFS 找到的路径一定是最短路径。
• 时间复杂度: $O(V+E)$，其中 V 是节点数，E 是边数。
• $O(V)$：这一部分代表算法需要至少访问每一个顶点（节点）一次。在最坏的情况下，每个节点都至少被访问一次（即使有的节点可能因为是隔离的而没有其他节点与其相连）。
• $O(E)$：每条边在算法执行过程中也至少被考虑一次。这是因为从任何一个节点出发，算法都需要检查它能直接到达的所有其他节点（即通过一条边直接连接的节点）。

示例代码

以下是一个迷宫探索算法的Java示例：

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

public class MazeSolver {
    private static class Position {
        int x, y;
        Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public boolean solveMaze(int[][] maze) {
        int rows = maze.length;
        int cols = maze[0].length;
        boolean[][] visited = new boolean[rows][cols];
        Queue<Position> queue = new LinkedList<>();

        // Starting point
        queue.add(new Position(0, 0));
        visited[0][0] = true;

        // Direction vectors for moving up, down, left, right
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            Position pos = queue.poll(); // 方向向量，表示上、下、左、右移动
            int x = pos.x;
            int y = pos.y;

            // Check if we have reached the goal
            if (x == rows - 1 && y == cols - 1) {
                return true;
            }

            // Explore neighbors
            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];

                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && maze[newX][newY] == 0 && !visited[newX][newY]) {
                    queue.add(new Position(newX, newY));
                    visited[newX][newY] = true;
                }
            }
        }

        return false;
    }
}

在这个示例中，迷宫使用二维数组表示，0表示可通行路径，1表示障碍。算法通过队列逐层探索迷宫路径，寻找从起点到终点的路径。

通过上述两个示例，我们可以看到队列在任务调度和路径探索中的重要应用。队列的先进先出（FIFO）特性在这些场景中非常有用，确保任务和路径的有序处理。