用栈实现队列

怎样从“用两个栈实现队列,依次 push 1,2,pop 应得 1。”推导出 队列 · 双栈，并证明每次状态变化都不会漏掉答案？

中心结论：in 栈负责 push;pop/peek 时若 out 空则把 in 全部倒入 out。

题目要求用栈实现一个队列的基本操作：push(x)、pop()、peek()、empty()。

在本站主例中，用两个栈实现队列,依次 push 1,2,pop 应得 1。

算法最终需要得到或观察：pop 返回 1,队列 FIFO 成立。

每一步重新回看全部历史会重复；栈或队列只保存仍可能影响未来决策的状态。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“栈与队列轨道”，明确答案需要观察什么。
2. 2状态只维护 in 栈、out 栈、待出队元素。
3. 3转移每一步按照 in 栈负责 push;pop/peek 时若 out 空则把 in 全部倒入 out。
4. 4收尾读取 pop 返回 1,队列 FIFO 成立。，并复核边界与复杂度。

入栈/入队的不是所有历史，而是未来仍需要的信息。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：in 栈、out 栈、待出队元素。

in 栈负责 push;pop/peek 时若 out 空则把 in 全部倒入 out。

执行过程中持续维护：in 栈、out 栈、待出队元素。

正确性依赖以下不变量：out 栈顶是队头;仅 out 空时才倒 in。

面试时可以压缩为：in/out 双栈:push→in;pop/peek 若 out 空则倒 in;均摊 O(1)。

落到当前题，执行机制可以压缩为：in 栈负责 push;pop/peek 时若 out 空则把 in 全部倒入 out。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入用两个栈实现队列,依次 push 1,2,pop 应得 1。 因为：in 栈负责 push;pop/peek 时若 out 空则把 in 全部倒入 out。
2. 2in 栈负责入队,out 栈负责出队双栈实现队列。 因为：倒入一次后 out 栈顶是最先入队的。
3. 3enqueue 2 → 压入 in 栈入队走 in 栈。 因为：push O(1)。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5out 空,把 in 全部倒入 out摊还 O(1) 的倒入。 因为：每个元素最多进出各一次。
6. 6dequeue → 1从 out 栈弹出队首。 因为：FIFO 语义成立。
7. 7dequeue → 2从 out 栈弹出队首。 因为：FIFO 语义成立。
8. 8收尾与复杂度pop 返回 1,队列 FIFO 成立。 因为：时间 均摊 O(1) · 空间 O(n)。in 栈负责 push;pop/peek 时若 out 空则把 in 全部倒入 out。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

type MyQueue struct {
	Stack *[]int
	Queue *[]int
}

/** Initialize your data structure here. */
func Constructor() MyQueue {
	tmp1, tmp2 := []int{}, []int{}
	return MyQueue{Stack: &tmp1, Queue: &tmp2}
}

/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int) {
	*this.Stack = append(*this.Stack, x)
}

/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
	if len(*this.Queue) == 0 {
		this.fromStackToQueue(this.Stack, this.Queue)
	}

	popped := (*this.Queue)[len(*this.Queue)-1]
	*this.Queue = (*this.Queue)[:len(*this.Queue)-1]
	return popped
}

/** Get the front element. */
func (this *MyQueue) Peek() int {
	if len(*this.Queue) == 0 {
		this.fromStackToQueue(this.Stack, this.Queue)
	}

	return (*this.Queue)[len(*this.Queue)-1]
}

/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
	return len(*this.Stack)+len(*this.Queue) == 0
}

func (this *MyQueue) fromStackToQueue(s, q *[]int) {
	for len(*s) > 0 {
		popped := (*s)[len(*s)-1]
		*s = (*s)[:len(*s)-1]

		*q = append(*q, popped)
	}
}

func main() {
    // 1. 主例
    //    输入：mode="queue-from-stacks", ops=["push 1","push 2","pop","push 3","pop"]
    //    期望：pop 返回 1,队列 FIFO 成立。
    //
    // 2. 失败 / 未命中
    //    检查：每次 pop 都倒 in,均摊失效。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC225 用队列实现栈；LC20 有效括号
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意用两个栈实现队列,依次 push 1,2,pop 应得 1。
2. 2重复每一步重新回看全部历史会重复；栈或队列只保存仍可能影响未来决策的状态。
3. 3优化in 栈负责 push;pop/peek 时若 out 空则把 in 全部倒入 out。
4. 4证明out 栈顶是队头;仅 out 空时才倒 in。
5. 5复杂度时间 均摊 O(1)，空间 O(n)