Java Queues – Reverse a Queue

A queue is a data structure that follows the FIFO (First In, First Out) principle. This means the first element added to the queue is the first one to be removed.

However, what if we need to reverse the queue? That means we want to transform a queue like this:

📥 Before Reversal (FIFO Order):
[1, 2, 3, 4, 5]

📤 After Reversal (LIFO Order):
[5, 4, 3, 2, 1]

Approach: How to Reverse a Queue

To reverse a queue, we can use a stack. A stack follows LIFO (Last In, First Out), which means the last element inserted is the first one to be removed.

🔹 Steps to Reverse a Queue:

1. Dequeue (remove) all elements from the queue one by one and push them onto a stack.
2. Pop all elements from the stack and enqueue them back into the queue.
3. Now the queue is reversed! 🎉

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class ReverseQueue {

    // Method to reverse the queue
    public static void reverseQueue(Queue<Integer> queue) {
        Stack<Integer> stack = new Stack<>();

        // Step 1: Move all elements from queue to stack
        while (!queue.isEmpty()) {
            stack.push(queue.poll());  // Remove from queue, push to stack
        }

        // Step 2: Move all elements back from stack to queue
        while (!stack.isEmpty()) {
            queue.add(stack.pop());  // Remove from stack, add to queue
        }
    }

    // Main method to test our queue reversal
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // Adding elements to queue
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(5);

        System.out.println("Original Queue: " + queue);

        // Call the reverseQueue method
        reverseQueue(queue);

        System.out.println("Reversed Queue: " + queue);
    }
}

🛠️ Complexity Analysis

• Time Complexity: O(n), where n is the number of elements in the queue.
• Space Complexity: O(n), because we use a stack to store elements.

📌 Next Steps

Now that you understand queue reversal, try solving these variations:

1. Reverse the first K elements of a queue.
2. Reverse a queue using recursion instead of a stack.
3. Implement a queue reversal without extra space.

🚀 Happy Coding! If you found this useful, don’t forget to practice more queue-based problems!