GATE 2006
An implementation of a queue Q using two stacks S1 and S2 is given below:
text
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?
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);
}