Implement Queue with two stacks
Filed under Expedia
Free read 2 of 3Confirm amortized time complexity expectations for the queue operations.
The question
Implement a first-in, first-out (FIFO) queue using only two stacks. The implemented queue should support all standard queue operations: push, peek/pop, and empty.
Constraints
- At most 100 calls will be made to push, pop, peek, and empty.
- All the calls to pop and peek are valid.
Examples
- Input
- ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]
- Output
- [null, null, null, 1, 1, false]
- Why
- Queue instantiates, pushes 1 then 2. Peek returns 1. Pop removes and returns 1. Empty checks if queue is empty.
Approach
Confirm amortized time complexity expectations for the queue operations.
On every push, empty stack 1 into stack 2, push the new item onto stack 1, then empty stack 2 back into stack 1. This makes push O(N).
Maintain an input stack and an output stack. Push elements onto the input stack. When pop or peek is called, if the output stack is empty, pop all elements from the input stack and push them onto the output stack, reversing their order.
Calling pop or peek on an empty queue (though constrained as valid), and handling sequences of multiple pushes followed by multiple pops.
Solution
O(1) amortized time per operation, O(N) space
class MyQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []
def push(self, x: int) -> None:
self.in_stack.append(x)
def pop(self) -> int:
self.peek()
return self.out_stack.pop()
def peek(self) -> int:
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
return self.out_stack[-1]
def empty(self) -> bool:
return not self.in_stack and not self.out_stack
Tips
- What they are testing: Test alternating push and pop operations to ensure amortized O(1) performance works correctly.
- Common mistake: Unnecessarily transferring elements back and forth between stacks on every single push or pop operation.
Related Expedia questions
Collected from public candidate posts and coding forums. Updated Nov 2026.