Reversing a Queue in Java: A Simple and Efficient Approach Using Stacks

 

In this blog post, we’ll explore a simple yet effective way to reverse a queue using a stack in Java. This technique leverages the Last-In-First-Out (LIFO) nature of stacks to reverse the First-In-First-Out (FIFO) order of queues.

The Problem

Given a queue of integers, we want to reverse the order of its elements. For example, if the queue initially contains [1, 2, 3, 4, 5], after reversal, it should contain [5, 4, 3, 2, 1].

The Solution

To achieve this, we can use a stack. The idea is to dequeue all elements from the queue and push them onto the stack. Since a stack reverses the order of elements, we can then pop all elements from the stack back into the queue, effectively reversing the queue.

 Code

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

public class QueueReversal {
    public static void reversalQueue(Queue<Integer> q) {
        Stack<Integer> s = new Stack<>();

        // Transfer elements from the queue to the stack
        while (!q.isEmpty()) {
            s.push(q.remove());
        }

        // Transfer elements back from the stack to the queue
        while (!s.isEmpty()) {
            q.add(s.pop());
        }
    }

    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();

        // Add elements to the queue
        q.add(1);
        q.add(2);
        q.add(3);
        q.add(4);
        q.add(5);

        // Reverse the queue
        reversalQueue(q);

        // Print the reversed queue
        while (!q.isEmpty()) {
            System.out.print(q.remove() + " ");
        }
    }
}

Explanation

1. Import Statements: We import the necessary classes from the Java standard library.
2. reversalQueue Method: This method takes a queue as input and reverses its elements using a stack.
   • Step 1: Dequeue all elements from the queue and push them onto the stack.
   • Step 2: Pop all elements from the stack and enqueue them back into the queue.
3. main Method: This method demonstrates the usage of the reversalQueue method.
• Step 1: Create a queue and add some elements to it.
• Step 2: Call the reversalQueue method to reverse the queue.
• Step 3: Print the reversed queue.

Time Complexity

The time complexity of the reversalQueue method is O(N), where N is the number of elements in the queue. This is because:

1. The first while loop iterates through all N elements to push them onto the stack.
2. The second while loop iterates through all N elements to pop them from the stack and add them back to the queue.

Space Complexity

The space complexity of the reversalQueue method is also O(N). This is due to the additional space required to store the elements in the stack. The stack will hold all N elements of the queue at one point in time.

In summary:

• Time Complexity: O(N)
• Space Complexity: O(N)

Conclusion

Reversing a queue using a stack is a straightforward approach that leverages the inherent properties of these data structures. This method is efficient and easy to implement, making it a great example of how different data structures can be used together to solve problems.

Feel free to try out the code and see how it works. Happy coding! 😊

---

If you have any questions or need further clarification, don’t hesitate to ask!