Suppose you are given an implementation of a queue of integers. The operations…
2024
Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:
i. isEmpty (Q) — returns true if the queue is empty, false otherwise.
ii. delete (Q) — deletes the element at the front of the queue and returns its value.
iii. 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
Attempted by 6 students.
Show answer & explanation
Correct answer: B
Concept:
A recursive call that stashes a value in its own local variable BEFORE recursing further, and only acts on that stashed value AFTER the recursive call returns, produces a last-in-first-out unwind: the outermost call's stashed value is the last one acted upon, while the innermost call's stashed value is the first one acted upon. This is the standard 'recursion behaves like a stack' principle, and it flips whatever ordering the values had on the way down when it is applied on the way back up.
Application:
Take Q = [10, 20, 30] (10 at the front, 30 at the rear) and call f(Q).
Call 1: i = delete(Q) removes 10, leaving Q = [20, 30]; call 1 then calls f(Q) again and waits.
Call 2 (inside call 1): i = delete(Q) removes 20, leaving Q = [30]; call 2 then calls f(Q) again and waits.
Call 3 (inside call 2): i = delete(Q) removes 30, leaving Q = []; call 3 then calls f(Q) again and waits.
Call 4 (inside call 3): isEmpty(Q) is true, so call 4 does nothing and returns immediately — this is the base case.
Control returns to call 3, which now runs insert(Q, 30): Q becomes [30].
Control returns to call 2, which now runs insert(Q, 20): Q becomes [30, 20].
Control returns to call 1, which now runs insert(Q, 10): Q becomes [30, 20, 10].
Cross-check:
Generalising the trace: for a queue of n elements, the k-th call (counting from the outermost) deletes the k-th element from the original front and does not reinsert it until calls k+1 through n have all finished and reinserted their own elements. So the reinsertion order is n, n-1, ..., 1 — the element that was originally at the rear is reinserted first, and the element that was originally at the front is reinserted last. That is exactly a full reversal, matching the 3-element trace: [10, 20, 30] became [30, 20, 10].
So f reverses the order of the elements in the queue Q.