操作系统OPT算法(最佳页面替换算法)

import sun.plugin.javascript.navig.Link;
import java.util.*;
class Pair
{
    public Pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
    public int first;
    public int second;
}
// opt算法的思路是
// 将每个数字和它的出现了的索引的队列做成映射表
// 每次比较内存里面的元素的索引队列的对首元素谁最大
// 最大的那个滚
public class Main
{
    static void ListTrave(List<Integer> list)
    {
        System.out.print("list: ");
        for (int i = 0; i < list.size(); ++ i)
        {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
    }
    static void QueueTrave(Queue<Integer> q)
    {
        System.out.print("Queue:");
        Iterator<Integer> it = q.iterator();
        while(it.hasNext())
        {
            System.out.print(it.next() + " ");
        }
        System.out.println();
    }
    static void MapTrave(Map<Integer, Queue<Integer> > map)
    {
        System.out.println("map:");
        for (Integer i : map.keySet())
        {
            System.out.print(i + ": ");
            Iterator it = map.get(i).iterator();
            while(it.hasNext())
            {
                System.out.print(it.next() + " ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner (System.in);
        // 内存访问顺序
        System.out.println("内存的访问顺序：");
        int numPage = in.nextInt();
//        System.out.println(numPage);
        // 页面中断的次数
        int cnt = 0;
        // 内存块的数量
        System.out.println("内存的数量：");
        int numMemory = in.nextInt();
        System.out.println("输入内存：");
        Map<Integer, Queue<Integer> > map = new HashMap<>();
        // 把每个元素存一遍
        // 用队列的好处是 可以保证查询的效率是O(1)
        Queue<Integer> q = new LinkedList<>();
        // 存放当前内存中的元素
        List<Integer> list = new ArrayList<>();
        // 把每个元素和它的索引队列做成映射表
        for (int i = 0; i < numPage; ++ i)
        {
            int num = in.nextInt();
            q.add(num);
            if (map.containsKey(num))
            {
                Queue<Integer> queue = map.get(num);
                queue.add(i);
                map.put(num, queue);
            }
            else
            {
                Queue<Integer> queue = new LinkedList<>();
                queue.add(i);
                map.put(num, queue);
            }
        }
        // 检查
//        QueueTrave(q);
//        MapTrave(map);
        for (int i = 0; i < numPage; ++ i)
        {
            int num = q.poll();
            if (list.size() < numMemory)
            {
                if (!list.contains(num))
                {
                    list.add(num);
                    map.get(num).poll();
                    cnt ++;
                }
            }
            else
            {
                if (list.contains(num))
                {
                    // 这里是就算 内存里面存在这个元素 但是也是还要假替换的 就是
                    // 把这次新来的num的对应的队列的索引也删掉
                    map.get(num).poll();
                }
                else
                {
                    check((ArrayList<Integer>) list, map);
                    cnt ++;
                    list.add(num);
                    // 把num对应的索引删掉一个
                    map.get(num).poll();
                }
            }
//            ListTrave(list);
        }
//        System.out.println("cnt: " + cnt);
        System.out.printf("%.1f%%", (double)cnt / (double)numPage * 100);
    }
    // 返回那个要滚的数字
    static int check(ArrayList<Integer> list, Map<Integer, Queue<Integer> > map)
    {
//        System.out.println("enter:");
//        ListTrave(list);
//        MapTrave(map);
        // 最后要滚的数字 和 对应的索引
        // 先设置为list的第一个元素
        // 如果这个数字对应的队列映射为空那么 用负数代表索引 表示无穷远
        int t = list.get(0);    // t是内存中的数字
        int idx = 0;  // t对应的索引
        int t2 = map.get(t).size();  // 索引对应的数字对应的队列的大小
        int t3;                     // 队列第一个数字的索引
        // 判断是否为空的情况
        if (t2 == 0) t3 = -1;
        else t3 = map.get(t).peek();
//        System.out.println("t1 + idx + t2 + t3=" + t + " " + idx + " " + t2 + " " + t3);
        Pair num = new Pair(idx, t3);  // num存放需要删除的数字的索引和这个数字对应的队列的队首
        if (num.second == -1)  // 如果找到-1的后面的就不用找了
        {
            list.remove(num.first);  // remove是按照索引删除
            return list.get(num.first);
        }
//        System.out.println("t1 + idx + t2 + t3=" + t + " " + idx + " " + t2 + " " + t3);
        for (int i = 1; i < list.size(); ++ i)
        {
//            ListTrave(list);
            t = list.get(i);
            idx = i;
            t2 = map.get(t).size();
            if (t2 == 0) t3 = -1;
            else t3 = map.get(t).peek();
//            System.out.println("t1 + idx + t2 + t3=" + t + " " + idx + " " + t2 + " " + t3);
            if(t3 == -1)
            {
                list.remove(idx);
                return list.get(num.first);
            }
            else
            {
                // 让更远的代替
                if (num.second < t3)
                {
                    num = new Pair(idx, t3);
                }
            }
        }
        // 最后second最大的滚
        list.remove(num.first);
        return list.get(num.first);
    }
}