L2 · Working engineerStacks & queues~10 min · 4 tests#45

Implement a Queue Using Two Stacks

Build a FIFO queue from two LIFO stacks with amortised O(1) enqueue and dequeue. Understand amortised analysis with a classic interview question.

The problem

Implement MyQueue using only two Python lists used as stacks (append / pop from the end):

enqueue(x)
dequeue() — returns the front, or None if empty

Examples

Example 1

Input

run_ops(MyQueue, [], [["enqueue", 10], ["enqueue", 20], ["enqueue", 30], ["dequeue"], ["dequeue"]])

Expected output

[None, None, None, 10, 20]

Example 2

Input

run_ops(MyQueue, [], [["enqueue", 1], ["dequeue"], ["enqueue", 2], ["enqueue", 3], ["dequeue"], ["dequeue"]])

Expected output

[None, 1, None, None, 2, 3]

+ 2 hidden tests on Submit — interleaved.

Edge cases to ask about

Dequeue from empty
Interleaved enqueue/dequeue

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · MyQueue

class MyQueue:
    def __init__(self):
        self.inbox = []
        self.outbox = []

    def enqueue(self, x):
        pass

    def dequeue(self):
        pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and read why.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
Move everything back and forth each time	O(n) per op	O(n)
bestLazy transfer (inbox → outbox only when outbox is empty)	O(1) amortised	O(n)	Each element is moved at most once.

Walkthrough of the optimal approach (try it yourself first)

New items go on inbox. To dequeue, take from outbox; if it is empty, pour all of inbox into it (which reverses the order, putting the oldest on top).

One dequeue can cost O(n), but each element is moved at most once in its lifetime, so the amortised cost per operation is O(1). Explaining amortised analysis is the real interview question here.

Complexity: O(1) amortised time, O(n) space. Each element is pushed to inbox once, moved to outbox once and popped once — three O(1) operations over its lifetime.

Reveal the reference solution

class MyQueue:
    def __init__(self):
        self.inbox = []
        self.outbox = []

    def enqueue(self, x):
        self.inbox.append(x)

    def dequeue(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop() if self.outbox else None

Follow-ups interviewers ask

Add peek().
Implement a stack with two queues (next question).

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Implement a Queue Using Two Stacks in Python?

The optimal solution runs in O(1) amortised time and O(n) auxiliary space. Each element is pushed to inbox once, moved to outbox once and popped once — three O(1) operations over its lifetime.

What is the brute-force approach, and how do you optimise it?

Move everything back and forth each time: O(n) per op time, O(n) space. Lazy transfer (inbox → outbox only when outbox is empty): O(1) amortised time, O(n) space. Each element is moved at most once.

What follow-up questions do interviewers ask about Implement a Queue Using Two Stacks?

Add peek(). Implement a stack with two queues (next question).