本文详解如何仅用两个标准队列（fifo）模拟栈（lifo）行为，通过合理调度元素迁移实现高效 push 和 pop，并提供可运行、符合逻辑的完整 java 实现。
本文详解如何仅用两个标准队列（fifo）模拟栈（lifo）行为，通过合理调度元素迁移实现高效 push 和 pop，并提供可运行、符合逻辑的完整 java 实现。
在经典数据结构问题中，“用两个队列实现栈”考察对 FIFO 与 LIFO 本质差异的理解与转换能力。核心思想是：始终保证一个队列（如 out）按栈序（后进先出）存储元素，另一个（如 in）作为临时缓冲区。每次 push(x) 时，将新元素插入 in，再把 out 中所有现存元素逐个移入 in，最后交换两队列引用——这样 x 就成为 out 的新队首，从而在下次 pop() 时被最先取出，完美复现栈顶行为。
以下为清晰、健壮、可直接运行的实现：
✅ 正确实现：MyQueue（链表实现的队列）
class MyQueue {
static class Node {
int val;
Node next;
Node(int val) { this.val = val; }
}
private Node head = null, tail = null;
private int n = 0;
public boolean offer(int val) {
Node node = new Node(val);
if (head == null) {
head = node;
} else {
tail.next = node;
}
tail = node;
n++;
return true;
}
public int poll() {
if (n <= 0) throw new RuntimeException("Queue is empty");
int val = head.val;
head = head.next;
n--;
if (n == 0) tail = null;
return val;
}
public int size() { return n; }
public boolean isEmpty() { return n == 0; }
}⚠️ 注意：原代码中 Queue.add() 实际实现的是头插法（类似栈压入），违背队列“先进先出”语义；而 remove(int i) 方法逻辑混乱（参数未使用、重复减 N），导致 pop 过程不可控。本实现严格遵循队列规范：offer() 尾插、poll() 头删。
Java注释规范Skills下载当用户要求为 Java 代码添加注释、修改注释、审查注释、整理注释格式，或要求按照代码注释规范处理 Java 文件时，使用本技能。本技能用于统一生成和维护 Java 类注释模板、按 Git 对比 release 判断版本号、补充每行代码上方中文块注释、调整注释空行规则，并保持 Java 文件 UTF-8 无 BOM 编码。典型触发场景包括：补充类注释、更新 @version、检查 @author 来源、整理行尾注释、把注释放到代码上一行、检查注释是否符合规范、构建前检查 Java 注释风格。
✅ 正确实现：MyStack（双队列模拟栈）
import java.util.EmptyStackException;
public class MyStack {
private MyQueue in = new MyQueue();
private MyQueue out = new MyQueue();
public int push(int val) {
// 1. 新元素入 in
in.offer(val);
// 2. 将 out 中所有元素迁移到 in（保持栈序）
while (!out.isEmpty()) {
in.offer(out.poll());
}
// 3. 交换引用：让 in 成为新的 out（即栈顶在队首）
swapInAndOut();
return val;
}
public int pop() {
if (out.isEmpty()) {
throw new EmptyStackException();
}
return out.poll(); // 直接取 out 队首 —— 即栈顶
}
private void swapInAndOut() {
MyQueue temp = in;
in = out;
out = temp;
}
// 辅助方法：便于验证（非必需）
public boolean isEmpty() { return out.isEmpty(); }
public int size() { return out.size(); }
}✅ 使用示例与输出验证
public class Main {
public static void main(String[] args) {
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 输出: 3
System.out.println(stack.pop()); // 输出: 2
stack.push(4);
System.out.println(stack.pop()); // 输出: 4
System.out.println(stack.pop()); // 输出: 1
}
}执行逻辑说明（以 push(1)→push(2)→push(3) 为例）：
立即学习“Java免费学习笔记（深入）”；
- push(1)：in=[1] → out=[] → 交换 → out=[1]
- push(2)：in=[2] → 迁移 out → in=[2,1] → 交换 → out=[2,1]
- push(3)：in=[3] → 迁移 out → in=[3,2,1] → 交换 → out=[3,2,1]
此时 out.poll() 总返回 3、2、1，完全符合栈 LIFO 特性。
? 关键总结
- 时间复杂度：push() 为 O(n)（因需迁移全部元素），pop() 为 O(1)；若追求均摊 O(1)，可采用“懒迁移”策略（仅在 pop 时转移），但本教程以清晰性优先。
- 避免陷阱：勿在队列中使用头插、勿在 pop 中做无效遍历或值比较（如原代码中的 if(q1curr.data == x)），队列操作应基于位置而非内容匹配。
- 命名语义化：类名应反映抽象意图（如 MyStack 而非 DoubleQueue），提升可维护性。
通过此实现，你不仅能解决作业要求，更能深入掌握数据结构间“行为模拟”的设计哲学。
