23 is correct

Dark Mode

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).

6 votes

Best answer

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

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