Fundamentals · Hard · Free
Implement a queue using two stacks — explain amortized cost.
FresherFundamentalsData Structures & Algorithms
Queue from two stacks
Enqueue to stack in; dequeue pop from stack out—if empty, pour in into out reversing order. Amortized O(1) per op.
java
Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
void enqueue(int x) { in.push(x); }
int dequeue() {
if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
return out.pop();
}Explain amortized: each element moved once between stacks.