栈和队列互相实现这类题，最容易写成“背 API”的题。其实它考的不是 push、pop、offer、poll 会不会用，而是你能不能在受限操作里维护正确的顺序。
- 栈：后进先出。最后进去的元素最先出来。
- 队列：先进先出。最早进去的元素最先出来。
所以这篇只抓一个问题：怎么把一种顺序改造成另一种顺序，并且在每次操作后都不乱。
结论
| 目标 | 做法 | 关键点 |
|---|---|---|
| 用栈实现队列 | 两个栈，一个收新元素，一个吐老元素 | out 空了才从 in 倒，倒就一次倒完 |
| 用队列实现栈 | 一个队列，每次 push 后旋转旧元素 | 新元素必须被转到队头，队头始终是栈顶 |
前者是“需要出队时再整理”，所以 pop / peek 是均摊 O(1)。后者是“入栈时立刻整理”，所以 push 是 O(n)，但 pop / top 很轻。
两个栈实现队列
队列要的是先进先出，但单个栈天然会把顺序反过来。解决办法很直观：反两次，顺序就回来了。
新元素先进入 in 栈：
push 1, 2, 3
in: [1, 2, 3] 栈顶是 3out: []当需要弹出队头时，把 in 全部倒进 out：
in: []out: [3, 2, 1] 栈顶是 1这时 out.pop() 弹出的就是最早入队的 1。队列顺序靠的就是这一次完整翻转。
倒数据的两条铁律
这里真正重要的不是“有两个栈”，而是倒数据的时机：
- 只有
out为空时，才能从in往out倒。 - 只要开始倒，就必须把
in一次倒完。
如果 out 里还有旧元素，你又把新元素倒进去，新元素会压在旧元素上面，出队顺序就被破坏了。如果只倒一部分，留在 in 栈底的老元素会被后来进来的新元素盖住，也会乱。
可以把 out 理解成“已经排好队、等待出队的一批元素”。只要这批元素还没出完，新来的元素就只能待在 in 里排下一批。
代码实现
class MyQueue {
public Stack<Integer> in; public Stack<Integer> out;
public MyQueue() { in = new Stack<Integer>(); out = new Stack<Integer>(); }
// 倒数据：从 in 栈倒入 out 栈 // 铁律 1：out 空了才能倒 // 铁律 2：只要倒，就必须把 in 全部倒完 private void inToOut() { if (out.empty()) { while (!in.empty()) { out.push(in.pop()); } } }
public void push(int x) { // 新元素先进入 in，排在下一批等待出队 in.push(x); // 如果 out 为空，就顺手把 in 倒过去；out 不空则不会影响旧元素先出 inToOut(); }
public int pop() { // 出数据是从out出的 // 如果 out 为空，会从 in 补一批,因为可能出现： // in: [2, 3] // out: [] inToOut(); return out.pop(); }
public int peek() { // 和 pop 一样，先保证 out 栈顶是当前队头 inToOut(); return out.peek(); }
public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}这里容易误会的一点是：inToOut() 不是每次调用都会倒数据。它内部先判断 out.empty()，只有 out 空了，才会把 in 一次性倒过去；如果 out 不空，就什么都不做。
具体过程是这样：
push(1)in: [1]out: []
out 为空，inToOut() 真正倒数据：in: []out: [1]
push(2)in: [2]out: [1]
out 不空，inToOut() 什么都不做：in: [2]out: [1]
所以 1 仍然在 out 栈顶，先出。
如果后面 out 被弹空了，再执行 pop() / peek()：in: [2, 3]out: []
out 为空，inToOut() 把 in 全部倒过去：in: []out: [3, 2] 栈顶是 2
这时 out.pop() / out.peek() 拿到的就是队头 2。可以这样记：
push：先放进 in，再尝试倒pop：先尝试倒，再从 out 弹peek：先尝试倒，再从 out 看核心不是“每次都倒”，而是：每次操作前后调用 inToOut() 都没问题，因为它只在 out 为空时真正执行。
LeetCode 调用格式平台上的原始输入会写成方法名数组和参数数组，输出则是每一步调用的返回值：
最容易错的两种写法
第一种是 out 非空也继续倒：
private void inToOut() { while (!in.empty()) { out.push(in.pop()); }}假设 out 栈顶已经是队头 1，这时又把 in 里的新元素倒进去，新元素会压到 1 上面，下一次弹出的就不是队头了。
第二种是只倒一个元素：
private void inToOut() { if (out.empty() && !in.empty()) { out.push(in.pop()); // 只倒了一个！ }}这会让 in 栈底部的老元素继续被压在下面，后续再加入新元素时，老元素就不可能按队列顺序先出来。
口诀
in负责进，out负责出；out空了才倒，倒就倒干净。
一个队列实现栈
队列只能从队尾进、队头出。想让它表现得像栈，就要让“最后加入的元素”立刻来到队头。
做法放在 push 上：先把新元素正常入队，再把它前面的所有旧元素依次从队头取出，重新放到队尾。
例如队列当前是 [2, 1]，队头是 2，表示栈顶是 2。现在执行 push(3)：
入队 3 → [2, 1, 3]旋转第 1 个 → [1, 3, 2]旋转第 2 个 → [3, 2, 1] ← 3 到了队头，正是栈顶这样一来，队头永远保存栈顶。pop() 就是 queue.poll()，top() 就是 queue.peek()。
代码实现
class MyStack {
Queue<Integer> queue;
public MyStack() { queue = new LinkedList<Integer>(); }
// O(n)：先记录旧元素个数，再把它们旋转到新元素后面 public void push(int x) { int n = queue.size(); queue.offer(x); for (int i = 0; i < n; i++) { queue.offer(queue.poll()); } }
public int pop() { return queue.poll(); }
public int top() { return queue.peek(); }
public boolean empty() { return queue.isEmpty(); }
}为什么要先记录 n = queue.size()？因为 n 表示这次 push 之前的旧元素个数。新元素入队后，只需要把这 n 个旧元素转到后面，新元素就会停在队头。
LeetCode 调用格式平台上的原始输入会写成方法名数组和参数数组，输出则是每一步调用的返回值：
旋转次数别写错
最常见的错误，是把循环条件写成动态的 queue.size()：
public void push(int x) { queue.offer(x); for (int i = 0; i < queue.size(); i++) { // 错！size 包含了刚入队的新元素 queue.offer(queue.poll()); }}这里有两个问题。第一，queue.size() 包含刚入队的新元素，旋转次数会多一次，新元素可能又被转回队尾。第二，循环过程中虽然 poll 和 offer 让总大小看起来没变，但代码表达的是一个会被操作影响的状态，读起来也很危险。
正确做法是：入队前先记住旧元素个数。
public void push(int x) { int n = queue.size(); queue.offer(x); for (int i = 0; i < n; i++) { queue.offer(queue.poll()); }}口诀新元素入队，旧元素全部轮转到后面，队头永远是栈顶。
复杂度对比
| 实现 | push | pop | peek / top | empty | 空间 |
|---|---|---|---|---|---|
| 双栈实现队列 | O(1) | 均摊 O(1) | 均摊 O(1) | O(1) | O(n) |
| 单队列实现栈 | O(n) | O(1) | O(1) | O(1) | O(n) |
双栈队列的均摊 O(1) 来自一个事实：每个元素最多进 in 一次，再从 in 倒到 out 一次，不会被反复搬来搬去。
单队列栈则把整理成本固定放在 push 上：每加入一个新元素，都要把旧元素轮转一遍。
记法
这两题可以放在一起记：
- 队列要老元素先出：用
out保存已经排好顺序的一批老元素，out空了才补货。 - 栈要新元素先出：每次
push后立刻把新元素转到队头，让它下一次第一个出来。
一个是“分批翻转”，一个是“即时旋转”。把这两个动作想清楚，代码基本就不会写乱。
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时