三个栈实现一个队列

2015 年 4 月 30 日

28hua

保证每个队列操作(在最坏情况下)都只需要常数次的栈操作(警告:非常难!)

http://www.oschina.net/question/585840_119204

问题下的回答看不懂了

4666 次点击

所在节点

8 条回复

ryd994

2015 年 4 月 30 日

答案2属于脑筋急转弯，窃以为不算答案，真要这么实现早被内存玩死了
答案1的汉诺塔属于正常人第一反应

rock_cloud

2015 年 4 月 30 日

sgissb1

2015 年 5 月 1 日

不是2个栈实现一个队列吗？怎么是三个呢？

ryd994

2015 年 5 月 1 日

@sgissb1 两个实现起来很简单，但是至少O(n)
现在要O(1)
入队压栈A，出队弹栈B
如果栈B空了，就一个个从栈A倒出过来

sgissb1

2015 年 5 月 2 日

@ryd994 哦，没注意。

zwzmzd

2015 年 5 月 3 日

其实从摊还角度来看，两个栈的实现平均每次复杂度也是O(1)

uleh

2015 年 5 月 3 日

没get到这题的点在哪里…
汉娜塔有个限制是每堆都必须按从小到大排列，栈和队列又没有这个限制。
进的时候入栈1，出的时候栈1全部出栈并入栈2，然后按栈2顺序出。
出栈过程中发生入栈操作则使用栈3。
不就可以了么。

uleh

2015 年 5 月 3 日

@uleh 常数次栈操作…问题是出在这呢

第 1 页／共 1 页

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.