in DS
574 views
1 vote
1 vote

Let S be a stack of size 4 ≥ 1 and it is initially empty. Suppose we push the numbers 1, 2, 3, 4 in sequence and then perform 4 pop operations. Let one push operation takes 5 ns; one pop operation takes 5 ns; the time between the end of one such stack operation and the start of the next operation is 2 ns. The stack-life
of a particular element p ≥ 1 is defined as the time elapsed from the end of push (p) to the start of the pop operation that removes p from the stack. The average stack-life of an element of this stack is ___________ (in ns).

in DS
574 views

2 Answers

6 votes
6 votes
Best answer
avg life time of stack is calculated as n(x+y)-x

where n = number of input (4)

            x = number of push/pop operation performed in a stack (5ns)

           y = elasped time (2ns)

so 4(5+2)-5 =23ns
selected by

4 Comments

23 is correct
1
1

 just_bhavana  thnx for correcting me

1
1

 would u like to have some kheer...

0
0
1 vote
1 vote
Ans is 23ns.

Lets say every iPUSH and iPOP operation takes 'X' ns, where 'i' represents the element index.
Let 'Y' ns be the delay between two consecutive PUSH and POP operation.
Since it is a stack of 4elements. The operations will be in the order :
1PUSH -> 2PUSH -> 3PUSH -> 4PUSH -> 4POP -> 3POP -> 2POP -> 1POP

For 4th element, stack-life = Y
For 3rd element, stack-life = Y+4PUSH+Y+4POP+Y = 3Y +2X
For 2nd element, stack-life = Y+3PUSH+Y+4PUSH+Y+4POP+Y+3POP+Y= 5Y + 4X
For 1st element, stack-life = Y+2PUSH+Y+3PUSH+Y+4PUSH+Y+4POP+Y+3POP+Y+2POP+Y = 7Y + 6X

So, average stack-life of an element = ((Y)+(3Y+2X)+(5Y+4X)+(7Y+6X))/4 = (16Y + 12X)/4 = 4Y + 3X
Given in question, Y=2ns; X=5ns
Ans : ((4*2) + (3*5)) = 23ns