用两个栈实现一个队列

分析&回答

最基础的思路。：始终维护s1作为存储空间，以s2作为临时缓冲区。（肯定不 OK）

• 入队时，将元素压入s1。
• 出队时，将s1的元素逐个“倒入”（弹出并压入）s2，将s2的顶元素弹出作为出队元素，之后再将s2剩下的元素逐个“倒回”s1。见下面示意图：

头尾元素考虑优化。 （依然不 OK）

• 入队时，先判断s1是否为空，如不为空，说明所有元素都在s1，此时将入队元素直接压入s1；如为空，要将s2的元素逐个“倒回”s1，再压入入队元素。
• 出队时，先判断s2是否为空，如不为空，直接弹出s2的顶元素并出队；如为空，将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。

来个彻底点的优化。 ：避免了反复“倒”栈，仅在需要时才“倒”一次。

• 入队时，将元素压入s1。
• 出队时，判断s2是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。

反思&扩展

为了大家更加方便的刷题，我们对文章进行了分类和整理，免费为大家提供刷题服务。程序员不欺骗程序员，赶紧扫码小程序刷起来！

为了一站式解决面者刷题问题，部分内容可能存在摘录情况，如有侵权辛苦您留言联系我们，我们会删除文章或添加引用文案，Thanks！