2.6 如何用两个栈模拟队列操作

难度系数：★★★☆☆　被考察系数：★★★★☆

分析与解答：

题目要求用两个栈来模拟队列，假设使用栈A与栈B模拟队列Q，其中，A为插入栈，B为弹出栈，以实现队列Q。

再假设栈A 和栈B都为空，可以认为栈 A 提供入队列的功能，栈B提供出队列的功能。

要入队列，入栈 A 即可，而出队列则需要分两种情况考虑：

1）如果栈B不为空，那么直接弹出栈 B 的数据。

2）如果栈B为空，那么依次弹出栈A的数据，放入栈B中，再弹出栈 B 的数据。

根据以上思路，实现代码如下：

程序的运行结果为

算法性能分析：

这个算法入队操作的时间复杂度为O（1），出队列操作的时间复杂度则依赖与入队与出队执行的频率。总体来讲，出队列操作的时间复杂度为 O（1），当然会有个别操作需要耗费更多的时间（因为需要从两个栈之间移动数据）。