Queue using two Stacks

Summary

Given a queue data structure, design and implement an algorithm to simulate its functionality using two stacks. This problem involves implementing the basic operations of enqueue and dequeue using stack-based approach.

Detailed Explanation

The idea is to use two stacks, one for enqueue operation and another for dequeue operation. The first stack (enqueue stack) is used to store elements as they are added to the queue. When an element needs to be dequeued, it is moved from the enqueue stack to the dequeue stack. If the dequeue stack is empty, all elements from the enqueue stack are moved to the dequeue stack.

Here's a step-by-step breakdown of the solution:

Initialize two stacks: enqueueStack and dequeueStack.
To enqueue an element:
- Push the element onto enqueueStack.
To dequeue an element:
- If dequeueStack is empty, pop all elements from enqueueStack and push them onto dequeueStack. This ensures that the order of elements remains the same.
- Pop the top element from dequeueStack, which represents the dequeued element.

Time complexity: O(1) for enqueue and O(n) for dequeue operations (where n is the number of elements in the queue). Space complexity: O(n), where n is the maximum size of the queue.

Optimized Solutions

Java

class QueueUsingTwoStacks { Stack<Integer> enqueueStack; Stack<Integer> dequeueStack; public QueueUsingTwoStacks() { enqueueStack = new Stack<>(); dequeueStack = new Stack<>(); } public void enqueue(int element) { enqueueStack.push(element); } public int dequeue() { if (dequeueStack.isEmpty()) { while (!enqueueStack.isEmpty()) { dequeueStack.push(enqueueStack.pop()); } } return dequeueStack.pop(); } }