169. Interleave the First Half of a Queue With the Second Half

Given a queue of n integers (n even), rearrange it by interleaving the first half with the second half: first element of the first half, first element of the second half, second element of the first half, second element of the second half, and so on. Print the result, front to back.

Input: The first line contains an integer n (guaranteed even). The second line contains n space-separated integers, the queue's values from front to back. Output: Print the interleaved values, space-separated, front to back, on one line.

2 <= n <= 10^5, n is even

This only works cleanly because n is guaranteed even, so both halves are exactly equal in size - an odd-length version would need an explicit decision about which half gets the 'extra' middle element.

Split a queue exactly down the middle, then weave the two halves back together, alternating one element from each half. Brute force: Dump the entire queue into an array, manually compute the interleaved order using index arithmetic, then rebuild the queue from that array - correct, but doesn't take advantage of the queue's own natural splitting/dequeuing operations directly. Optimised: Splitting into exactly two queues (front half and back half) and then alternately draining one element from each directly produces the interleaved order, using only basic enqueue/dequeue operations with no separate index-arithmetic bookkeeping needed.

Dequeue every element of the queue into a plain array so it can be indexed directly, then build the interleaved order by walking i from 0 to n/2 - 1 and taking arr[i] followed by arr[n/2 + i], enqueuing each back into the queue in that order. This is easy to get right because it sidesteps the queue's FIFO restriction entirely by falling back to array indexing, but it doesn't respect the spirit of solving this as a queue problem using only queue operations. Time: O(n) Space: O(n)

Dequeue only the first n/2 elements and push them onto a stack, which reverses their order; then pop the stack back into the rear of the (now front-truncated) queue, restoring their original relative order but moved to the back - leaving the queue as [second half][first half]. Finally, rotate the queue n/2 times: each rotation dequeues the current front element and immediately enqueues it to the rear, alternating one 'take from front, send to back' step with the interleave bookkeeping so the two halves weave together as they rotate past. This uses a stack sized only to the first half rather than a second full-size queue, roughly halving the auxiliary storage compared to the two-queue approach. Time: O(n) Space: O(n/2)

Dequeue the first n/2 elements into an auxiliary queue q1, which leaves the original queue holding exactly the second half; dequeue those into a second auxiliary queue q2. Now repeatedly dequeue the front of q1 and the front of q2, enqueuing each pair back into the (now empty) original queue in that order, until both auxiliary queues are empty. This solves the problem using only proper enqueue/dequeue operations rather than array indexing, respecting the queue abstraction, though it still needs auxiliary storage proportional to the whole queue. Time: O(n) Space: O(n)

1. Split the queue into two separate queues of equal size: the first half and the second half. 2. Repeatedly dequeue one element from the first half's queue and enqueue it into the result. 3. Then dequeue one element from the second half's queue and enqueue it into the result too. 4. Keep alternating between the two halves until both are empty.

Time: O(n) - every element is moved a small constant number of times (into its half's queue, then into the final result). Space: O(n), for the two half-sized queues used during the interleaving process.

the minimum n = 2 (one element from each half); n = 10^5 for performance; repeated values across the two halves.

This is a good example of a problem where correctly identifying the natural DECOMPOSITION (split into two, then merge in an alternating pattern) makes the implementation almost trivial - spend your thinking time on the decomposition, not on complex index math.