Register

Stack

1,568 views
1 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).

2 Answers

Best answer
6 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 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
Voting & Accepting an answer helps improve the community
← Previous · How to determine the...Next → · Madeeasy test series
← Previous in category · StackNext in category → · #madeeasytestseries
Position:
Show:

Related questions

9 9 votes
2 2 answers
420
420 views
GO Classes asked Jul 27
420 views
GO Classes DPP | GATE CS, DA | Data Structure | Stack and Queue Transfer
Given a stack $S$ with $5$ elements from top to bottom as:$2, 4, 6, 8, 10$and an empty queue $Q$.First, remove the elements one by one from $S$ and insert them into $Q$.T...
7 7 votes
1 1 answer
493
493 views
GO Classes asked Jul 27
493 views
GO Classes DPP | GATE CS, DA | Data Structure | Stack & Queue
Which of the following statements are true?$\text{S1.}$ Stack operations $\texttt{push}$, $\texttt{pop}$, and $\texttt{isEmpty}$ can be worst-case $O(1)$ for a linked-lis...
7 7 votes
1 1 answer
319
319 views
GO Classes asked Jul 10
319 views
GO Classes DPP | GATE CS, DA | Data Structure | Stack Implementation & DFS
Assume there are $n$ elements in the data structure. Consider the following statements:$\text{S1}:$ A stack can be implemented using a linked list such that each individu...
6 6 votes
3 3 answers
326
326 views
GO Classes asked Jul 8
326 views
GO Classes DPP | GATE CS, DA | Data Structure | Stack Permutation
Suppose an intermixed sequence of stack push and pop operations is performed. The push operations push the integers $0$ through $9$ in order. The pop operations print the...