Implement a queue of max length N using two stacks
Filed under Arcesium
Free read 3 of 3Confirm if the capacity N is strictly enforced and how to handle overflow/underflow errors.
The question
Implement a Queue data structure with a fixed maximum capacity N using only two stacks. The queue must support enqueue and dequeue operations, respecting the FIFO order.
Constraints
- Capacity N is fixed at initialization.
- Must use exactly two stacks for storage.
- Enqueue must fail if queue is full.
- Dequeue must fail if queue is empty.
Examples
- Input
- N=2, enqueue(1), enqueue(2), dequeue()
- Output
- 1
- Why
- Stack 1 stores elements; Stack 2 is used to reverse order during dequeue.
Approach
Confirm if the capacity N is strictly enforced and how to handle overflow/underflow errors.
Use 'inStack' for incoming elements and 'outStack' for outgoing. When dequeueing, if 'outStack' is empty, pop all from 'inStack' to 'outStack'.
Handle empty queue dequeue and full queue enqueue scenarios explicitly.
Solution
O(1) amortized time, O(N) space
class Queue:
def __init__(self, n): self.n, self.s1, self.s2 = n, [], []
def enqueue(self, x):
if len(self.s1) + len(self.s2) < self.n: self.s1.append(x)
def dequeue(self):
if not self.s2:
while self.s1: self.s2.append(self.s1.pop())
return self.s2.pop() if self.s2 else None
Tips
- What they are testing: Tests focus on boundary conditions: enqueueing to a full queue and dequeueing from an empty one.
- Common mistake: Failing to handle the transfer of elements between stacks efficiently, leading to O(N) dequeue operations instead of amortized O(1).
Related Arcesium questions
Collected from public candidate posts and coding forums. Updated Nov 2026.