Building Queue From Stack

Question

Imagine your interviewer asks for a queue but with a twist: you can only use stacks.

It’s actually a small shift in approach that reveals how data structure thinking and algorithmic trade offs make you a stronger engineer.

Read on, this one problem has shown up in interviews, production bug fixes, and test cases for people who later got promoted for thinking clearly under constraint.

Building a Queue using Two Stacks is a classic DSA puzzle that’s deceptively practical. It’s not just about solving the puzzle, it’s about demonstrating these career making skills:

1 : converting constraints into elegant designs,
2 : reasoning about amortized complexity (not just worst case noise),
3 : writing predictable, maintainable code that can be explained in an interview or to your teammates.

Stacks are LIFO, queues are FIFO, that’s the core mismatch. But by pairing two stacks and moving elements between them on demand, we get the FIFO behavior for free, while keeping operations simple.

How to approach ? : do most of the work lazily (only when needed). This gives amortized O(1) time for both enqueue and dequeue, which is often good enough in interviews and many real world scenarios.

class QueueUsingStacks:
    """
    Queue implemented with two stacks (lists).
    - push_stack: where we push new elements (enqueue)
    - pop_stack: where we pop elements for dequeue/peek
    Amortized costs: enqueue O(1), dequeue amortized O(1).
    """
    def __init__(self):
        self.push_stack = []
        self.pop_stack = []

    def _transfer_if_needed(self):
        """Move everything from push_stack to pop_stack if pop_stack is empty.
        This reverses order so front of queue is at the end of pop_stack.
        Each element moves at most once => amortized O(1) per op.
        """
        if not self.pop_stack:
            while self.push_stack:
                self.pop_stack.append(self.push_stack.pop())

    def enqueue(self, x):
        """Add x to the end of the queue. O(1)."""
        self.push_stack.append(x)

    def dequeue(self):
        """Remove and return the front element. Raises IndexError if empty."""
        self._transfer_if_needed()
        if not self.pop_stack:
            raise IndexError("dequeue from empty queue")
        return self.pop_stack.pop()

    def peek(self):
        """Return front element without removing it. Raises IndexError if empty."""
        self._transfer_if_needed()
        if not self.pop_stack:
            raise IndexError("peek from empty queue")
        return self.pop_stack[-1]

    def is_empty(self):
        """True if queue has no elements."""
        return not (self.push_stack or self.pop_stack)

    def __len__(self):
        """Total number of elements in the queue."""
        return len(self.push_stack) + len(self.pop_stack)


# ---- clear demo with labeled prints ----
if __name__ == "__main__":
    q = QueueUsingStacks()
    q.enqueue(10)
    q.enqueue(20)
    q.enqueue(30)

    print("dequeue ->", q.dequeue())   # -> 10
    q.enqueue(40)

    print("peek    ->", q.peek())      # -> 20
    print("len     ->", len(q))        # -> 3

    print("draining queue:")
    while not q.is_empty():
        print(q.dequeue())

If you found this helpful, like or share so your network can pick up a neat DSA approach. Read more on DSA with me here.

Comments

Nice approach.
It would be a good idea to define a Stack class and use the two instances of the Stack class instead of using the list objects for push_stack and pop_stack
So a minimal Stack class may be defined as follows:

class Stack(object):
    def __init__(this):
        this._elements_ = []
    def push(this,element):
        this._elements_.append(element)
        return True
    def pop(this):
        return this._elements_.pop()
    def peek(this):
        return this._elements_[len(_elements_)-1]
    def __len__(this):
        return len(this._elements_)
    def is_empty(this):
        return this.size() == 0

---

Yeah, this approach is good too if you want more custom control.

---

My only point was not to use list and to use Stack in the spirit of the problem statement.