168. Reverse the First K Elements of a Queue

Given a queue of n integers (front to back) and a number k, reverse the order of just the first k elements, leaving the rest of the queue unchanged. Print the resulting queue, front to back.

Input: The first line contains an integer n. The second line contains n space-separated integers, the queue's values front to back. The third line contains k, how many front elements to reverse. Output: Print the resulting queue's values, space-separated, front to back.

1 <= k <= n <= 10^5

Only the first k elements' RELATIVE order changes - the remaining n-k elements' relative order among themselves is completely untouched, which is exactly why you don't need to touch them at all during the process.

Flip the order of just the FRONT portion of a queue, leaving everything behind it exactly as it was. Brute force: Dequeue all n elements into a regular array, manually reverse just the first k entries of that array, then rebuild the queue from the modified array - this works, but uses an extra full-size array rather than reusing the queue's own structure directly. Optimised: A stack is the perfect tool for reversing exactly k elements, since pushing then popping automatically reverses order - using a stack sized to exactly k elements (rather than a full n-sized array) makes the extra memory used proportional only to k, not the whole queue.

Push the first k elements onto a stack (which reverses their order), then pop them into a new auxiliary queue so they're now in reversed order at its front. Continue by dequeuing each of the remaining n-k elements from the original queue and appending them to that same auxiliary queue. The auxiliary queue now holds the fully correct answer and can be copied back. This uses only genuine stack/queue operations rather than array indexing, but the auxiliary queue still ends up holding all n elements. Time: O(n) Space: O(n)

Push only the first k elements onto a stack (O(k) extra space), then pop them straight back onto the rear of the very same queue - this leaves the queue as [remaining n-k original elements][reversed first k]. Finally, rotate the queue n-k times: each rotation dequeues the current front (one of the untouched elements, now sitting ahead of the reversed block) and immediately enqueues it to the rear, which walks the untouched elements back to the front of the line while preserving their order and leaving the reversed first k at the very front once the rotation completes. This needs a stack sized only to k rather than an auxiliary structure holding the whole queue. Time: O(n) Space: O(k)

Dequeue every element of the queue into an array so the first k elements can be indexed directly, reverse just that first k-length slice of the array in place, and then enqueue the whole array (reversed prefix followed by unchanged remainder) back into the queue. This produces the correct result and is simple to reason about, but it needs an array holding the entire queue's contents even though only the first k elements actually need reordering. Time: O(n) Space: O(n)

1. Dequeue the first k elements one at a time, pushing each one onto a stack as you go - this naturally reverses their order. 2. Pop everything off the stack and enqueue it back into the queue - since a stack is LIFO, this places them back in REVERSED order relative to how they started. 3. The remaining (n - k) elements were never touched, so they're still in their original relative order, right behind the now-reversed first k.

Time: O(n) - dequeuing the first k elements, reversing them via the stack, and re-enqueuing takes time proportional to k, and the untouched remainder still needs to conceptually 'stay' in the queue, so overall the whole operation is linear in the total size. Space: O(k), for the temporary stack holding just the first k elements - not the whole queue.

k = 1 (no visible change to a single reversed element); k = n (the entire queue gets reversed); n = 10^5 for performance.

Recognizing 'I need to reverse SOME elements' as an immediate signal to reach for a stack (LIFO naturally reverses order) is a fast, reusable pattern-matching skill worth having ready.