# LeetCode 232: Implement Queue using Stacks

## Problem Restatement

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

The queue must support:

| Operation | Meaning |
|---|---|
| `push(x)` | Add `x` to the back of the queue |
| `pop()` | Remove and return the front element |
| `peek()` | Return the front element without removing it |
| `empty()` | Return whether the queue is empty |

A queue follows FIFO order:

```text
First In, First Out
```

A stack follows LIFO order:

```text
Last In, First Out
```

The challenge is to simulate FIFO behavior using only stacks.

LeetCode states that only standard stack operations are allowed:

```text
push to top
peek/pop from top
size
is empty
```

The problem also asks for amortized `O(1)` complexity for queue operations. ([leetcode.com](https://leetcode.com/problems/implement-queue-using-stacks/?utm_source=chatgpt.com))

## Input and Output

We implement a class:

```python
class MyQueue:
```

Supported operations:

| Method | Return |
|---|---|
| `push(x)` | None |
| `pop()` | Front value |
| `peek()` | Front value |
| `empty()` | Boolean |

Example sequence:

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

## Examples

Example 1:

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

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

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

Explanation:

```text
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:

```text
1
2
3
```

the stack becomes:

```text
top -> 3
       2
       1
```

But a queue should remove:

```text
1
```

first.

A stack removes:

```text
3
```

first.

So one plain stack gives the wrong order.

## Key Insight

We can reverse the order twice.

Use two stacks:

| Stack | Purpose |
|---|---|
| `in_stack` | Receives new elements |
| `out_stack` | Provides front elements |

### Push

When pushing:

```text
push(1)
push(2)
push(3)
```

store everything in `in_stack`.

```text
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.

```text
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:

```text
1, 2, 3
```

After pushing into `in_stack`:

```text
top -> 3, 2, 1
```

Moving them into `out_stack` reverses the order:

```text
top -> 1, 2, 3
```

So:

```text
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:

```text
a, b, c
```

Then `in_stack` stores:

```text
top -> c, b, a
```

After transfer:

```text
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:

```python
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:

```text
O(1)
```

This is called amortized constant time.

## Complexity

| Operation | Time | Why |
|---|---|---|
| `push` | `O(1)` | Single stack append |
| `pop` | Amortized `O(1)` | Each element transferred once |
| `peek` | Amortized `O(1)` | Same reasoning as `pop` |
| `empty` | `O(1)` | Two length checks |

Space complexity:

| Metric | Value |
|---|---|
| Space | `O(n)` |

All queue elements are stored across the two stacks.

## Implementation

```python
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:

```python
self.in_stack = []
self.out_stack = []
```

New elements always enter `in_stack`:

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

The helper function `move()` transfers elements:

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

This reverses the order.

For `pop()`:

```python
if not self.out_stack:
    self.move()
```

We refill `out_stack` only when necessary.

Then:

```python
return self.out_stack.pop()
```

removes the queue front.

For `peek()`:

```python
return self.out_stack[-1]
```

returns the queue front without removing it.

For `empty()`:

```python
return not self.in_stack and not self.out_stack
```

Both stacks must be empty.

## Testing

```python
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()
```

| Test | Why |
|---|---|
| Empty queue | Initial state |
| Multiple pushes | Order preservation |
| `peek()` before `pop()` | Front access without removal |
| Interleaved operations | Real queue behavior |
| Final empty check | All elements removed correctly |