easy Reverse a Queue

Problem Statement

Given a queue containing integer elements, return the updated queue after reversing its elements.

Examples

Example 1

• Input: queue = [1, 2, 3, 4, 5]
• Expected Output: [5, 4, 3, 2, 1]
• Explanation: The input queue elements are reversed.

Example 2

• Input: queue = [10, 20, 30, 40, 50]
• Expected Output: [50, 40, 30, 20, 10]
• Explanation: The input queue elements are reversed.

Example 3

• Input: queue = [5, 7, 12, 2, 4, 5]
• Expected Output: [5, 4, 2, 12, 7, 5]
• Explanation: The input queue elements are reversed.

Solution

The given Java program reverses the order of elements in a queue using a stack. The idea is to first transfer all the elements from the queue to a stack, which inherently reverses their order due to the Last-In-First-Out (LIFO) nature of a stack. Once all the elements are in the stack, they are popped back into the queue, thus reversing their original order. This approach efficiently leverages the stack's properties to achieve the desired outcome, ensuring that the elements in the queue are reversed.

Step-by-Step Algorithm

1. Initialize Stack:

   • Create an empty Stack<Integer> named stack.

2. Transfer Elements to Stack:

   • While the queue is not empty:
     • Remove the front element from the queue using remove().
     • Push this element onto the stack using stack.add().

3. Transfer Elements Back to Queue:

   • While the stack is not empty:
     • Pop the top element from the stack using stack.pop().
     • Add this element back to the queue using queue.add().

4. Return the Queue:

   • The queue now contains the elements in reversed order. Return the modified queue.

Algorithm Walkthrough

Code

Here is how we can implement this algorithm:

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

public class Solution {

  // Declare a static Queue of Integer type.
  static Queue<Integer> queue;

  // Define a static method to reverse the order of elements in the queue.
  Queue<Integer> reverseQueue(Queue<Integer> q) {
    // Create a Stack to temporarily hold the elements from the queue.
    Stack<Integer> stack = new Stack<>();

    // Transfer elements from the queue to the stack.
    // This will reverse the order of elements because stacks follow LIFO order.
    while (!q.isEmpty()) {
      // Add the front element of the queue to the stack.
      stack.add(q.peek());
      // Remove the front element from the queue.
      q.remove();
    }

    // Transfer elements back from the stack to the queue.
    // The order of elements will now be reversed in the queue.
    while (!stack.isEmpty()) {
      // Add the top element of the stack to the queue.
      q.add(stack.peek());
      // Remove the top element from the stack.
      stack.pop();
    }
    return q;
  }

  // Define the main method to test the reverseQueue method.
  public static void main(String[] args) {
    // Initialize the queue and add some elements to it.
    queue = new LinkedList<Integer>();
    queue.add(1);
    queue.add(2);
    queue.add(3);
    queue.add(4);
    queue.add(5);

    // Call the method to reverse the order of elements in the queue.
    Solution sol = new Solution();
    sol.reverseQueue(queue);

    // Print the reversed queue to the console.
    System.out.println(queue);
  }
}

Complexity Analysis

Time Complexity

• Transferring elements from the queue to the stack: The first while loop iterates over all elements in the queue and pushes them onto the stack. This takes time, where N is the number of elements in the queue.

• Transferring elements back from the stack to the queue: The second while loop pops elements from the stack and adds them back to the queue. This also takes time.

• Therefore, the overall time complexity is .

Overall time complexity: .

Space Complexity

• Stack space: The stack is used to store the elements from the queue. Since the stack holds all N elements from the queue, the space required is .

• Queue space: The queue already holds N elements, but since we are using the same queue for input and output, this does not count as additional space.

Overall space complexity: .