四大高频设计题深度解析：LRU缓存、LFU缓存、最大频率栈、餐盘栈
目录
- LRU缓存：原理、设计、代码与应用
- LFU缓存：原理、设计、代码与应用
- 最大频率栈：原理、设计、代码与应用
- 餐盘栈：原理、设计、代码与应用
- 相关题型与工程拓展
- 总结与学习建议
1. LRU缓存（Least Recently Used）
1.1 原理与生活类比
LRU（最近最少使用）缓存是一种常见的缓存淘汰策略。核心思想：
每次访问（get/put）都把该元素放到最上面，超出容量时淘汰最久未使用的元素（最下面的元素）。
生活类比：你有一摞书，每次看一本书就把它放到最上面。如果书太多了，最下面的书会被移除。
1.2 设计原理与数据结构
- 双向循环链表：维护元素的访问顺序，头部是最新，尾部是最旧。
- 哈希表：key 映射到链表节点，实现 O(1) 查找。
- 哨兵节点 dummy：链表头尾都指向 dummy，极大简化插入、删除逻辑。
操作流程
- get(key)：查找哈希表，若存在则移动到链表头部，返回 value，否则返回 -1。
- put(key, value)：若 key 存在，更新 value 并移动到头部；否则新建节点插入头部，若超容量则删除尾部节点。
关键细节
- 节点要存 key，便于删除尾部节点时同步删除哈希表。
- 用循环链表和哨兵节点，所有节点的 prev/next 都不为空，插入删除统一处理，无需特判头尾。
1.3 Mermaid示意图
LRU缓存结构
操作流程
graph TD
A[put/get访问节点x] --> B[从链表中删除x]
B --> C[插入到dummy后面]
C --> D[若超容量，删除dummy.prev]
1.4 代码实现（C++/Python，详细注释）
C++实现
// 双向链表节点定义
class Node {
public:
int key, value;
Node *prev, *next;
Node(int k = 0, int v = 0) : key(k), value(v) {}
};
class LRUCache {
private:
int capacity;
Node* dummy; // 哨兵节点，dummy->next是头，dummy->prev是尾
unordered_map<int, Node*> key_to_node; // 哈希表，key映射到节点
// 删除一个节点（抽出一本书）
void remove(Node* x) {
x->prev->next = x->next;
x->next->prev = x->prev;
}
// 在链表头添加一个节点（把一本书放在最上面）
void push_front(Node* x) {
x->prev = dummy;
x->next = dummy->next;
x->prev->next = x;
x->next->prev = x;
}
// 获取key对应的节点，并把它移到链表头部
Node* get_node(int key) {
auto it = key_to_node.find(key);
if (it == key_to_node.end()) return nullptr;
Node* node = it->second;
remove(node); // 把这本书抽出来
push_front(node); // 放在最上面
return node;
}
public:
LRUCache(int capacity) : capacity(capacity), dummy(new Node()) {
dummy->prev = dummy;
dummy->next = dummy;
}
int get(int key) {
Node* node = get_node(key);
return node ? node->value : -1;
}
void put(int key, int value) {
Node* node = get_node(key);
if (node) {
node->value = value; // 更新value
return;
}
key_to_node[key] = node = new Node(key, value); // 新书
push_front(node);
if (key_to_node.size() > capacity) { // 超容量
Node* back_node = dummy->prev;
key_to_node.erase(back_node->key);
remove(back_node);
delete back_node;
}
}
};
Python实现
class Node:
__slots__ = 'prev', 'next', 'key', 'value'
def __init__(self, key=0, value=0):
self.key = key
self.value = value
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.dummy = Node()
self.dummy.prev = self.dummy
self.dummy.next = self.dummy
self.key_to_node = {}
def get_node(self, key: int):
if key not in self.key_to_node:
return None
node = self.key_to_node[key]
self.remove(node)
self.push_front(node)
return node
def get(self, key: int) -> int:
node = self.get_node(key)
return node.value if node else -1
def put(self, key: int, value: int) -> None:
node = self.get_node(key)
if node:
node.value = value
return
self.key_to_node[key] = node = Node(key, value)
self.push_front(node)
if len(self.key_to_node) > self.capacity:
back_node = self.dummy.prev
del self.key_to_node[back_node.key]
self.remove(back_node)
def remove(self, x: Node) -> None:
x.prev.next = x.next
x.next.prev = x.prev
def push_front(self, x: Node) -> None:
x.prev = self.dummy
x.next = self.dummy.next
x.prev.next = x
x.next.prev = x
1.5 带过期时间的LRU实现
原理说明
- 每个节点增加 expireTime 字段，表示过期时间戳。
- put 时设置 expireTime，get 时判断当前时间是否过期。
- 过期节点在 get/put 时被移除。
C++实现（详细注释）
#include <chrono>
#include <ctime>
class Node {
public:
int key, value;
long long expireTime; // 过期时间戳（毫秒）
Node *prev, *next;
Node(int k = 0, int v = 0, long long exp = 0) : key(k), value(v), expireTime(exp) {}
};
class LRUCache {
private:
int capacity;
Node* dummy;
unordered_map<int, Node*> key_to_node;
// 获取当前时间戳（毫秒）
long long now() {
return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
}
void remove(Node* x) {
x->prev->next = x->next;
x->next->prev = x->prev;
}
void push_front(Node* x) {
x->prev = dummy;
x->next = dummy->next;
x->prev->next = x;
x->next->prev = x;
}
Node* get_node(int key) {
auto it = key_to_node.find(key);
if (it == key_to_node.end()) return nullptr;
Node* node = it->second;
// 判断是否过期
if (node->expireTime < now()) {
remove(node);
key_to_node.erase(key);
delete node;
return nullptr;
}
remove(node);
push_front(node);
return node;
}
public:
LRUCache(int capacity) : capacity(capacity), dummy(new Node()) {
dummy->prev = dummy;
dummy->next = dummy;
}
int get(int key) {
Node* node = get_node(key);
return node ? node->value : -1;
}
void put(int key, int value, int ttl_ms) {
long long expire = now() + ttl_ms;
Node* node = get_node(key);
if (node) {
node->value = value;
node->expireTime = expire;
return;
}
key_to_node[key] = node = new Node(key, value, expire);
push_front(node);
if (key_to_node.size() > capacity) {
Node* back_node = dummy->prev;
key_to_node.erase(back_node->key);
remove(back_node);
delete back_node;
}
}
};
1.6 真实场景与策略对比
真实场景
- 数据库缓存：如MySQL的InnoDB Buffer Pool，缓存最近访问的数据页，淘汰最久未用页。
- Web缓存：如浏览器缓存、CDN缓存，优先保留最近访问的资源。
- 内存管理：操作系统页面置换，LRU算法决定哪些页面被换出。
策略对比
- LRU适合：数据访问有“局部性原理”，即最近访问的数据很可能再次被访问。
- LFU适合：热点数据分布稳定，频繁访问的数据应长期保留。
- 实际选择：如Redis 6.0支持多种淘汰策略，需根据业务场景权衡。
2. LFU缓存（Least Frequently Used）
2.1 原理与生活类比
LFU（最不经常使用）缓存是一种淘汰策略，核心思想：
每次淘汰“使用频率最少”的元素，如果有多个，淘汰最久未使用的那个。
生活类比：你有好几摞书，每摞书代表“看过x次”的书。每次看一本书，就把它从当前摞抽出来，放到右边那摞的最上面。淘汰时，移除最左边那摞的最下面的书。
2.2 设计原理与数据结构
- key_to_node：key 映射到节点，节点包含 key、value、freq
- freq_to_dummy：freq 映射到双向链表的哨兵节点，每个链表存储所有相同频率的节点
- minFreq：当前最小频率
操作流程
- get(key)：查找节点，移出原链表，插入 freq+1 链表头部，若原链表空且为 minFreq，minFreq++
- put(key, value)：若 key 存在，更新 value 并提升频率；否则新建节点插入 freq=1 链表头部，若超容量则淘汰 minFreq 链表尾部节点
关键细节
- 每个频率一摞书，每摞书用双向链表维护顺序，淘汰时找 minFreq 摞的最下面的书。
- minFreq 始终指向最左边非空摞。
2.3 Mermaid示意图
LFU缓存结构
操作流程
2.4 代码实现（C++/Python，极其详细注释）
C++实现
// LFU缓存节点定义
class Node {
public:
int key, value, freq;
Node *prev, *next;
Node(int k = 0, int v = 0, int f = 1) : key(k), value(v), freq(f), prev(nullptr), next(nullptr) {}
};
class LFUCache {
private:
int capacity; // 缓存容量
int minFreq; // 当前最小频率
unordered_map<int, Node*> key_to_node; // key到节点的映射
unordered_map<int, Node*> freq_to_dummy; // 频率到链表哨兵的映射
// 创建一个新的双向循环链表的哨兵节点
Node* new_list() {
Node* dummy = new Node();
dummy->prev = dummy;
dummy->next = dummy;
return dummy;
}
// 在freq对应的链表头部插入节点x
void push_front(int freq, Node* x) {
if (!freq_to_dummy.count(freq)) freq_to_dummy[freq] = new_list();
Node* dummy = freq_to_dummy[freq];
x->prev = dummy;
x->next = dummy->next;
dummy->next->prev = x;
dummy->next = x;
}
// 从链表中删除节点x
void remove(Node* x) {
x->prev->next = x->next;
x->next->prev = x->prev;
}
// 访问key对应的节点，提升频率
Node* get_node(int key) {
auto it = key_to_node.find(key);
if (it == key_to_node.end()) return nullptr;
Node* node = it->second;
int oldFreq = node->freq;
remove(node); // 从原频率链表删除
Node* dummy = freq_to_dummy[oldFreq];
// 如果原频率链表空且minFreq==oldFreq，minFreq++
if (dummy->next == dummy && minFreq == oldFreq) minFreq++;
node->freq++;
push_front(node->freq, node); // 插入新频率链表头部
return node;
}
public:
LFUCache(int capacity) : capacity(capacity), minFreq(0) {}
int get(int key) {
Node* node = get_node(key);
return node ? node->value : -1;
}
void put(int key, int value) {
if (capacity == 0) return;
Node* node = get_node(key);
if (node) {
node->value = value;
return;
}
if (key_to_node.size() == capacity) {
// 淘汰minFreq链表的最后一个节点
Node* dummy = freq_to_dummy[minFreq];
Node* toRemove = dummy->prev;
key_to_node.erase(toRemove->key);
remove(toRemove);
delete toRemove;
}
// 新节点，freq=1
node = new Node(key, value, 1);
key_to_node[key] = node;
push_front(1, node);
minFreq = 1;
}
};
Python实现
class Node:
__slots__ = 'prev', 'next', 'key', 'value', 'freq'
def __init__(self, key=0, value=0, freq=1):
self.key = key
self.value = value
self.freq = freq
self.prev = self.next = None
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.minFreq = 0
self.key_to_node = {}
self.freq_to_dummy = {}
def new_list(self):
dummy = Node()
dummy.prev = dummy
dummy.next = dummy
return dummy
def push_front(self, freq, x):
if freq not in self.freq_to_dummy:
self.freq_to_dummy[freq] = self.new_list()
dummy = self.freq_to_dummy[freq]
x.prev = dummy
x.next = dummy.next
dummy.next.prev = x
dummy.next = x
def remove(self, x):
x.prev.next = x.next
x.next.prev = x.prev
def get_node(self, key):
if key not in self.key_to_node:
return None
node = self.key_to_node[key]
oldFreq = node.freq
self.remove(node)
dummy = self.freq_to_dummy[oldFreq]
if dummy.next == dummy and self.minFreq == oldFreq:
self.minFreq += 1
node.freq += 1
self.push_front(node.freq, node)
return node
def get(self, key: int) -> int:
node = self.get_node(key)
return node.value if node else -1
def put(self, key: int, value: int) -> None:
if self.capacity == 0:
return
node = self.get_node(key)
if node:
node.value = value
return
if len(self.key_to_node) == self.capacity:
dummy = self.freq_to_dummy[self.minFreq]
toRemove = dummy.prev
del self.key_to_node[toRemove.key]
self.remove(toRemove)
node = Node(key, value, 1)
self.key_to_node[key] = node
self.push_front(1, node)
self.minFreq = 1
2.5 实际应用与策略对比
真实场景
- 热点数据缓存：如视频网站、新闻门户，热点内容频繁访问，LFU能长期保留高频数据。
- 分布式缓存：如Redis、Memcached，LFU适合热点数据分布稳定的场景。
- 数据库缓冲池：如Oracle、SQL Server，部分采用LFU策略管理缓冲页。
策略对比
- LFU适合：热点数据分布稳定，频繁访问的数据应长期保留。
- LRU适合：数据访问有“局部性原理”，即最近访问的数据很可能再次被访问。
- 实际选择：如Redis 6.0支持多种淘汰策略，需根据业务场景权衡。
3. 最大频率栈（Maximum Frequency Stack）
3.1 原理与生活类比
最大频率栈是一种特殊的栈，支持 push 和 pop 操作，每次 pop 返回出现频率最高的元素，若有多个则返回最接近栈顶的那个。
生活类比：你有多摞书，每摞书代表出现频率相同的元素，每次pop弹出最右边那摞的最上面那本书。
3.2 设计原理与数据结构
- 哈希表 cnt：记录每个元素的出现次数。
- 栈的列表 stacks：stacks[i] 存储所有出现次数为 i+1 的元素，保证同频率下后入先出。
操作流程
- push(val)：cnt[val]++，若新频率等于当前最大频率，创建新栈，压入。
- pop()：弹出最大频率栈的栈顶元素，cnt[val]–，若栈空则删除该栈。
关键细节
- 不会出现中间栈为空，因为只在最大频率栈上弹出。
- 保证弹出的是最接近栈顶的元素，因为每个频率的元素都按入栈顺序排列。
3.3 Mermaid示意图
3.4 代码实现（C++/Python，极其详细注释）
C++实现
class FreqStack {
vector<stack<int>> stacks; // 每个频率一个栈
unordered_map<int, int> cnt; // 记录每个val的出现次数
public:
// 入栈操作
void push(int val) {
// 如果val的频率等于当前栈数，说明需要新建一个栈
if (cnt[val] == stacks.size())
stacks.push_back({});
stacks[cnt[val]].push(val); // 压入对应频率的栈
cnt[val]++;
}
// 出栈操作
int pop() {
int val = stacks.back().top(); // 弹出最大频率栈的栈顶
stacks.back().pop();
if (stacks.back().empty()) stacks.pop_back(); // 栈空则删除
cnt[val]--;
return val;
}
};
Python实现
class FreqStack:
def __init__(self):
self.stacks = [] # 每个频率一个栈
self.cnt = defaultdict(int) # 记录每个val的出现次数
def push(self, val: int) -> None:
# 如果val的频率等于当前栈数，说明需要新建一个栈
if self.cnt[val] == len(self.stacks):
self.stacks.append([val])
else:
self.stacks[self.cnt[val]].append(val)
self.cnt[val] += 1
def pop(self) -> int:
val = self.stacks[-1].pop()
if not self.stacks[-1]:
self.stacks.pop()
self.cnt[val] -= 1
return val
3.5 实际应用与策略对比
- 频率优先队列：可用于任务调度、缓存淘汰等。
- 与LFU的区别：LFU淘汰最少使用，最大频率栈弹出最常用。
- 工程场景：如频率优先的任务调度、数据流分析、热点数据弹出。
4. 餐盘栈（Dinner Plate Stacks）
4.1 原理与生活类比
餐盘栈是一组容量相同的栈，支持 push、pop、popAtStack 操作。push 总是推入最左边未满的栈，pop 总是弹出最右边非空栈。
生活类比：你有一排餐盘，每个盘子最多放capacity个菜，每次优先往最左边未满的盘子放菜，取菜时优先从最右边非空盘子取。
4.2 设计原理与数据结构
- stacks：所有栈的列表
- 最小堆 h：维护所有未满栈的下标，push时取最小下标
- 懒删除：popAtStack后若栈空，实际删除在push时处理
操作流程
- push(val)：若堆顶下标越界则清空堆，若堆非空则入栈，否则新建栈。
- pop()：等价于 popAtStack 最后一个非空栈。
- popAtStack(index)：若栈非空则弹出，若栈满则入堆。
关键细节
- 懒删除：popAtStack后不立即删除空栈，push时发现堆顶下标越界再清空堆。
- pushAtStack(index, val) 拓展：可用堆或有序集合维护未满栈下标。
4.3 Mermaid示意图
4.4 代码实现（C++/Python，极其详细注释）
C++实现
class DinnerPlates {
int capacity; // 每个栈的容量
vector<stack<int>> stacks; // 所有栈
priority_queue<int, vector<int>, greater<>> idx; // 未满栈的下标（最小堆）
public:
DinnerPlates(int capacity) : capacity(capacity) {}
// 入栈操作
void push(int val) {
// 堆顶下标越界，清空堆
if (!idx.empty() && idx.top() >= stacks.size())
while (!idx.empty()) idx.pop();
if (idx.empty()) { // 所有栈都是满的
stack<int> st;
st.push(val);
stacks.emplace_back(st);
if (capacity > 1) idx.push(stacks.size() - 1);
} else { // 还有未满栈
auto &st = stacks[idx.top()];
st.push(val);
if (st.size() == capacity) idx.pop();
}
}
// 出栈操作
int pop() {
return popAtStack(stacks.size() - 1);
}
// 指定栈出栈
int popAtStack(int index) {
if (index < 0 || index >= stacks.size() || stacks[index].empty())
return -1;
auto &st = stacks[index];
if (st.size() == capacity) idx.push(index);
int val = st.top();
st.pop();
// 懒删除：只在push时清理空栈
while (!stacks.empty() && stacks.back().empty())
stacks.pop_back();
return val;
}
};
Python实现
import heapq
class DinnerPlates:
def __init__(self, capacity: int):
self.capacity = capacity
self.stacks = []
self.h = [] # 最小堆，保存未满栈的下标
def push(self, val: int) -> None:
# 堆顶下标越界，清空堆
while self.h and self.h[0] >= len(self.stacks):
heapq.heappop(self.h)
if self.h:
self.stacks[self.h[0]].append(val)
if len(self.stacks[self.h[0]]) == self.capacity:
heapq.heappop(self.h)
else:
self.stacks.append([val])
if self.capacity > 1:
heapq.heappush(self.h, len(self.stacks) - 1)
def pop(self) -> int:
return self.popAtStack(len(self.stacks) - 1)
def popAtStack(self, index: int) -> int:
if index < 0 or index >= len(self.stacks) or len(self.stacks[index]) == 0:
return -1
if len(self.stacks[index]) == self.capacity:
heapq.heappush(self.h, index)
val = self.stacks[index].pop()
while self.stacks and len(self.stacks[-1]) == 0:
self.stacks.pop()
return val
4.5 实际应用与策略对比
- 资源池管理：如线程池、连接池，优先分配最早空闲的资源。
- 分布式任务分配：多队列调度，优先填充最左边未满队列。
- 工程场景：如餐厅上菜、分布式缓存分片。
5. 相关题型与工程拓展
- LRU/LFU/最大频率栈/餐盘栈是缓存淘汰、频率调度、资源池管理等场景的基础。
- 工程实践：Redis、Memcached、操作系统页面置换、数据库缓冲池、Web CDN缓存等。
- 设计技巧总结：
- 哈希表+链表/栈/堆的复合数据结构，兼顾查找和顺序操作的高效性。
- 哨兵节点极大简化链表操作。
- 懒删除、最小堆等技巧提升效率。
6. 总结与学习建议
- 先理解原理，再动手实现，多画图、多调试。
- 关注工程细节，如内存管理、边界处理、性能优化。
- 多思考实际场景下的应用与优化，如带过期时间的LRU、分布式LFU等。
- 代码要有详细注释，便于维护和复用。
本博客全面梳理了 LRU、LFU、最大频率栈、餐盘栈四大设计题，结合自画结构图、资料、代码、原理、工程拓展，帮助你彻底掌握这些高频面试与工程实用题型。
Ran tool
Ran tool
Ran tool
Ran tool
Ran tool
Ran tool
以下是部分结构图的Mermaid代码，供你直接复制到支持Mermaid的编辑器或Markdown环境中渲染。部分复杂结构（如嵌套subgraph）Mermaid不支持，建议用分步图或简化结构表达。
1. LRU缓存结构图
2. LRU操作流程
graph TD
A[put/get访问节点x] --> B[从链表中删除x]
B --> C[插入到dummy后面]
C --> D[若超容量，删除dummy.prev]
graph TD
A[put/get访问节点x] --> B[从链表中删除x]
B --> C[插入到dummy后面]
C --> D[若超容量，删除dummy.prev]
3. LFU操作流程
4. LFU结构图（简化版）
如需最大频率栈、餐盘栈等结构图，建议用如下简化方式：
最大频率栈（简化）
餐盘栈（简化）
如需进一步美化或细化结构图，请告知具体需求！