← Arcesium questions

Implement a queue of max length N using two stacks

Filed under Arcesium

Free read 3 of 3

Confirm 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

  1. Confirm if the capacity N is strictly enforced and how to handle overflow/underflow errors.

Solution

O(1) amortized time, O(N) space

Python
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.