答案：使用队列模拟LRU缓存可通过惰性删除和重复入队实现，但效率低于哈希表+双向链表组合。
在C++中，使用队列单独实现LRU（Least Recently Used）缓存并不高效，因为队列无法快速定位和更新中间元素。真正的LRU需要支持快速查找、插入、删除以及标记“最近使用”操作。通常采用哈希表 + 双向链表的组合方式，但若坚持用“队列”的思路模拟，可以通过一些变通方法实现一个简化版的LRU。
基本思路：队列 + 辅助结构模拟LRU
虽然标准队列（如 std::queue）不支持随机访问或元素移动，但我们可以通过以下方式模拟LRU行为：
- 使用
std::queue记录访问顺序（最老的在队头） - 使用
std::unordered_set或std::unordered_map快速判断元素是否在缓存中 - 当缓存满且新元素不存在时，从队列头弹出旧元素
- 关键问题：如果访问的是已存在的元素（命中），如何将其标记为“最近使用”？——队列本身无法删除中间元素，因此需要重建或打标记
由于这种限制，我们引入一种惰性删除 + 重复入队的方法。
立即学习“C++免费学习笔记（深入）”；
方法：惰性更新 + 队列重复入队
允许同一个key多次出现在队列中，但通过哈希表记录当前有效的值，并在弹出时判断是否过期。
数据结构：
-
std::queue<int></int>：记录访问顺序（包括重复） -
std::unordered_map<int int></int>：存储 key -> value 映射 -
std::unordered_set<int></int>或直接用 map 判断存在性 -
int capacity：最大容量
put 操作逻辑：
- 如果 key 已存在，更新 value，并将 key 再次入队（表示最新使用）
- 如果 key 不存在且缓存已满，则从队列头开始“惰性弹出”：检查队头 key 是否仍有效（map 中是否存在且值未被覆盖），若无效则丢弃，直到腾出空间
- 插入新 key-value，key 入队
get 操作逻辑：
- 查 map 是否存在 key
- 存在则返回 value，并将 key 再次入队（标记为最近使用）
- 不存在返回 -1
代码示例
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
class LRUCache {
private:
queue<int> q;
unordered_map<int, int> cache;
int capacity;
public:
LRUCache(int cap) : capacity(cap) {}
int get(int key) {
if (cache.find(key) == cache.end()) {
return -1;
}
// 标记为最近使用：重新入队
q.push(key);
return cache[key];
}
void put(int key, int value) {
// 如果已存在，更新值并重新入队
if (cache.find(key) != cache.end()) {
cache[key] = value;
q.push(key);
return;
}
// 检查容量，惰性清理
while (cache.size() >= capacity) {
int oldKey = q.front(); q.pop();
// 如果 map 中的值仍匹配（说明未被覆盖），则真正删除
// 实际上我们只删一次，但可能遇到重复入队的旧记录
if (cache.find(oldKey) != cache.end()) {
cache.erase(oldKey);
}
}
cache[key] = value;
q.push(key);
}
};使用示例
int main() {
LRUCache lru(2);
lru.put(1, 1);
lru.put(2, 2);
cout << lru.get(1) << endl; // 1
lru.put(3, 3); // evicts key 2
cout << lru.get(2) << endl; // -1
cout << lru.get(3) << endl; // 3
return 0;
}注意事项与局限性
- 空间开销大：队列中可能存在大量重复或已失效的记录
- 时间不稳定：get 和 put 操作可能导致队列积压，清理时需多次 pop
- 不是严格O(1)：理想 LRU 应为 O(1)，此方法平均接近但最坏情况较差
- 适用场景有限：适合教学理解，生产环境推荐用 list + unordered_map 手写双向链表
如果追求效率，应使用 std::list 模拟双向链表，配合哈希表指向节点，实现真正的 O(1) LRU。
基本上就这些，用队列模拟LRU能跑通逻辑，但本质是妥协方案。
