【正确答案】我们可以使用两个数据结构实现一个LRU缓存。
(1)使用双向链表实现的队列，队列的最大容量为缓存的大小。在使用过程中，把最近使用的页面移动到队列头，最近没有使用的页面将被放在队列尾的位置。
(2)使用一个哈希表，把页号作为键，把缓存在队列中的结点的地址作为值。
当引用一个页面时，如果所需的页面在内存中，只需要把这个页对应的结点移动到队列的前面。如果所需的页面不在内存中，此时需要把这个页面加载到内存中。简单地说，就是将一个新结点添加到队列的前面，并在哈希表中更新相应的结点地址。如果队列是满的，那么就从队列尾部移除一个结点，并将新结点添加到队列的前面。实现代码如下：
from collections import deque
class LRU:
def __init__(self,cacheSize):
self.cacheSize=cacheSize
self.queue=deque()
self.hashSet=set()
#判断缓存队列是否已满
def isQueueFull(self):
return len(self.queue)==self.cacheSize
#把页号为pageNum的页缓存到队列中,同时也添加到Hash表中
def enqueue(self,pageNum):
#如果队列满了,需要删除队尾的缓存的页
if self.isQueueFull():
self.hash Set.remove(self.queue[-1])
self.queue.pop()
self.queue.appendleft(pageNum)
#把新缓存的结点同时添加到hash表中
self.hashSet.add(pageNum)
"""
当访问某一个page的时候会调用这个函数，对于访问的page有两种情况：
1. 如果page在缓存队列中，直接把这个结点移动到队首
2. 如果page不在缓存队列中，把这个page缓存到队首。
"""
def accessPage(self,pageNum):
#page不在缓存队列中, 把它缓存到队首
if pageNum not in self.hashSet:
self.enqueue(pageNum)
#page已经在缓存队列中了, 移动到队首
elif pageNum!=self.queue[0]:
self.queue.remove(pageNum)
self.queue.appendleft(pageNum)
def printQueue(self):
while len(self.queue)＞0:
print self.queue.popleft(),
if __name__="__main__":
#假设缓存大小为3
1ru=LRU(3)
#访问page
1ru.accessPage(1)
1ru.accessPage(2)
1ru.accessPage(5)
1ru.accessPage(1)
1ru.accessPage(6)
1ru.accessPage(7)
#通过上面的访问序列后，缓存的信息为
1ru.printQueue()
程序的运行结果为：
7 6 1