Gate CS-2006 Question Paper With Solutions

Q. 69 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 (<=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? Answer: (A)

Explanation: