Let S be a stack of size n ≥ 1. Starting with the empty

Home » Programming & Data Structure » Programming and data structure miscellaneous » Question

Let S be a stack of size n ≥ 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operations and the start of the next operation. For m ≥ 1, define the stack – life of m as the time elapsed from the end of Push (m) to the start of the pop operation that removes m from S. The average stack – life of an element of this stack is

1. n (X + Y)
2. 3Y + 2X
3. n (X + Y) – x
4. Y + 2X

Correct Option: C

Let us represent stack-life, of ith element as s(i). The ith element will be in stack till (n–i) elements are
pushed and popped. Plus one more y for the time interval between the push of ith element and the (i+1)th element. So,
S(i) = y + 2(n–i). (y + x)
= y + 2(n – i). z
= y + 2nZ – 2iz
Where z = (y + x).

Average, stack-file will, A = ∑		s(i)
		n

nA = ( ny + 2.n.n.z - 2.z.∑i )

nA = ny + 2.n.n.z - 2.z.		n(n + 1)
		2

n A = ny + 2. n.n.z – z (n.n) – n.z
A = y + 2 nz – (n + 1). z = y + (n–1). z
= y + (n – 1)(y + x) = n(x + y) – x.