备考首页> 数据结构> 队列
1

问答题 1 /25

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

参考答案

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

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

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

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

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

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


纠错 收藏
查看讨论
上一题 下一题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号