用双向链表就可以解决这个问题，双向链表可以以O(1)的时间访问头尾元素。还有个问题，如果调用Insert(v)，按照之前的算法，我先得知道v在不在这个双向链表中，如果不在直接插到头部，如果在的话，将其提取到头部。如果仅仅是双向链表，那么还是需要遍历一遍队列，查询v是不是已经在队列中了。
可以用一个map记录已经在队列中的元素到链表节点的键值对，这样就可以以O(1)的时间查询某个value是否已经在队列中。
最终确定数据结构如下：
假设两种极端的情况：
没有缓冲池，那么数据都位于磁盘上，第一次访问一页数据，需要将其从磁盘读取到内存，第二次在访问相同的页时，还需要从磁盘读，非常耗时。
假设内存无限大，那么访问一页数据后，将该页数据直接保存到内存，下次再访问该页时，直接访问内存缓存就行。但是现实中内存比磁盘容量小得多，只能缓存有限个数据页，如下图内存只能缓存三个页，依次访问PAGE 1, 2, 3, 现在已经缓存了PAGE 1, 2, 3，假设想读取PAGE 4，那么得先清空一个内存缓存页，用来缓存PAGE 4的数据，那么清除谁呢？。这时候任务2的替换策略就派上用场了，根据LRU替换策略，PAGE 1是最近最久没有被使用过的，那么就将PAGE 1重新写回到磁盘，然后将PAGE 4读取到内存。
所以BUFFER POOL MANAGER的作用是加速数据的访问，同时对使用者来说是透明的。
具体代码就不贴了，可以参考我的实现：https://github.com/gatsbyd/cmu_15445_2018