GATE Overflow Test Series | Data Structures | Test 1 | Question: 29

Question

Consider a STACK being implemented using two QUEUES by favoring the PUSH operations to POP. If $k$ PUSH operations and $l$ POP operations are done on this STACK with $n$ elements initially $(k,l << n)$, the minimum sum of the corresponding ENQUEUE and DEQUEUE operations will be

• A. $O(kl)$
• B. $O(ln)$
• C. $O(k+l)$
• D. $O(k)$

Answer 1

While we implement a STACK by a QUEUE, we can make either the PUSH or POP operation $O(1)$ and the other will be $O(n).$ Here, PUSH operation is being favored and so it will be $O(1)$ and POP will be $O(n).$

So, after $k$ PUSH and $l$ POP operations, total operations will be $O(k) + O(ln) = O(ln)$ since $(k << n).$