LRU 缓存实现
如何实现LRU缓存方案?应该使用什么数据结构?
我们给出了可以引用的总可能页码。我们还给出了缓存(或内存)大小(缓存一次可以容纳的页帧数)。...LRU 缓存方案是当缓存已满并且引用缓存中不存在的新页面时删除最近最少使用的帧。...使用队列和散列的 LRU 缓存实现:
要解决该问题,需要遵循以下想法:
我们使用两种数据结构来实现 LRU Cache。
队列是使用双向链表实现的。队列的最大大小将等于可用帧的总数(缓存大小)。...**示例 –**考虑以下参考字符串:1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
使用 3 页框架的最近最少使用 (LRU) 页面替换算法查找页面错误数。...辅助空间:
O(n),我们需要在缓存中存储n个元素,所以空间复杂度为O(n)。