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

【出自JD面试题】

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

分析与解答：

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

再假设栈A和栈B都为空，可以认为栈A提供入队列的功能，栈B提供出队列的功能。要入队列，入栈 A 即可，而出队列则需要分两种情况考虑：

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

2）如果栈B为空，则依次弹出栈A的数据，放入栈B中，再弹出栈B的数据。实现代码如下：

程序的运行结果为

算法性能分析：

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