class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.prev = None
self.next = None
class DoubleList:
def __init__(self):
# 头指针、尾指针
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
self.lenSize = 0
# 尾插、头出、任意删
def add_last(self, x):
x.next = self.tail
x.prev = self.tail.prev
self.tail.prev.next = x
self.tail.prev = x
self.lenSize += 1
def pop_head(self):
if self.lenSize > 0:
tmp = self.head.next
self.remove_anywhere(tmp)
return tmp
def remove_anywhere(self, x):
x.prev.next = x.next
x.next.prev = x.prev
self.lenSize -= 1
def get_size(self):
return self.lenSize
class LRU:
def __init__(self, cap):
self.map = {}
self.cache = DoubleList()
# 最大容量
self.cap = cap
def get(self, key):
if key in self.map:
self.make_recently(key)
return self.map[key].val
else:
return -1
def put(self, key, val):
if key in self.map:
self.remove(key)
self.add_recently(key, val)
return
if self.cache.lenSize == self.cap:
self.remove_least_used()
self.add_recently(key, val)
# 对手机后台的操作
# 1. 打开新应用
def add_recently(self, key, val):
node = Node(key, val)
node.prev = self.cache.tail.prev
self.cache.tail.prev.next = node
self.cache.tail.prev = node
node.next = self.cache.tail
# 放进map
self.map[key] = node
# 2. 打开后台应用
def make_recently(self, key):
node = self.map[key]
self.cache.remove_anywhere(node)
self.cache.add_last(node)
# 3. 划掉后台应用
def remove(self, key):
node = self.map[key]
self.cache.remove_anywhere(node)
self.map.pop(key)
# 4. 杀后台
def remove_least_used(self):
tmp = self.cache.pop_head()
self.map.pop(tmp.key)
网友评论