用栈实现队列：倒一次，队头就在顶上
栈只能从同一头进出。入队先堆进 in；要出队时把 in 整摞倒进 out，最早的那个翻到顶上，再弹就符合先进先出。
push 只压 in。pop 或 peek 时若 out 为空，把 in 全部弹出入 out，in 底部最早的元素成为 out 顶部。out 非空就绝不再倒。每个元素最多被搬一次，均摊 O(1)，最坏单次 O(n)，空间 O(n)。
只能用栈的压入、弹出、看栈顶，实现队列的入队、出队、看队头、判空。栈是后进先出：最后放进去的最先出来。队列是先进先出：先放进去的先出来。两边开口习惯相反。
主例依次 push 1、2、3，再 pop。队列应当弹出 1，留下 2、3。若只用一只栈，弹出的会是 3，顺序反了。
本文要回答：为什么倒一次就能把顺序正过来，为什么 out 里还有货时不能再倒，以及主例三次入栈、一次倒栈、一次弹出分别把两只栈变成什么样。
in 只收新的，out 只发旧的
第一直觉是每次入队都把旧栈倒进临时栈、放下新元素、再倒回来，让栈底永远是队头。这样做对，但每一次 push 都是线性搬运，n 次入队就是平方级。队列真正频繁的往往是「先堆一串，再取一串」，不该为每一次入队付清全部搬家费。
缺的是把「反转」推迟到真正需要队头的那一刻。一只栈负责收新元素，叫 in；另一只栈负责发旧元素，叫 out。push 只往 in 上压，完全不管出队顺序。等到 pop 或 peek，如果 out 是空的，再把 in 里的东西一个一个弹出来、压进 out。倒一次，顺序反一次：原先压在 in 底的最早元素，现在正好在 out 顶。
为什么倒两次等于没倒？元素进 in 时已经被反过一次（后进的在顶上）；整摞倒进 out，再反一次，最早的回到最上面。此后 out 顶就是队头，弹出即可。out 里只要还剩东西，就说明队头仍在 out 顶，新来的 push 继续进 in，两伙人互不打扰。
用手走主例。push 1、2、3，in 从底到顶是 1、2、3，out 空，演示第一帧。第一次 pop 时 out 空，开始倒：3 先从 in 弹进 out，接着 2，最后 1。in 空了，out 从底到顶是 3、2、1，顶上是 1，这是演示第二帧。
弹出 1 之后，out 剩下 3、2，顶上是 2，这是第三帧。下一次 pop 不必再倒，直接得 2。先进的 1 先出，FIFO 成立。
均摊为什么是常数：每个元素只进 in 一次、进 out 一次、出 out 一次。把 n 次操作的搬家总次数摊回去，平均每次是常数。某一次 pop 可能倒掉整摞 in，最坏是 O(n)，但这些元素以后再 pop 就是 O(1)。empty 看两只栈是否都空；peek 和 pop 一样先保证 out 非空，再读栈顶，peek 不弹。
out 非空时若强行再倒，新倒进去的会压在旧队头上面，顺序立刻乱。主例若在弹出 1 之后立刻 push 4，4 应待在 in 里；此时再 pop，必须先拿 out 顶的 2，而不是去碰 4。这是这道设计题最容易写错的一句。
均摊分析倒栈看起来像 O(n)，但每个元素一生只被倒一次。n 次 push/pop 加起来，搬运总次数仍是 O(n)，所以均摊每次 O(1)。不要在 out 非空时倒第二次，那不是优化，是把已经排好的队头埋住。
Go：双栈
type MyQueue struct { in, out []int }func Constructor() MyQueue { return MyQueue{} }func (q *MyQueue) Push(x int) {q.in = append(q.in, x)}func (q *MyQueue) transfer() {if len(q.out) > 0 { return }for len(q.in) > 0 {n := q.in[len(q.in)-1]q.in = q.in[:len(q.in)-1]q.out = append(q.out, n)}}func (q *MyQueue) Pop() int {q.transfer()n := q.out[len(q.out)-1]q.out = q.out[:len(q.out)-1]return n}
1Push 只碰 in，绝不先倒栈。切片末尾当栈顶。
2transfer 开头那句 if len(q.out) > 0 是不变量：out 还有人，队头就在 out 顶，不能把 in 压上去。
3主例三次 Push 后 in=[1,2,3]；第一次 Pop 触发倒栈，out=[3,2,1]，弹出 1。之后 out 非空，再 Pop 直接得 2。
总结
in 收新的；out 空才整摞倒过去。倒一次，最早的翻到顶。主例先弹出 1。
- 一只栈收、一只栈发。两次后进先出叠在一起，变成先进先出。
- 主例 in 里 1、2、3 倒进 out 后顶上是 1；弹出 1 以后顶上是 2，不必再倒。
- out 非空时再倒会把队头埋住。每个元素只搬一次，均摊常数。