GATE CSE
First time here? Checkout the FAQ!
x
+10 votes
795 views

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 ?

  1. Leaves the queue Q unchanged
  2. Reverses the order of the elements in the queue Q
  3. Deletes the element at the front of the queue Q and inserts it at the rear keeping the other elements in the same order
  4. Empties the queue Q
asked in DS by Veteran (20.8k points)   | 795 views

4 Answers

+13 votes
Best answer

insert() will inserts the value in just reverse order.

answered by Veteran (58.4k points)  
selected by
@ shreshta I have a doubt i.e as Q is not a global structure or static so how various invocation can work on the same queue q. As every invocation will work on their local copies so how an inner invocation can change the value of the queue of the calling function(or outer function).So I think the answer must be c because only the outermost function will have an impact on the original queue.
Can we not do push, push , pop in one stack? then in case of poping only one element is popped. Then why same will not happen in queue?
Because every function invocation will be doing changes to their own local copies which are provided by their parent function and not on the same queue because it is not called by reference but call by value. That's why only the changes made by the outermost invocation i.e the parent or root will be done on the original queue.
any reference ? I donot think call by reference or call by value will make any problem here.
The above answer will be alright if we consider it to be global so that all invocations will be able to make changes to the same Queue. Have you considered it to be global???
+5 votes
ans b)
answered by Boss (5.3k points)  
+5 votes
answer will be b.

explanation...

assume a queue of element 1 2 3 4 5...

now as Q is not empty it will delete 1 and 1 will be sored in i and den again f(Q) will be called which contains element 23456...but the trace (activation of inset (Q,1)) remains.it continues till 5 is deleted and again activation is executed by inserting q(5)...to q(1),,,thus reversing the queue
answered by Veteran (10.6k points)  
is ny other better approach to understand it ?
why it is saved... it is not declared as static and default everything is in activation record please explain this point .
0 votes
Answer: B
answered by Veteran (35k points)  


Top Users Sep 2017
  1. Habibkhan

    6826 Points

  2. Arjun

    2310 Points

  3. Warrior

    2302 Points

  4. nikunj

    1980 Points

  5. A_i_$_h

    1842 Points

  6. manu00x

    1750 Points

  7. Bikram

    1744 Points

  8. SiddharthMahapatra

    1718 Points

  9. makhdoom ghaya

    1690 Points

  10. rishu_darkshadow

    1672 Points


26,033 questions
33,610 answers
79,659 comments
31,066 users