easyStack / QueuePure DSA~16 min
Queue From Two Stacks
A worker only exposes a stack primitive, but the job dispatcher needs FIFO ordering. Implement a queue using two stacks so enqueue and dequeue stay amortised O(1).
Problem
Implement a FIFO queue using only two stacks. Support push(x), pop() (remove and return the front), peek() (return the front), and empty(). Each operation must use only standard stack operations (push, pop, peek/top, size/empty).
Input
A sequence of push/pop/peek/empty operations; pushed values are integers.
Output
Each pop/peek returns the front element; empty returns a boolean.
Constraints
- Only stack operations may be used internally
- pop and peek are called on a non-empty queue
- Amortised O(1) per operation
Examples
Example 1
Input
push(1), push(2), peek(), pop(), empty()
Output
peek→1, pop→1, empty→false
FIFO: 1 enqueued first leaves first; 2 still remains.
Example 2
Input
push(5), pop(), empty()
Output
pop→5, empty→true
The single element dequeues, leaving the queue empty.