本文详解如何仅用两个标准队列（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 <blockquote><p>⚠️ 注意：原代码中 Queue.add() 实际实现的是<strong>头插法（类似栈压入）</strong>，违背队列“先进先出”语义；而 remove(int i) 方法逻辑混乱（参数未使用、重复减 N），导致 pop 过程不可控。本实现严格遵循队列规范：offer() 尾插、poll() 头删。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2870" title="Gradle 9.8.0"><img
src="https://img.php.cn/upload/manual/001/431/639/6ad9ce71d8cb6379.png" alt="Gradle 9.8.0" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2870" title="Gradle 9.8.0" class="overflowclass">Gradle 9.8.0</a>
<p class="overflowclass"></p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2870" title="Gradle 9.8.0" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div></blockquote><h3>✅ 正确实现：MyStack（双队列模拟栈）</h3><pre class="brush:php;toolbar:false;">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) 为例）：
- 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），提升可维护性。
通过此实现，你不仅能解决作业要求，更能深入掌握数据结构间“行为模拟”的设计哲学。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
