题:
设 S 是一个大小为 n >= 1 的堆栈。从空堆栈开始，假设我们按顺序压入前 n 个自然数，然后执行 n 个弹出操作。
假设 Push 和 Pop 操作各需要 X 秒，并且在一个这样的堆栈操作结束和下一个操作开始之间经过 Y 秒。
对于 m >= 1，将 m 的堆栈生命周期定义为从 Push(m) 结束到从 S 中删除 m 的弹出操作开始所耗时。此堆栈中元素的平均堆栈生命周期为
(A) n(X+ Y)
(B) 3Y + 2X
(C) n(X + Y)-X
(D) Y + 2X
问题取自此 Link
我的方法:
For n elements Push takes X time, hence for m elements Push takes m/n*X
For n elements Pop takes X time, hence for m elements Push takes m/n*X
Interval Time is m/n*Y
Stack Life = End of Push(m) to start of Pop(m) = Interval Time = m/n*Y
Average Stack Life = (m/n*Y) / m = Y/n
没有一个答案是匹配的。
请指导我正确的方法来实现我的目标。
最佳答案
这是我的方法:
Stack lifetime of nth element -> Y
For (n-1)th -> 2X+2Y + stack lifetime of nth element = 2X + 3Y
For (n-2)th -> 2X+2Y + stack lifetime of (n-1)th element = 4X + 5Y
..
..
For 1st -> 2(n-1)X + (2n-1)Y
Sum of all life spans= (Σ 2(n-1)X) + (Σ (2n-1)Y)对于 n = 1 到 n通过上述从 1 到 n 的总和计算总和，您将得到:
Sum = n(n(X+Y)-X)
Therefore Average = Sum/n = n(X+Y)-X . Hence Option (c)
这个问题在这里被问到:http://geeksquiz.com/data-structures-stack-question-7/
关于data-structures - 堆栈生命周期，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24464942/