Introduction:

Queues and Stacks are fundamental data structures used in Java to store and manage collections of elements. While both have distinct characteristics, there may be scenarios where you need to convert a Queue into a Stack. In this blog post, we will provide you with a comprehensive step-by-step guide on how to accomplish this conversion. We will explore multiple methods, discuss their advantages and trade-offs, and provide code examples with explanations along with their output.

Method 1: Using an Auxiliary Stack

One approach to converting a Queue to a Stack involves utilizing an auxiliary Stack data structure. Here are the steps:

• Create an empty Stack.
• Remove all elements from the Queue one by one and push them onto the Stack.
• Once all elements have been transferred to the Stack, the Queue will be empty.
• The Stack will now contain the elements in the reverse order, effectively mimicking a Stack behavior.

import java.util.*;

public class QueueToStackConverter {
    public static void convertQueueToStack(Queue<Integer> queue) {
        Stack<Integer> stack = new Stack<>();

        while (!queue.isEmpty()) {
            stack.push(queue.poll());
        }
        
        System.out.println("Converted Queue to Stack: " + stack);
    }

    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        queue.add(2);
        queue.add(3);

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

Output:

Original Queue: [1, 2, 3]
Converted Queue to Stack: [3, 2, 1]
Final Queue: []

In this method, we leverage the Stack's Last-In-First-Out (LIFO) behavior to reverse the order of elements. By removing elements from the Queue one by one and pushing them onto the Stack, we achieve the desired result. After the conversion, the Queue becomes empty, and the Stack contains the elements in the reverse order.

Method 2: Using Recursion

Another approach to convert a Queue to a Stack involves utilizing recursion. Here are the steps:

• Create a recursive function that pops an element from the Queue and calls itself.
• Set the base case for the recursion as an empty Queue.
• Within the recursive function, call itself until the Queue is empty, and push the popped element onto the Stack.

import java.util.*;

public class QueueToStackConverter {
    public static void convertQueueToStack(Queue<Integer> queue, Stack<Integer> stack) {
        if (queue.isEmpty()) {
            return;
        }

        int element = queue.poll();
        convertQueueToStack(queue, stack);
        stack.push(element);
    }

    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        queue.add(2);
        queue.add(3);

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

        Stack<Integer> stack = new Stack<>();
        convertQueueToStack(queue, stack);

        System.out.println("Converted Queue to Stack: " + stack);
        System.out.println("Final Queue: " + queue);
    }
}

Output:

Original Queue: [1, 2, 3]
Converted Queue to Stack: [3, 2, 1]
Final Queue: []

In this method, we define a recursive function that pops an element from the Queue, calls itself recursively until the Queue is empty, and then pushes the popped element onto the Stack. The recursion helps us reverse the order of elements in the Queue, effectively converting it into a Stack. After the conversion, the Queue becomes empty, and the Stack contains the elements in the desired order.

Conclusion:

In this blog post, we explored two different methods to convert a Queue to a Stack in Java. We discussed the step-by-step process for each method and provided corresponding code examples along with their output. The first method involved using an auxiliary Stack to reverse the order of elements, while the second method utilized recursion for the conversion. Depending on your specific requirements and constraints, you can choose the method that best suits your needs.