用两个栈实现一个队列

分析&回答

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

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

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

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

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

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

反思&扩展