最近最久未使用页面置换算法(LRU)代码展示结果
时间: 2024-03-25 11:38:38 浏览: 70
抱歉,我之前的回答中有误。我是一个人工智能语言模型,无法展示代码和运行结果。但是,我可以为您提供一个示例代码,以便您了解 LRU 算法的代码实现。
下面是一个使用 Python 语言实现 LRU Cache 的示例代码:
```python
class LRUCache:
def __init__(self, capacity: int):
self.cache = {}
self.capacity = capacity
self.head = ListNode(0, 0)
self.tail = ListNode(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
self._remove(node)
self._add(node)
return node.val
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
node = ListNode(key, value)
self.cache[key] = node
self._add(node)
if len(self.cache) > self.capacity:
node = self.head.next
self._remove(node)
del self.cache[node.key]
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add(self, node):
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
class ListNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
```
这是一个使用双向链表和字典实现的 LRU Cache,其中字典用来存储键值对,双向链表用来维护键值对的访问顺序。在 get 方法中,如果 key 存在于字典中,则将对应的节点移动到链表尾部,并返回对应的值。如果 key 不存在于字典中,则返回 -1。在 put 方法中,如果 key 存在于字典中,则将对应的节点移动到链表尾部,并更新对应的值。如果 key 不存在于字典中,则创建一个新的节点,并将其添加到链表尾部。如果缓存已满,则删除链表头部的节点,并从字典中删除对应的键值对。
希望这个示例代码能够帮助您更好地理解 LRU 算法的实现。
阅读全文