import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Replacement{
	private int n;//页面数
	private int m;//内存块数
	private double rate;//中断率
	private List<Integer> block=new ArrayList<Integer>();
	private List<Integer> page=new ArrayList<Integer>();
	
	public void init() {
		Scanner in=new Scanner(System.in);
		System.out.println("请输入进程的页面数：");
		n=in.nextInt();
		System.out.println("请输入已在内存中分配的块数：");
		m=in.nextInt();
		System.out.println("请输入程序访问内存的页面顺序：（输入完毕请以“/”结束并回车）");
		while(in.hasNextInt()) {
			page.add(in.nextInt());
		}
	}
	
	public void OPT() {
		int s=0;//中断次数
		int MAX=1000;
		int index=-2;//最久时间不会用到
		int size=page.size();//即访问次数
		double rate;//中断率
		System.out.println("***************Optimal Algorithm***************");
		for(int i=0;i<m;i++) {
			block.add(page.get(i));
			s++;
			System.out.println(block);
		}
		for(int i=0;i<m;i++) {
			page.remove(0);
		}
		while(page.size()!=0){
			FIRST_LOOP:
			for(int i=0;i<m;i++) {
				for(int k=0;k<m;k++) {
					if(block.get(k)==page.get(0)) {
						page.remove(0);
						break FIRST_LOOP;
					}
				}
				for(int k=0;k<m;k++) {
					if(page.indexOf(block.get(k))==-1) {
						MAX=block.get(k);
						break FIRST_LOOP;
					}
				}
				if(page.indexOf(block.get(i))>index) {
					index=page.indexOf(block.get(i));
				}
			}
			for(int i=0;i<m;i++) {
				if((block.get(i)==MAX)||((index!=-2)&&(block.get(i)==page.get(index)))) {
					block.set(i, page.get(0));
					s++;
					page.remove(0);
					MAX=1000;
					index=-2;
					break;
				}
			}
			System.out.println(block);
		}
		rate=(1.0*s/size)*100;
		System.out.println("中断次数："+s);
		System.out.println("访问次数："+size);
		System.out.printf("中断率：%.2f%%\n",rate);
	}
	
	public void FIFO() {
		int s=0;//中断次数
		int size=page.size();//即访问次数
		double rate;//中断率
		System.out.println("***************First In First Out Algorithm***************");
		for(int i=0;i<m;i++) {
			block.add(page.get(i));
			s++;
			System.out.println(block);
		}
		for(int i=0;i<m;i++) {
			page.remove(0);
		}
		MAX_LOOP:
		while(page.size()!=0) {
			for(int k=0;k<m;k++) {
				if(block.get(k)==page.get(0)) {
					page.remove(0);
					System.out.println(block);
					continue MAX_LOOP;
				}
			}
			for(int i=0;i<m-1;i++) {
				block.set(i,block.get(i+1));
			}
			block.set(m-1, page.get(0));
			s++;
			page.remove(0);
			System.out.println(block);
		}
		rate=(1.0*s/size)*100;
		System.out.println("中断次数："+s);
		System.out.println("访问次数："+size);
		System.out.printf("中断率：%.2f%%\n",rate);
	}
	
	public void LRU() {
		int s=0;//中断次数
		int size=page.size();//即访问次数
		double rate;//中断率
		int MIN=1000;
		List<Integer> test=new ArrayList<Integer>();
		System.out.println("***************Least Recently Used Algorithm***************");
		for(int i=0;i<m;i++) {
			block.add(page.get(i));
			s++;
			System.out.println(block);
		}
		for(int i=0;i<m;i++) {
			test.add(page.get(0));
			page.remove(0);
		}
		while(page.size()!=0){
			FIRST_LOOP:
			for(int i=0;i<m;i++) {
				for(int k=0;k<m;k++) {
					if(block.get(k)==page.get(0)) {
						test.add(page.get(0));
						page.remove(0);
						break FIRST_LOOP;
					}
				}
				if(test.lastIndexOf(block.get(i))<MIN) {
					MIN=test.lastIndexOf(block.get(i));
				}
			}
			for(int i=0;i<m;i++) {
				if((MIN!=1000)&&(block.get(i)==test.get(MIN))) {
					block.set(i, page.get(0));
					s++;
					test.add(page.get(0));
					page.remove(0);
					MIN=1000;
				}
			}
			System.out.println(block);
		}
		rate=(1.0*s/size)*100;
		System.out.println("中断次数："+s);
		System.out.println("访问次数："+size);
		System.out.printf("中断率：%.2f%%\n",rate);
	}
	
}

public class Main2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
		while(true) {
			System.out.println("请输入想要实现的算法 1：OPT 2:FIFO 3:LRU 4:退出(输入格式：1 or 2 or 3 or 4)");
			int choice=in.nextInt();
			switch(choice) {
			case 1:
				Replacement re1=new Replacement();
				re1.init();
				re1.OPT();break;
			case 2:
				Replacement re2=new Replacement();
				re2.init();
				re2.FIFO();break;
			case 3:
				Replacement re3=new Replacement();
				re3.init();
				re3.LRU();break;
			case 4:
				System.out.println("退出成功！");
				System.exit(0);break;
			}
		}
	}
}

运行结果：