[理工] 107台大資演

[gash55025502 (白影弓)]

https://i.imgur.com/gXSnfrP.jpg

大家好 想問一下這題的第二小題
我知道accounting method的方法
課本上的例子是讓enquece的cost設2 dequeue設0
但這題因為有特別說是用stack implement的queue
感覺應該不能用上面的寫法
請問有人知道這題應該怎麼寫嗎？
或者能要一下立宇老師的題庫班講義這題的寫法嗎？感謝～

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.117.248.5 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1576039568.A.C49.html
推 mistel: 把enqueue設3 其中有1是push進stack 1，另外1是pop後push
→ mistel: 進stack 2的成本，第三個1是從stack 2 pop的成本，所以這
→ mistel: 樣也可以分攤成enqueue O(n)，Dequeue 0 不知道對不對...
推 mistel: 覺得基本想法還是dequeue成本不會超過enqueue 然後把成本
→ mistel: 定在每個元素的push和pop，但我才剛學amortized analysis
→ mistel: ，講錯請鞭小力點qq
→ gash55025502: 感覺蠻有道理的！感謝