题目一：LRU

问题描述

请你实现一个满足 LRU(最近最少使用)缓存约束 的数据结构及其基础功能.

具体的来说，你需要建立一个可以容纳 capacity 个一一对应的 unsigned int - int 键值对的数据结构。和电话簿中一个姓名对应一个电话类似， 这个数据结构一个 unsigned int 对应一个 int，并且最多存储 capacity 个这样的配对。

然后你需要支持以下操作：

• 插入功能，传入 unsigned int key 和 int value，如果数据结构中存在 key 则更新对应的 value 为传入值。
• 查找功能，传入 key，查找并返回对应的 value，如果找不到则返回 -1。

由于最多存储 capacity 个键值对，当插入的键值对超过 capacity 个时，需要选择最近最少使用的一个 key 删掉（在这里意味着上一次插入或查找该 key 的时间离现在最远）然后才能插入新的键值对。

你还需要支持

• 逆序输出，按照最近最少使用的 key 排前面，最近刚刚使用过的 key 排后面的顺序输出键值对。

你可以使用一个带头节点链表实现这个功能，每次访问某个 key，就把它从链表中间拿出放到链表最前面（即 head->next）。

另外,请你思考:如何设计函数get()和put()使其以 O(1) 的平均时间复杂度运行?你可以在本次实验中额外实现这一点,不作为强制要求.

capacity,key均为unsigned int型，value 为 int 型

输入形式

输入第一行为LRU缓存容量capacity和等待执行的操作数n;

输入接下来n行为等待执行的操作,每一行第一部分为3个字符代表操作名称,接下来为操作对应的变量;

输出形式

输出根据不同的操作分为两种类型,get（读取）和rev（逆序输出）,而put（插入）没有输出.

连续的get操作输出在同一行内;而当遇到rev操作时,先另起一行,然后每一行输出一个节点对应的key-value组(key和value用单个空格分隔),rev的最后一行输出末尾有换行符.

一个抽象的例子(暂时不考虑LRU缓存中的具体情况):

假设LRU缓存大小为2,去除put操作后的输入为:

get 1

get 2

rev

get 3

get 4

rev

对应的输出形如:

get_value1 get_value2

rev_key1 rev_value1

rev_key2 rev_value2

get_value3 get_value4

rev_key3 rev_value3

rev_key4 rev_value4

样例输入

2 10
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4
rev

样例输出

1 -1 -1 3 4
3 3
4 4

样例说明

按照样例输入的操作序列：

1. put 1 1, put 2 2：缓存变为 [2:2, 1:1]（2 是最近访问的）。
2. get 1：命中 1，输出 1，将其移至头部，缓存变为 [1:1, 2:2]。
3. put 3 3：容量为 2，此时已满。淘汰最久未访问的 2，插入 3，缓存变为 [3:3, 1:1]。
4. get 2：未命中，输出 -1。
5. put 4 4：淘汰最久未访问的 1，插入 4，缓存变为 [4:4, 3:3]。
6. 接下来的 get 1, get 3, get 4 分别输出 -1, 3, 4。
7. rev：从最久未访问到最近访问输出，即先输出 3 3，再输出 4 4。

评分标准

暂定4组测试样例,每组25分.