How do you implement a Queue using two Stacks?

Difficulty: 4/10

Stacks and Queues, Amortized Analysis, Concurrency

Queue Using Two Stacks

A Queue can be implemented using two Stacks by using one stack for incoming elements and another for outgoing elements. When Dequeue is requested and the output stack is empty, elements are transferred from the input stack to reverse their order, producing FIFO behavior.

javascript

1
Enqueue is O(1).
2
A single Dequeue can be O(n) when transfer is required.
3
Dequeue is amortized O(1) because each element moves from input to output at most once.
4
Auxiliary space is O(n).
5
This is a classic example of amortized analysis.

Scenario Questions

0-2 years experience

Follow-up Questions