题面描述:

给定一个缓存最多存放N页，输入K次操作，操作包括插入（A）、查询（Q）和删除（D）。插入时如果页面已存在则刷新访问时间，否则插入新页面，若超过容量N则淘汰最久未使用页面。查询和删除操作也会刷新页面的访问时间。最后输出缓存内页面编号，按LRU（最近最少使用）顺序排列。

思路

双向链表 + 哈希表

这是一道经典原题146. LRU缓存 。

题目描述

$\qquad$小明有一门专业课，叫做操作系统，简称OS。操作系统的页式存储管理中，当主存满并且需要的存储页不在主存中，需要对主存中的页面进行置换，其中有一个非常重要的算法，即LRU置换算法。

$\qquad$LRU (Least Recently Used)缓存算法理一种常用于管理缓存的策略，其目标是保留最近使用过的数据,而淘汰最久未被使用的数据。实现简单的LRU缓存算法,支持查询、插入、删除操作。

$\qquad$最久未被使用定义：查询、插入和删除操作均为一次访问操作，每个元素均有一个最后一次被访问时间,按照最后一次被访问时间排序，时间最早的即为最久未使用。插入操作：当缓存中已经存在，则刷新值，不存在，则插入，如果超过上限，则淘汰最久未被使用的元素。

输入描述

$\qquad$第一行两个数N和K，分别表示缓存内最多可以存放页数，以及操作序列中的总操作数。其中N∈[1,100]，K∈[1,10000]。

$\qquad$第二至第K+1行，每行两个输入，两个输入用空格分隔。第一个输入是一个字符$ch_i$：A表示插入，Q表示查询，D表示删除。第二个输入是一个整数$a_i$，表示一个页面的编号。其中$a_i$∈[1,100000]。

输出描述

$\qquad$输出一行，表示缓存内各页面的编号，按照LRU优先级。

样例一

输入

2 5
A 103
A 102
A 102
Q 103
A 101

输出

101 103

解释

缓存大小为2，依次进行插入103、102，重复插入102，查询一次103，插入101时，最久未使用的元素为102，所以淘汰102。

Limitation

1s, 1024KiB for each test case.