// 第 8 周 – 实践课练习的参考答案
// 运行：java Exercises08.java
import java.util.ArrayDeque;
import java.util.Queue;

public class Exercises08 {

    // E1. 代码阅读（旧试卷中的题目）：n = 10 时输出什么？
    static void fibonacciQueue(int n) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(0);
        q.offer(1);
        for (int i = 0; i < n; i++) {
            int a = q.poll();
            System.out.print(a + " ");
            int b = q.peek();
            q.offer(a + b);
        }
        System.out.println();
    }

    // E2. 约瑟夫问题：n 个人围成一圈，每数到第 k 个人就淘汰。最后剩下谁？
    static int josephus(int n, int k) {
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) q.offer(i);
        StringBuilder order = new StringBuilder();
        while (q.size() > 1) {
            for (int i = 1; i < k; i++) q.offer(q.poll()); // 把 k-1 个人送到队尾
            order.append(q.poll()).append(' ');             // 第 k 个人被淘汰
        }
        System.out.print("order of elimination: " + order);
        return q.poll();
    }

    // E3. 时间片轮转调度：每个进程最多运行 'quantum' 时间，然后回到队尾
    static void roundRobin(String[] names, int[] burst, int quantum) {
        Queue<Integer> q = new ArrayDeque<>();
        int[] left = burst.clone();
        for (int i = 0; i < names.length; i++) q.offer(i);
        int time = 0;
        while (!q.isEmpty()) {
            int p = q.poll();
            int run = Math.min(quantum, left[p]);
            time += run;
            left[p] -= run;
            if (left[p] > 0) q.offer(p);
            else System.out.print(names[p] + " done (t=" + time + ")  ");
        }
        System.out.println();
    }

    // E4. 借助栈把队列逆序
    static Queue<Integer> reverse(Queue<Integer> q) {
        ArrayDeque<Integer> st = new ArrayDeque<>();
        while (!q.isEmpty()) st.push(q.poll());
        while (!st.isEmpty()) q.offer(st.pop());
        return q;
    }

    // E5. 代码阅读：字母 = 入队，'*' = 出队并输出
    static String trace(String ops) {
        Queue<Character> q = new ArrayDeque<>();
        StringBuilder out = new StringBuilder();
        for (char c : ops.toCharArray()) {
            if (c == '*') out.append(q.poll());
            else if (c != ' ') q.offer(c);
        }
        return out.toString();
    }

    // E6. 用队列持续计算最近 k 个数据的平均值（滑动平均）– 每个数据 O(1)
    static void movingAverage(int[] data, int k) {
        Queue<Integer> window = new ArrayDeque<>();
        int sum = 0;
        for (int x : data) {
            window.offer(x);
            sum += x;
            if (window.size() > k) sum -= window.poll();
            System.out.printf("%.1f ", (double) sum / window.size());
        }
        System.out.println();
    }

    public static void main(String[] args) {
        System.out.print("E1. ");
        fibonacciQueue(10);
        System.out.print("E2. ");
        System.out.println("-> survivor: " + josephus(7, 3));
        System.out.print("E3. ");
        roundRobin(new String[] { "P1", "P2", "P3" }, new int[] { 5, 2, 4 }, 2);
        Queue<Integer> q = new ArrayDeque<>(java.util.List.of(1, 2, 3, 4));
        System.out.println("E4. reverse([1,2,3,4]) = " + reverse(q));
        System.out.println("E5. trace(\"D A T * A * S * T R * U C * T\") = " + trace("D A T * A * S * T R * U C * T"));
        System.out.print("E6. moving average (k=3): ");
        movingAverage(new int[] { 10, 20, 30, 40, 50, 60 }, 3);
    }
}