Stacks & QueuesProblem 27 of 38
Reverse a Queue using recursion
Problem Statement
Given a queue, write a recursive function to reverse it. You can only use standard queue operations: enqueue (push to back), dequeue (pop from front), front (peek front), and isEmpty.
Example:
Input: Queue = [1, 2, 3, 4, 5]
(front) (rear)
Output: Queue = [5, 4, 3, 2, 1]
(front) (rear)
Approach 1: Using Stack (Iterative)
Intuition
Use a stack as an auxiliary data structure. Dequeue all elements from the queue and push them onto the stack. Then pop all elements from the stack and enqueue them back to the queue.
Algorithm
- Dequeue all elements and push to stack
- Pop all elements from stack and enqueue to queue
- The queue is now reversed
java
import java.util.*;
public class ReverseQueue {
public static void reverseQueueIterative(Queue<Integer> q) {
Stack<Integer> stk = new Stack<>();
// Dequeue all and push to stack
while (!q.isEmpty()) {
stk.push(q.poll());
}
// Pop all from stack and enqueue
while (!stk.isEmpty()) {
q.offer(stk.pop());
}
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.offer(1);
q.offer(2);
q.offer(3);
q.offer(4);
q.offer(5);
System.out.println("Original queue: " + q);
reverseQueueIterative(q);
System.out.println("Reversed queue: " + q);
}
}Complexity Analysis
- Time Complexity: O(n) - each element is processed twice
- Space Complexity: O(n) - stack holds all n elements
Approach 2: Optimal (Using Recursion)
Intuition
Use recursion to implicitly use the call stack instead of an explicit stack. Dequeue the front element, recursively reverse the remaining queue, then enqueue the dequeued element. The recursion naturally reverses the order.
Algorithm
- Base case: If queue is empty, return
- Dequeue the front element
- Recursively reverse the remaining queue
- Enqueue the dequeued element at the back
java
import java.util.*;
public class ReverseQueue {
public static void reverseQueue(Queue<Integer> q) {
// Base case
if (q.isEmpty()) {
return;
}
// Dequeue front element
int front = q.poll();
// Recursively reverse remaining queue
reverseQueue(q);
// Enqueue the front element at back
q.offer(front);
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.offer(1);
q.offer(2);
q.offer(3);
q.offer(4);
q.offer(5);
System.out.println("Original queue: " + q);
reverseQueue(q);
System.out.println("Reversed queue: " + q);
}
}Complexity Analysis
- Time Complexity: O(n) - each element is processed once
- Space Complexity: O(n) - recursion stack holds n frames
Approach 3: Understanding the Recursion
Visual Walkthrough
Initial Queue: [1, 2, 3, 4, 5]
Call Stack (going down):
reverseQueue([1, 2, 3, 4, 5])
front = 1, queue = [2, 3, 4, 5]
reverseQueue([2, 3, 4, 5])
front = 2, queue = [3, 4, 5]
reverseQueue([3, 4, 5])
front = 3, queue = [4, 5]
reverseQueue([4, 5])
front = 4, queue = [5]
reverseQueue([5])
front = 5, queue = []
reverseQueue([]) // Base case, return
queue.push(5) -> queue = [5]
queue.push(4) -> queue = [5, 4]
queue.push(3) -> queue = [5, 4, 3]
queue.push(2) -> queue = [5, 4, 3, 2]
queue.push(1) -> queue = [5, 4, 3, 2, 1]
Final Queue: [5, 4, 3, 2, 1]
java
import java.util.*;
public class ReverseQueueVisualized {
private static int depth = 0;
private static String indent() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < depth; i++) sb.append(" ");
return sb.toString();
}
public static void reverseQueueVisualized(Queue<Integer> q) {
if (q.isEmpty()) {
System.out.println(indent() + "Base case: queue is empty, returning");
return;
}
int front = q.poll();
System.out.println(indent() + "Dequeued: " + front + ", Remaining size: " + q.size());
depth++;
reverseQueueVisualized(q);
depth--;
q.offer(front);
System.out.println(indent() + "Enqueued: " + front + ", Queue size: " + q.size());
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= 5; i++) q.offer(i);
System.out.println("Reversing queue [1, 2, 3, 4, 5]:");
System.out.println("================================");
reverseQueueVisualized(q);
System.out.println("================================");
System.out.println("Final queue: " + q);
}
}Complexity Analysis
- Time Complexity: O(n) - each element dequeued and enqueued once
- Space Complexity: O(n) - recursion stack depth equals n
Key Takeaways
- Recursion as Stack: The call stack implicitly acts as a stack for reversal
- Order of Operations: Dequeue before recursion, enqueue after recursion
- Base Case: Empty queue signals end of recursion
- Stack vs Recursion: Both achieve the same result with same complexity
- In-place Operation: The queue is modified in place, no new queue created
- This concept applies to reversing any sequential data structure using recursion