栈的设计题：最小栈与用队列模拟栈
摘要
本篇覆盖两道栈的设计类题目：LeetCode 155（Min Stack，最小栈）和 LeetCode 225（Implement Stack using Queues，用队列实现栈）。最小栈要求在普通栈的三个操作之上，额外支持 的最小值查询——这是一个经典的”以空间换时间”设计，辅助栈同步维护最小值序列；LeetCode 225 考察用两个 FIFO 队列模拟 LIFO 栈，深化对栈和队列本质差异的理解。两道题的共同点是：在既有数据结构的约束下，通过精心的设计达到额外的功能目标，是系统设计思维的微缩体现。
第 1 章 LeetCode 155：最小栈
1.1 题目
LeetCode 155 - Min Stack（中等）
设计一个支持 push、pop、top 和 getMin 操作的栈，其中 getMin 必须在 时间内运行。
// 接口定义
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // 返回 -3
minStack.pop();
minStack.top(); // 返回 0
minStack.getMin(); // 返回 -21.2 朴素思路的问题
最直接的想法：维护一个全局的 minValue 变量。
// 有缺陷的实现
private int minValue = Integer.MAX_VALUE;
public void push(int val) {
stack.push(val);
minValue = Math.min(minValue, val);
}
public void pop() {
int popped = stack.pop();
if (popped == minValue) {
// ??? 最小值被弹出了，minValue 应该更新为什么？
}
}问题：当最小值元素被 pop() 删除后，我们无法在 时间内知道新的最小值。要恢复，只能重新扫描整个栈，时间 。
1.3 核心设计：辅助最小值栈
解决思路：用一个辅助栈同步追踪每个状态下的最小值。
- 主栈
dataStack：存储所有元素 - 辅助栈
minStack：与主栈同步，minStack.top()始终是当前主栈所有元素的最小值
同步规则：
push(val)：主栈压入val；辅助栈压入Math.min(val, minStack.peek())（若辅助栈为空则直接压入val）pop()：主栈弹出；辅助栈也弹出（保持同步）getMin()：返回minStack.peek()
关键直觉：辅助栈的第 i 个元素，记录的是”当主栈中恰好有 i 个元素时，这 i 个元素的最小值是什么”。每次 pop 时，主栈和辅助栈同步缩减，所以辅助栈顶始终是当前状态的最小值。
示例（操作序列：push(-2), push(0), push(-3), pop(), getMin()）：
push(-2):
dataStack: [-2]
minStack: [-2] ← min of {-2} = -2
push(0):
dataStack: [-2, 0]
minStack: [-2, -2] ← min of {-2, 0} = -2
push(-3):
dataStack: [-2, 0, -3]
minStack: [-2, -2, -3] ← min of {-2, 0, -3} = -3
getMin() → minStack.top() = -3 ✓
pop():
dataStack: [-2, 0]（弹出 -3）
minStack: [-2, -2]（弹出 -3，同步缩减）
top() → dataStack.top() = 0 ✓
getMin() → minStack.top() = -2 ✓
1.4 代码实现
class MinStack {
private Deque<Integer> dataStack;
private Deque<Integer> minStack;
public MinStack() {
dataStack = new ArrayDeque<>();
minStack = new ArrayDeque<>();
}
public void push(int val) {
dataStack.push(val);
// 辅助栈记录当前最小值
int currentMin = minStack.isEmpty() ? val : Math.min(val, minStack.peek());
minStack.push(currentMin);
}
public void pop() {
dataStack.pop();
minStack.pop(); // 同步弹出
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.peek();
}
}复杂度：所有操作时间 ，空间 （辅助栈与主栈大小相同）。
1.5 空间优化：只在最小值变化时才压辅助栈
注意到辅助栈的相邻两个元素，如果上一个元素不比当前的更小，那两个位置值相同，存在冗余。可以改为：只有当新元素 <= 当前最小值时，才往辅助栈压入 val（而不是压 currentMin）。
public void push(int val) {
dataStack.push(val);
// 只在 val 是新的最小值时才压辅助栈
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
int popped = dataStack.pop();
// 只有当弹出的是当前最小值时，辅助栈才同步弹出
if (popped == minStack.peek()) {
minStack.pop();
}
}注意等号：
val <= minStack.peek()必须用
<=而不是<。考虑push(3), push(3), pop()的情况：
- 若用
<：push(3) 压辅助栈 → [3]；第二个 push(3) 不压（不满足 3<3）→ [3]；pop() 弹出 3，由于 3==minStack.peek() 也弹辅助栈 → []- 但此时主栈还有一个 3，
getMin()调用辅助栈为空，错误！- 用
<=：第二个 push(3) 也压辅助栈 → [3, 3]；pop() 弹一次 → [3]；正确
这个优化减少了辅助栈的元素数量（最好情况下，辅助栈只有 1 个元素），但最坏情况（单调递减序列）空间仍是 。
第 2 章 LeetCode 225：用队列实现栈
2.1 题目
LeetCode 225 - Implement Stack using Queues（简单）
仅使用两个队列实现一个后进先出（LIFO）的栈，并支持普通栈的全部四种操作：push、pop、top、empty。
// 示例
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); // 返回 2
stack.pop(); // 返回 2
stack.empty();// 返回 false额外限制：只能使用队列的标准操作（enqueue、dequeue、peek front、size、isEmpty）。
2.2 理解问题的本质
栈是 LIFO：最后入的最先出。
队列是 FIFO：最先入的最先出。
如果用队列存储 [1, 2, 3]（3 是最后入的），队列的自然出队顺序是 1 → 2 → 3（FIFO），而栈需要的出栈顺序是 3 → 2 → 1（LIFO）。
矛盾的核心：我们需要访问队列的”尾部”（最后加入的元素），但队列只允许访问”头部”。
2.3 解法一：push 时搬移（push ，pop ）
让主队列 q1 始终按照”栈顶在前”的顺序存储元素。每次 push 时，把新元素先放入空队列 q2，再把 q1 的所有元素移入 q2，最后交换 q1 和 q2：
初始: q1=[], q2=[]
push(1):
q2 = [1]
q1(空)移入q2，q1和q2交换
q1=[1], q2=[]
push(2):
q2 = [2]
把q1=[1]移入q2 → q2=[2,1]
交换 → q1=[2,1], q2=[]
push(3):
q2 = [3]
把q1=[2,1]移入q2 → q2=[3,2,1]
交换 → q1=[3,2,1], q2=[]
pop() → q1.poll() = 3，q1=[2,1] ✓
class MyStack {
private Queue<Integer> q1; // 主队列，保持栈顶在头部
private Queue<Integer> q2; // 辅助队列
public MyStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
}
public void push(int x) {
q2.offer(x); // 新元素先入 q2
while (!q1.isEmpty()) {
q2.offer(q1.poll()); // q1 全部移入 q2
}
// 交换 q1 和 q2
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
}
public int pop() {
return q1.poll();
}
public int top() {
return q1.peek();
}
public boolean empty() {
return q1.isEmpty();
}
}2.4 解法二：pop 时搬移（push ，pop ）
反过来，push 直接放入 q1，pop/top 时把 q1 除最后一个元素外全部移入 q2，最后一个就是”栈顶”：
public void push(int x) {
q1.offer(x); // O(1)
}
public int pop() {
// 把 q1 除了最后一个元素，全部搬到 q2
while (q1.size() > 1) {
q2.offer(q1.poll());
}
int top = q1.poll(); // 最后一个就是栈顶
// 交换
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
return top;
}2.5 解法三：单队列实现（进阶）
实际上只需要一个队列——push 后，将队列中除新元素外的所有元素循环出队并重新入队，使新元素到达队头：
class MyStack {
private Queue<Integer> q;
public MyStack() {
q = new LinkedList<>();
}
public void push(int x) {
q.offer(x);
// 将 x 之前的所有元素循环到 x 后面（让 x 在队头）
int size = q.size();
for (int i = 0; i < size - 1; i++) {
q.offer(q.poll());
}
// 现在 x 在队头（最近 push 的在最前面）
}
public int pop() {
return q.poll();
}
public int top() {
return q.peek();
}
public boolean empty() {
return q.isEmpty();
}
}直观理解：每次 push 后，循环旋转队列，把新元素旋转到队头。队列内部始终保持”最新入的在前面”的顺序，出队即等同于出栈。
复杂度：push ，pop/top/empty 。
第 3 章 设计题的思维方法
3.1 最小栈的工程映射
最小栈的设计思想——“辅助数据结构同步追踪某种查询结果”——在工程中非常常见：
- 数据库索引：不修改主表数据，通过维护独立的 B+ Tree 索引来支持 查询
- Redis 的 Sorted Set：同时维护 Hash（ 按 key 查 score）和 Skip List（ 按 score 范围查询），以双倍空间支持两种查询模式
- 优先队列 + 惰性删除：某些场景下无法直接从堆中删除任意元素，会维护一个”待删除集合”，在弹出时跳过这些元素
辅助数据结构的设计原则：
- 辅助结构与主结构同步更新（每次主操作后辅助结构也更新）
- 辅助结构记录的是某种”派生信息”（如最小值、前缀和、累计计数）
- 读操作只查辅助结构（），写操作同时更新两者（可能 ）
3.2 栈与队列互转的复杂度分析
| 操作 | 栈模拟队列（LeetCode 232） | 队列模拟栈（LeetCode 225） |
|---|---|---|
| push | （摊还） | （“push 时搬移”方案） |
| pop | （摊还） | （“push 时搬移”方案） |
为什么栈模拟队列的摊还分析是 ？见 03 队列基础：用栈实现队列与循环队列设计 的详细推导。
设计题的面试技巧
这类题目的面试评分维度不只是”能写出来”，还包括：
- 需求澄清：先问清楚”哪些操作允许 ，哪些必须 “，给出相应的权衡
- 多种方案：能给出”push 昂贵”和”pop 昂贵”两种方案，并解释各自的适用场景（push 少/pop 少）
- 边界分析：空栈操作的处理，以及
=与<等细节（最小栈的等号问题）
下一篇预告
03 队列基础：用栈实现队列与循环队列设计 将覆盖队列的对称设计题：LeetCode 232（用栈实现队列），与本篇的 LeetCode 225 形成镜像，并通过摊还分析理解为什么”双栈队列”的摊还时间是 ；LeetCode 622（Design Circular Queue，循环队列）则考察用固定大小数组实现队列时的下标取模技巧，是理解环形缓冲区（Ring Buffer）的绝佳入口。