Official PYQ · 2006Q49Arrays, Stacks and QueuesMCQ1 mark

GATE CS 2006 Q49 — Arrays, Stacks and Queues

An implementation of a queue $Q$ , using two stacks $S1$ and $S2$ , is given below:

void insert (Q, x) { 
    push (S1, x); 
} 
void delete (Q) { 
    if (stack-empty(S2)) then 
        if (stack-empty(S1)) then { 
            print(“Q is empty”); 
            return; 
        } 
        else while (!(stack-empty(S1))){ 
            x=pop(S1); 
            push(S2,x); 
        } 
    x=pop(S2);
}

Let $n$ insert and $m(\leq n)$ delete operations be performed in an arbitrary order on an empty queue $Q$ . Let $x$ and $y$ be the number of push and pop operations performed respectively in the process. Which one of the following is true for all $m$ and $n$ ?

View worked solution

Answer: A

To find the number of push operations ( $x$ ) and pop operations ( $y$ ), let us track the movement of elements between the two stacks $S1$ and $S2$ :

Push Operations ( $x$ ):
- Each of the $n$ insert operations performs exactly $1$ push onto $S1$ . This contributes $n$ pushes.
- During the $m$ delete operations, some $k$ elements are transferred from $S1$ to $S2$ . Each transferred element requires $1$ push onto $S2$ .
- Since $m$ successful deletes are performed, at least $m$ elements must be transferred to $S2$ , so $k \ge m$ .
- Since only $n$ elements are ever inserted, at most $n$ elements can be transferred, so $k \le n$ .
- Thus, the total number of pushes is $x = n + k$ . Since $m \le k \le n$ , we have: $n + m \le x \le 2n$
Pop Operations ( $y$ ):
- The $k$ elements transferred from $S1$ to $S2$ must be popped from $S1$ . This contributes $k$ pops.
- Each of the $m$ delete operations pops exactly $1$ element from $S2$ . This contributes $m$ pops.
- Thus, the total number of pops is $y = k + m$ . Since $m \le k \le n$ , we have: $2m \le y \le n + m$

Combining these bounds, we get $n+m \le x \le 2n$ and $2m \le y \le n+m$ , which matches Option A.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Arrays, Stacks and Queues questions

GATE CS 2006 Q49 — Arrays, Stacks and Queues

Related questions