GATE IT 2007 | Question: 30

Question

Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:

1. $isEmpty (Q)$ — returns true if the queue is empty, false otherwise.
2. $delete (Q)$ — deletes the element at the front of the queue and returns its value.
3. $insert (Q, i)$ — inserts the integer i at the rear of the queue.

Consider the following function:

void f (queue Q) {
int i ;
if (!isEmpty(Q)) {
   i = delete(Q);
   f(Q);
   insert(Q, i);
  }
}

What operation is performed by the above function $f$ ?

• A. Leaves the queue $Q$ unchanged
• B. Reverses the order of the elements in the queue $Q$
• C. Deletes the element at the front of the queue $Q$ and inserts it at the rear keeping the other elements in the same order
• D. Empties the queue $Q$

Comments

I think the program will never come to execute insert(Q, i) operation because the program recurse before it and as it become empty the isEmpty() becomes true and if section becomes false and it should not enter that setion and terminates.

Kindly tell me where I am wrong.

---

i also have the same doubt, initially it goes on deleting the elements from the queue and then the loop condition becomes false. So how are we executing the insert(q,i) statement...

---

@Anand Mundhe

According to me,

implementing using arrays : call by reference is default.

implementing using linked list : you are sending a pointer of the queue, which is also call by reference.

So I think we don’t have to worry about call by value here

Answer 1

Here is traced out recursive tree.

Answer: Option B

Answer 2

In this recursion, queue is being deleted by one element every time and getting saved in i. And again the function calls itself. When queue becomes empty, the last element will be inserted first in the queue. This will be for all the elements present. Thus, it reverses the order of elements in the queue.

Answer 3

Storing an element in a recursive function before you recurse is equivalent to storing in a stack, so you are taking elements from a queue and putting them in the stack. When the queue is empty you are inserting them back into the Queue.

This is how you reverse a queue with a stack.

Comments

When all the elements are deleted, the if condition will be false and we will be out of the statement so how will the insert(Q,i) statement executes?

---

isEmpty will evaluate to true, we are negating it, thus we will exit the last call.

Answer 4

This is a recursive program let Queue contians 1,2,3,4  and we can make recursion tree as

Now Traverse this recursion tree 

insert(4) 

4

insert(3)

4

3

insert(2)

4

3

2

insert(1)

4

3

2

1

So queue got reversed

Answer(b)