Suppose you are given an implementation of a queue of integers Consider the…
2007
Suppose you are given an implementation of a queue of integers
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
Attempted by 463 students.
Show answer & explanation
Correct answer: B
Answer: The function reverses the order of the elements in the queue.
How it works:
Base case: If the queue is empty, do nothing and return.
Recursive step: Remove the element at the front and store it in a variable.
Call the function recursively on the smaller queue (the remaining elements).
After the recursive call returns, insert the stored element at the rear of the queue. This places earlier front elements toward the rear, producing a reversal.
Example:
Start with [1, 2, 3, 4]. The function removes 1, then recurses on [2,3,4].
After all recursive calls complete, elements are reinserted in reverse order producing [4, 3, 2, 1].
Complexity:
Time: O(n), because each element is removed once and inserted once.
Space: O(n) auxiliary due to recursion stack (depth n).
A video solution is available for this question — log in and enroll to watch it.