![Go程序员面试算法宝典](https://wfqqreader-1252317822.image.myqcloud.com/cover/262/26268262/b_26268262.jpg)
上QQ阅读APP看书,第一时间看更新
2.6 如何用两个栈模拟队列操作
难度系数:★★★☆☆
被考查系数:★★★★☆
分析与解答:
题目要求用两个栈来模拟队列,假设使用栈A与栈B模拟队列Q,A为插入栈,B为弹出栈,以实现队列Q。
再假设A和B都为空,可以认为栈A提供入队列的功能,栈B提供出队列的功能。
要入队列,入栈A即可,而出队列则需要分两种情况考虑:
(1)如果栈B不为空,则直接弹出栈B的数据。
(2)如果栈B为空,则依次弹出栈A的数据,放入栈B中,再弹出栈B的数据。
实现代码如下:
![](https://epubservercos.yuewen.com/C814A1/14700476404565706/epubprivate/OEBPS/Images/87_01.jpg?sign=1739355453-Bhe8Znzr0dr7xdrENzxaJZEZyTa7hG92-0-11cd82f7c1e79775618ac6cca8e72333)
程序的运行结果为
![](https://epubservercos.yuewen.com/C814A1/14700476404565706/epubprivate/OEBPS/Images/87_02.jpg?sign=1739355453-WUxjib4P5gFMtPxGn6H5bN8vtPigpjh4-0-44d155b24c5100cbe7fa51d4418504e4)
算法性能分析:
这种方法入队操作的时间复杂度为O(1),出队列操作的时间复杂度则依赖于入队与出队执行的频率。总体来讲,出队列操作的时间复杂度为O(1),当然会有个别操作需要耗费更多的时间(因为需要从两个栈之间移动数据)。