1102: 双向链表的应用——LRUcache模拟
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：149
Solved：43
Description
你需要实现一个最近最少使用（LRU）缓存，支持以下操作：
$get(key)$: 如果缓存中存在指定的键，则返回该键对应的值（总是正整数），否则返回 $-1$。
$put(key, value)$: 如果键不存在，则写入其数据值。当缓存容量达到上限时，应该删除最近最少使用的数据值，以便为新数据值腾出空间。
缓存应该在 $O(1)$ 时间复杂度内完成这两种操作。
Input
以一个整数 $capacity$ 开始（$1 \leq capacity \leq 1000$），表示LRU缓存的容量。接下来是一系列操作，每个操作可能是： $get Key$: 执行 $get$ 操作，查询指定 $key$ 的值。 $put Key Value$: 执行 $put$ 操作，插入或更新指定 $key$ 和 $value$。 操作之间用空格分隔。 输入"exit"以代表结束(无双引号)
Output
对于每个 $get$ 操作，输出其结果，每个结果占一行。
Sample Input Copy
2
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4
exit
Sample Output Copy
1
-1
-1
3
4
HINT
在上述示例中：
首先初始化一个容量为 2 的缓存。
put 1 1 和 put 2 2 将键值对 [{1, 1}, {2, 2}] 放入缓存。
get 1 返回值 1，并将键 1 标记为最近使用。
put 3 3 插入键值对 [{3, 3}]，由于缓存已满，删除最近最少使用的键 2，缓存变为 [{1, 1}, {3, 3}]。
get 2 返回 -1，因为键 2 已被删除。
put 4 4 插入键值对 [{4, 4}]，缓存已满，删除最近最少使用的键 1，缓存变为 [{3, 3}, {4, 4}]。
get 1 返回 -1，因为键 1 已被删除。
get 3 返回 3。
get 4 返回 4。