Queue Implementation in Java Using Two Stacks

In this article, we'll dive deep into how to build a queue using two stacks in Java. 

Concept Behind the Implementation 

To build a queue using two stacks (let's call them stack1 and stack2), we can use one stack (stack1) for the enqueue operation and the other (stack2) for the dequeue operation. 

When dequeuing, if stack2 is empty, we'll pop all the elements from stack1 and push them onto stack2. 

Java Implementation

Let's dive into the code:

import java.util.Stack;

public class QueueUsingStacks<T> {
    private Stack<T> stack1;
    private Stack<T> stack2;

    public QueueUsingStacks() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void enqueue(T data) {
        stack1.push(data);
    }

    public T dequeue() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        if (stack2.isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return stack2.pop();
    }
}

Testing the Queue Implementation:

public class Main {
    public static void main(String[] args) {
        QueueUsingStacks<Integer> queue = new QueueUsingStacks<>();

        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);

        System.out.println(queue.dequeue() + " dequeued from queue");

        queue.enqueue(40);
        queue.enqueue(50);

        System.out.println(queue.dequeue() + " dequeued from queue");
    }
}

Output:

10 dequeued from queue
20 dequeued from queue

Performance Implications 

While this method may seem neat and clever, it's essential to be wary of its time complexities. Enqueue operations are O(1). However, dequeue operations are O(n) in the worst-case scenario since all elements might need to be transferred from stack1 to stack2. 

Conclusion

Implementing a queue using two stacks in Java showcases the versatility of data structures and the power of algorithmic thinking. While it might not be the most efficient method for handling large datasets, it serves as an excellent exercise in understanding the underlying principles of these data structures. It underscores the fact that computer science isn't just about finding a solution; it's about exploring all possible paths to reach that solution.