Queue Using Stacks, Merge Arrays, and Pattern
Filed under Accolite
Free read 3 of 3Use one stack for input (pushing) and another for output (popping/peeking).
The question
Implement a First-In-First-Out (FIFO) queue using only two stacks. The implemented queue should support the standard operations: push to back, peek from front, pop from front, and empty check.
Constraints
- 1 <= x <= 100
- At most 100 calls to push, pop, peek, and empty.
- Only standard stack operations (push to top, peek/pop from top, size, is empty) are allowed.
Examples
- Input
- ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]
- Output
- [null, null, null, 1, 1, false]
- Why
- Queue: [1, 2]. Peek returns 1. Pop returns 1. Queue: [2]. Empty returns false.
Approach
Use one stack for input (pushing) and another for output (popping/peeking).
Only move elements from the input stack to the output stack when the output stack is empty.
Explain why pop/peek are amortized O(1) because each element is moved between stacks at most once.
Check behavior when popping from an empty queue or checking empty status with elements in only one stack.
Solution
O(1) amortized time, O(n) space
class MyQueue:
def __init__(self):
self.in_stk = []
self.out_stk = []
def push(self, x: int) -> None:
self.in_stk.append(x)
def pop(self) -> int:
self.peek()
return self.out_stk.pop()
def peek(self) -> int:
if not self.out_stk:
while self.in_stk:
self.out_stk.append(self.in_stk.pop())
return self.out_stk[-1]
def empty(self) -> bool:
return not self.in_stk and not self.out_stk
Tips
- What they are testing: Perform multiple pushes followed by multiple pops to ensure the stack transfer logic maintains FIFO order.
- Common mistake: Moving all elements between stacks on every single push operation, which results in O(N) push instead of amortized O(1).
Related Accolite questions
Collected from public candidate posts and coding forums. Updated Nov 2026.