768 views
1 votes
1 votes

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

2 Answers

Best answer
6 votes
6 votes
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
1 votes
1 votes
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

Related questions

0 votes
0 votes
1 answer
1
Abhrajyoti00 asked Oct 29, 2022
718 views
Can there be “Stack Overflow” in Linked list Implementation of stack? If Yes, how?