用双栈实现队列：入队与出队的效率对比分析

方案1：入队阶段完成栈间元素迁移 #

核心逻辑：每次入队新元素时，先把存储队首元素的栈（stack_out）里的所有元素全部弹出，压入另一个栈（stack_in）；然后把新元素压入stack_in；最后再把stack_in的所有元素倒回stack_out。这样stack_out的栈顶永远是队列的队首元素，出队时直接弹出stack_out的栈顶即可。

优缺点 #

• 优点：出队操作是严格的O(1)时间复杂度，无论队列里有多少元素，出队都只需要一次栈弹出操作，延迟完全稳定。
• 缺点：每次入队都要完成两次全量栈迁移，时间复杂度为O(n)，元素越多，入队耗时越长，性能波动极大。而且反复遍历所有元素，缓存命中率低，对内存缓存不友好。

方案2：出队阶段完成栈间元素迁移 #

核心逻辑：入队时直接把元素压入stack_in，时间复杂度O(1)；出队时先检查stack_out是否为空——如果为空，就把stack_in里的所有元素弹出并压入stack_out（此时stack_out的栈顶就是队首），然后弹出stack_out的栈顶；如果stack_out不为空，直接弹出栈顶即可。

优缺点 #

• 优点：入队操作是严格的O(1)，性能稳定；出队操作虽然最坏情况是O(n)，但均摊时间复杂度是O(1)——因为每个元素只会被迁移一次，之后出队都是直接弹出。整体吞吐量远高于方案1，缓存友好性也更好，迁移是批量一次性完成的。
• 缺点：出队操作存在性能波动，当stack_out为空时，第一次出队会触发全量迁移，耗时随元素数量增加而变长；对延迟极度敏感的场景，这种突发的耗时增加可能会影响系统稳定性。

适用场景 #

• 方案1适用场景：极端依赖出队延迟稳定的场景，比如某些实时控制系统，要求出队操作的响应时间必须严格可控，不能有任何突发的耗时波动，哪怕牺牲入队性能也要保证出队的即时性。
• 方案2适用场景：绝大多数普通业务场景，尤其是入队操作频繁、或者能接受出队偶尔有一次性能波动的场景。比如消息队列的消费者端、普通任务队列等，这种方案的整体性能更优，吞吐量更高。

内容的提问来源于stack exchange，提问作者Malsha Dilmi