ACM_LRU页面置换算法

Problem Description:

sss操作系统没听课, 这周的操作系统作业完全不会, 你能帮他写出来吗, 以下是操作系统老师的实验说明:

LRU算法解释:

LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

LRU的实现（需要“堆栈”支持）:

可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号.

Input:

多组输入

每组数据第一行为n(1<=n<=100),n为页面栈的大小, m(1<=m<=500000), m为需要访问的页面序列长度, 第二行为访问页面序列a1~am (0<=ai<=1000)

Output:

输出一行, 最后栈内的元素(从栈底开始输出)

Sample Input:

5 11

4 7 0 7 1 0 1 2 1 2 6

Sample Output:

7 0 1 2 6
解题思路：结合LRU置换算法的定义举个栗子：假设现有一进程所访问的页面序列为：4，7，0，7，1，0，1，2，1，2，6。随着进程的访问，栈中页面号的变化情况如图所示。在访问页面6时发生了缺页，此时页面4是最近最久未被访问的页，应将它置换出去。此题直接暴力模拟即可。正确做法：双向链表+哈希表！

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int maxn=;

 int n,m,x,cnt,stk[],pos[maxn];

 int main(){

     while(cin>>n>>m){

         cnt=;memset(pos,,sizeof(pos));//标记页面在栈中的位置

         while(m--){

             cin>>x;

             if(pos[x]){//栈中已出现x，将x提到栈顶，剩下的页面往下移

                 for(int i=pos[x];i<cnt;++i)stk[i]=stk[i+],pos[stk[i]]=i;

                 stk[cnt]=x,pos[x]=cnt;

             }

             else{//x未出现

                 if(cnt!=n)stk[++cnt]=x,pos[x]=cnt;//栈未满则直接添加

                 else{//栈满，移去最久未使用的页面，将x放栈顶

                     for(int i=;i<n;++i)stk[i]=stk[i+],pos[stk[i]]=i;

                     stk[n]=x,pos[x]=n;

                 }

             }

         }

         for(int i=;i<=cnt;++i)cout<<stk[i]<<(i==cnt?'\n':' ');//输出当前栈中的页面号

     }

     return ;

 }