V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
28hua
V2EX  ›  程序员

三个栈实现一个队列

  •  
  •   28hua · 2015-04-30 13:41:31 +08:00 · 3909 次点击
    这是一个创建于 3477 天前的主题,其中的信息可能已经有所发展或是发生改变。
    保证每个队列操作(在最坏情况下)都只需要常数次的栈操作(警告:非常难!)

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

    问题下的回答看不懂了
    8 条回复    2015-05-03 09:55:18 +08:00
    ryd994
        1
    ryd994  
       2015-04-30 15:31:49 +08:00
    答案2属于脑筋急转弯,窃以为不算答案,真要这么实现早被内存玩死了
    答案1的汉诺塔属于正常人第一反应
    sgissb1
        3
    sgissb1  
       2015-05-01 17:02:36 +08:00
    不是2个栈实现一个队列吗?怎么是三个呢?
    ryd994
        4
    ryd994  
       2015-05-01 23:38:15 +08:00 via Android
    @sgissb1 两个实现起来很简单,但是至少O(n)
    现在要O(1)
    入队压栈A,出队弹栈B
    如果栈B空了,就一个个从栈A倒出过来
    sgissb1
        5
    sgissb1  
       2015-05-02 18:15:53 +08:00
    @ryd994 哦,没注意。
    zwzmzd
        6
    zwzmzd  
       2015-05-03 09:26:47 +08:00 via Android
    其实从摊还角度来看,两个栈的实现平均每次复杂度也是O(1)
    uleh
        7
    uleh  
       2015-05-03 09:53:47 +08:00 via iPhone
    没get到这题的点在哪里…
    汉娜塔有个限制是每堆都必须按从小到大排列,栈和队列又没有这个限制。
    进的时候入栈1,出的时候栈1全部出栈并入栈2,然后按栈2顺序出。
    出栈过程中发生入栈操作则使用栈3。
    不就可以了么。
    uleh
        8
    uleh  
       2015-05-03 09:55:18 +08:00 via iPhone
    @uleh 常数次栈操作…问题是出在这呢
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2325 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 00:02 · PVG 08:02 · LAX 16:02 · JFK 19:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.