LeetCode 232: Implement Queue using Stacks

Problem Restatement

We need to implement a queue using only standard stack operations.

The queue must support:

A queue follows FIFO order:

First In, First Out

A stack follows LIFO order:

Last In, First Out

The challenge is to simulate FIFO behavior using only stacks.

LeetCode states that only standard stack operations are allowed:

push to top
peek/pop from top
size
is empty

The problem also asks for amortized O(1) complexity for queue operations. (leetcode.com)

Input and Output

We implement a class:

class MyQueue:

Supported operations:

Example sequence:

push(1)
push(2)
peek() -> 1
pop()  -> 1
empty() -> false

Examples

Example 1:

Input:
["MyQueue", "push", "push", "peek", "pop", "empty"]

[[], [1], [2], [], [], []]

Output:
[null, null, null, 1, 1, false]

Explanation:

Queue after push(1): [1]
Queue after push(2): [1, 2]

peek() returns 1
pop() removes 1

Queue becomes [2]

empty() returns false

First Thought: Use One Stack

Suppose we only use one stack.

If we push:

1
2
3

the stack becomes:

top -> 3
       2
       1

But a queue should remove:

1

first.

A stack removes:

3

first.

So one plain stack gives the wrong order.

Key Insight

We can reverse the order twice.

Use two stacks:

Push

When pushing:

push(1)
push(2)
push(3)

store everything in in_stack.

in_stack:
top -> 3
       2
       1

Pop

When we need the queue front:

1. Move all elements from in_stack to out_stack.
2. The order reverses.

out_stack:
top -> 1
       2
       3

Now the oldest element appears on top.

So pop() returns the correct FIFO value.

Why Two Reversals Work

Suppose elements arrive in order:

1, 2, 3

After pushing into in_stack:

top -> 3, 2, 1

Moving them into out_stack reverses the order:

top -> 1, 2, 3

So:

stack reversal + stack reversal = original order

This recreates queue behavior.

Algorithm

push(x)

Push directly into in_stack.

pop()

If out_stack is empty:

1. Move every element from in_stack into out_stack.

Then pop from out_stack.

peek()

Same logic as pop(), but return the top value without removing it.

empty()

The queue is empty only if both stacks are empty.

Correctness

All newly inserted elements are first stored in in_stack.

When out_stack becomes empty, the algorithm transfers all elements from in_stack into out_stack.

This reverses their order.

Suppose elements entered in order:

a, b, c

Then in_stack stores:

top -> c, b, a

After transfer:

top -> a, b, c

So the oldest element appears on top of out_stack.

Therefore:

• pop() removes the oldest element.
• peek() returns the oldest element.

This matches FIFO queue behavior.

Finally, the queue is empty exactly when both stacks contain no elements.

Therefore, all operations behave correctly.

Amortized Complexity

At first glance, transferring elements may look expensive.

Example:

while self.in_stack:
    self.out_stack.append(self.in_stack.pop())

This can move many elements at once.

But each element moves:

1. Into in_stack
2. Into out_stack
3. Out of out_stack

Each element is moved only a constant number of times.

So across many operations, the average cost per operation is:

O(1)

This is called amortized constant time.

Complexity

Space complexity:

All queue elements are stored across the two stacks.

Implementation

class MyQueue:

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

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def move(self) -> None:
        while self.in_stack:
            self.out_stack.append(self.in_stack.pop())

    def pop(self) -> int:
        if not self.out_stack:
            self.move()

        return self.out_stack.pop()

    def peek(self) -> int:
        if not self.out_stack:
            self.move()

        return self.out_stack[-1]

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

Code Explanation

We initialize two stacks:

self.in_stack = []
self.out_stack = []

New elements always enter in_stack:

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

The helper function move() transfers elements:

while self.in_stack:
    self.out_stack.append(self.in_stack.pop())

This reverses the order.

For pop():

if not self.out_stack:
    self.move()

We refill out_stack only when necessary.

Then:

return self.out_stack.pop()

removes the queue front.

For peek():

return self.out_stack[-1]

returns the queue front without removing it.

For empty():

return not self.in_stack and not self.out_stack

Both stacks must be empty.

Testing

def run_tests():
    q = MyQueue()

    assert q.empty() is True

    q.push(1)
    q.push(2)
    q.push(3)

    assert q.peek() == 1
    assert q.pop() == 1

    assert q.peek() == 2

    q.push(4)

    assert q.pop() == 2
    assert q.pop() == 3
    assert q.pop() == 4

    assert q.empty() is True

    print("all tests passed")

run_tests()