Implement a Queue Using Stacks

mosesg1123
May 5
4 min read

Building a queue out of stacks is a classic exercise in adapting one data structure to mimic another. It’s not only a great warm‑up for understanding LIFO vs FIFO, but also shows up in real systems when you need to layer or adapt APIs.

Problem Statement

Design a first‑in, first‑out (FIFO) queue using only two stacks. Implement the following operations:

push(x): Add element x to the back of the queue.
pop(): Remove and return the element from the front of the queue.
peek(): Return the element at the front without removing it.
empty(): Return true if the queue is empty, false otherwise.

All operations should run in amortized O(1) time.

1. Clarify Requirements Before Jumping Into Code

Can I use any other data structures? Only two stacks (and primitive variables).
Do I need to handle underflow? Popping or peeking from an empty queue can raise an error or return a sentinel—I'll assume operations won’t be called on an empty queue.
Amortized vs. worst‑case time? Amortized O(1) is acceptable.
What’s the expected sequence of operations? Potentially many pushes before pops and vice versa.

2. Identify the Category of the Question

This is a data-structure adaptation or design problem, closely related to:

Stack operations (LIFO)
Queue semantics (FIFO)
Amortized analysis for cost spreading
Two-pointer or two-structure coordination

Recognizing “queue using stacks” points to the classic two-stack adapter pattern.

3. Consider a Brute‑Force Approach to Understand the Problem

A naive brute‑force: use one stack, and on every pop or peek, transfer all items into a temporary list/array to reverse order, access the first element, then rebuild the stack:

def pop():
    temp = []
    while stack:
        temp.append(stack.pop())
    result = temp.pop(0)
    for x in reversed(temp):
        stack.append(x)
    return result

Time Complexity: O(n) per pop/peek
Space Complexity: O(n) for the temp array
Drawback: Too slow for repeated operations

This makes FIFO correct but destroys performance.

4. Brainstorm More Solutions

I need to get amortized O(1). Options:

Two stacks with eager transfer: On each push, move all elements to a “new” stack, push the new element, then move everything back. Then pop or peek is just pop/peek on the main stack.
- Pros: pop/peek O(1).
- Cons: push O(n) every time.
Two stacks with lazy transfer (optimal):Maintain in_stack for pushes and out_stack for pops.
- push(x): push onto in_stack (O(1)).
- pop() / peek(): if out_stack empty, transfer all elements from in_stack to out_stack (reversing order), then pop/peek from out_stack. If not empty, just pop/peek.
- Pros: amortized O(1) per operation, simple to derive once you think about reversal.
- Cons: occasional O(n) transfer, but happens once per element.

To rediscover lazy transfer: I know a queue needs front‑first order. A stack reverses order. If I only reverse when needed—once per element—I can spread that cost. That leads naturally to pushing always to one stack and popping from the other, transferring only when the pop side is empty.

5. Discuss Trade‑Offs Between Your Solutions

Approach	push	pop/peek	Space	Pros	Cons
Eager two‑stack transfer	O(n)	O(1)	O(n)	pop/peek always O(1)	push always O(n)
Brute‑force single‑stack flip	O(1)	O(n)	O(n)	push is trivial	pop/peek O(n) each time
Lazy two‑stack transfer (optimal)	O(1)	amortized O(1)	O(n)	Amortized O(1) all ops	occasional O(n) transfer

The lazy two‑stack approach is the clear winner for balanced performance.

6. Write Pseudocode to Structure Your Thoughts

initialize in_stack and out_stack as empty stacks

function push(x):
  in_stack.push(x)

function pop():
  if out_stack is empty:
    while in_stack not empty:
      out_stack.push(in_stack.pop())
  return out_stack.pop()

function peek():
  if out_stack is empty:
    while in_stack not empty:
      out_stack.push(in_stack.pop())
  return out_stack.top()

function empty():
  return in_stack.empty() and out_stack.empty()

7. Consider Edge Cases

Empty queue → empty() returns true; pop() or peek() may throw an exception.
Multiple pushes before any pops → all live in in_stack; first pop triggers a full transfer.
Interleaved push/pop → if out_stack still has elements, pushes go to in_stack without affecting pops.
Single element → pushes to in_stack, then transferred to out_stack on first pop, then both stacks empty.
Large sequence → amortized cost holds across many operations.

8. Write Full Code Syntax (in Python)

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x):
        self.in_stack.append(x)

    def pop(self):
        self._move_if_needed()
        return self.out_stack.pop()

    def peek(self):
        self._move_if_needed()
        return self.out_stack[-1]

    def empty(self):
        return not self.in_stack and not self.out_stack

    def _move_if_needed(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

9. Test Your Code

q = MyQueue()
assert q.empty() == True

q.push(10)
q.push(20)
q.push(30)
assert q.empty() == False
assert q.peek() == 10

assert q.pop() == 10
assert q.peek() == 20

q.push(40)
assert q.pop() == 20
assert q.pop() == 30
assert q.pop() == 40
assert q.empty() == True

# interleaved operations
q.push(1)
assert q.pop() == 1
q.push(2)
q.push(3)
assert q.peek() == 2
assert q.pop() == 2
assert q.pop() == 3

print("All tests passed!")

10. Key Lessons to Remember for Future Questions

Adapter pattern: use two of one data structure (stacks) to simulate another (queue).
Lazy vs. eager strategies: delaying work can yield better amortized performance.
Amortized analysis: occasional expensive operations are fine if each element only triggers a shift once.
Clear helper methods (_move_if_needed) simplify code structure.
Thorough edge‑case testing—empty, single‑element, interleaved—ensures robustness.

Good luck and Happy Coding