1

问答题 1 /22

用两个栈实现一个队列的功能?要求给出算法和思路!

参考答案

设2个栈为A,B, 一开始均为空.

入队: 将新元素push入栈A; 

出队: (1)判断栈B是否为空;

 (2)如果不为空,则将栈A中所有元素依次pop出并push到栈B;

 (3)将栈B的栈顶元素pop出; 

这样实现的队列入队和出队的平摊复杂度都还是O(1), 比上面的几种方法要好。