Reverse the First k Elements of a Queue

Given a queue (a Deque<Integer> backed by ArrayDeque) and an integer k, reverse the order of the first k elements (the ones nearest the front). Leave the remaining elements in their original order. If k is larger than the queue, leave the queue unchanged.

Example 1

Input:  front [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] back, k = 5
Output: front [5, 4, 3, 2, 1, 6, 7, 8, 9, 10] back

Example 2

Input:  [1, 2, 3], k = 3
Output: [3, 2, 1]

Using only queue and stack operations

The standard interview version allows only enqueue (addLast), dequeue (pollFirst), and a helper stack (push and pop on another ArrayDeque):

1. Dequeue the first k elements and push them onto a stack. The stack reverses their order.
2. Pop the stack and enqueue each element. They go to the back, reversed.
3. The n - k elements that were not touched are now at the front. Dequeue each one and enqueue it again, so they move behind the reversed part.

Walkthrough with [1, 2, 3, 4, 5], k = 3:

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static void reverseK(Deque<Integer> queue, int k) {
        if (k > queue.size()) {
            return;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < k; i++) {
            stack.push(queue.pollFirst());
        }
        while (!stack.isEmpty()) {
            queue.addLast(stack.pop());
        }
        for (int i = 0; i < queue.size() - k; i++) {
            queue.addLast(queue.pollFirst());
        }
    }

    public static void main(String[] args) {
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= 10; i++) q.addLast(i);
        reverseK(q, 5);
        System.out.println(q);

        Deque<Integer> small = new ArrayDeque<>(java.util.List.of(1, 2, 3, 4, 5));
        reverseK(small, 3);
        System.out.println(small);
    }
}

[5, 4, 3, 2, 1, 6, 7, 8, 9, 10]
[3, 2, 1, 4, 5]

Time: O(n): k moves to the stack, k moves back, and n - k rotations. Space: O(k) for the stack.

pollFirst returns null on an empty queue, and unboxing null into an int would throw NullPointerException. It cannot happen here, because the method returns early when k > size, so the queue always has enough elements. The rotation loop uses queue.size() - k, which is re-evaluated on each check but stays constant: each iteration removes one element and adds one.

Optimal: put the first k back at the front

A Deque works at both ends. Remove the first k elements into an array, then add them back with addFirst in the order they were removed. Each addFirst places the element in front of the previous one, so the last element removed ends up first. The untouched elements never move.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

public class Main {
    static void reverseK(Deque<Integer> queue, int k) {
        if (k > queue.size()) {
            return;
        }
        int[] front = new int[k];
        for (int i = 0; i < k; i++) {
            front[i] = queue.pollFirst();
        }
        for (int i = 0; i < k; i++) {
            queue.addFirst(front[i]); // each element goes in front of the previous one
        }
    }

    public static void main(String[] args) {
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= 10; i++) q.addLast(i);
        reverseK(q, 5);
        System.out.println(q);

        Deque<Integer> shorter = new ArrayDeque<>(List.of(1, 2));
        reverseK(shorter, 5); // k too large: unchanged
        System.out.println(shorter);
    }
}

[5, 4, 3, 2, 1, 6, 7, 8, 9, 10]
[1, 2]

Time: O(k): k removals and k insertions at the ends. Space: O(k) for the temporary array.

Edge cases

• k = 0 or k = 1: nothing changes.
• k = n: the whole queue is reversed.
• k > n: unchanged, by the problem's definition.