Stacks & QueuesProblem 28 of 38
Reverse the first K elements of a queue
Problem Statement
Given a queue and an integer k, reverse the order of the first k elements of the queue, leaving the remaining elements in their original order.
Example:
Input: Queue = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 5
Output: Queue = [5, 4, 3, 2, 1, 6, 7, 8, 9, 10]
Explanation: First 5 elements [1, 2, 3, 4, 5] are reversed to [5, 4, 3, 2, 1]
Remaining elements [6, 7, 8, 9, 10] stay in place
Approach 1: Using Stack
Intuition
Use a stack to reverse the first k elements. Dequeue k elements and push them onto a stack. Pop from stack and enqueue back. Then rotate the remaining elements to their correct positions.
Algorithm
- Dequeue first k elements and push to stack
- Pop all elements from stack and enqueue to queue
- Dequeue (n-k) elements from front and enqueue to back
- This puts the reversed k elements at front, others at back
java
import java.util.*;
public class ReverseFirstK {
public static void reverseFirstK(Queue<Integer> q, int k) {
if (k <= 0 || k > q.size()) return;
Stack<Integer> stk = new Stack<>();
int n = q.size();
// Step 1: Push first k elements to stack
for (int i = 0; i < k; i++) {
stk.push(q.poll());
}
// Step 2: Pop from stack and enqueue (reversed k elements)
while (!stk.isEmpty()) {
q.offer(stk.pop());
}
// Step 3: Move remaining (n-k) elements to back
for (int i = 0; i < n - k; i++) {
q.offer(q.poll());
}
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= 10; i++) q.offer(i);
System.out.println("Original queue: " + q);
reverseFirstK(q, 5);
System.out.println("After reversing first 5 elements: " + q);
}
}Complexity Analysis
- Time Complexity: O(n) - processing all n elements
- Space Complexity: O(k) - stack holds k elements
Approach 2: Using Recursion
Intuition
Use recursion to reverse the first k elements. The recursion acts as an implicit stack. After reversing k elements, rotate the remaining elements to their correct positions.
Algorithm
- Use recursion to reverse first k elements (like reverse queue problem)
- After recursion, rotate (n-k) elements to the back
java
import java.util.*;
public class ReverseFirstK {
private static void reverseFirstKRecursive(Queue<Integer> q, int k) {
// Base case
if (k == 0) return;
// Dequeue front element
int front = q.poll();
// Recursively reverse remaining k-1 elements
reverseFirstKRecursive(q, k - 1);
// Enqueue the front element at back
q.offer(front);
}
public static void reverseFirstK(Queue<Integer> q, int k) {
if (k <= 0 || k > q.size()) return;
int n = q.size();
// Reverse first k elements using recursion
reverseFirstKRecursive(q, k);
// Rotate (n-k) elements to back
for (int i = 0; i < n - k; i++) {
q.offer(q.poll());
}
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= 10; i++) q.offer(i);
System.out.println("Original queue: " + q);
reverseFirstK(q, 5);
System.out.println("After reversing first 5 elements: " + q);
}
}Complexity Analysis
- Time Complexity: O(n) - k elements reversed + (n-k) elements rotated
- Space Complexity: O(k) - recursion stack depth
Approach 3: Optimized with Deque
Intuition
If using a deque (double-ended queue), we can reverse k elements more directly by manipulating both ends. However, standard queue only allows operations at front (dequeue) and back (enqueue).
Algorithm
- Extract first k elements into an array
- Reverse the array
- Create new queue with reversed elements followed by remaining elements
java
import java.util.*;
public class ReverseFirstK {
public static void reverseFirstKOptimized(Queue<Integer> q, int k) {
if (k <= 0 || k > q.size()) return;
List<Integer> firstK = new ArrayList<>();
// Extract first k elements
for (int i = 0; i < k; i++) {
firstK.add(q.poll());
}
// Reverse the extracted elements
Collections.reverse(firstK);
// Create result queue
Queue<Integer> result = new LinkedList<>();
// Add reversed elements
for (int x : firstK) {
result.offer(x);
}
// Add remaining elements
while (!q.isEmpty()) {
result.offer(q.poll());
}
// Copy back to original queue
while (!result.isEmpty()) {
q.offer(result.poll());
}
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= 10; i++) q.offer(i);
System.out.println("Original queue: " + q);
reverseFirstKOptimized(q, 5);
System.out.println("After reversing first 5 elements: " + q);
}
}Complexity Analysis
- Time Complexity: O(n) - processing all elements
- Space Complexity: O(n) - temporary storage for queue
Key Takeaways
- Two-Phase Approach: First reverse k elements, then reposition remaining elements
- Stack for Reversal: Stack naturally reverses the order of elements
- Rotation Step: Essential to move non-reversed elements to correct position
- Edge Cases: Handle k=0, k=n, k>n appropriately
- Queue Constraints: Only front dequeue and back enqueue allowed
- This problem combines reversal and rotation concepts