# LeetCode 225: Implement Stack using Queues

## Problem Restatement

We need to implement a stack using only queues.

A stack follows LIFO order:

```text
last in, first out
```

A queue follows FIFO order:

```text
first in, first out
```

We need to implement the class `MyStack` with these operations:

| Method | Meaning |
|---|---|
| `push(x)` | Push `x` onto the stack |
| `pop()` | Remove and return the top element |
| `top()` | Return the top element without removing it |
| `empty()` | Return whether the stack is empty |

The official problem asks us to implement a LIFO stack using only two queues. Valid queue operations are push to back, peek or pop from front, size, and empty check. It also asks whether the stack can be implemented using only one queue.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Method calls on `MyStack` |
| Output | Depends on the method |
| Allowed structure | Queue only |
| Required behavior | Stack behavior |
| Important guarantee | Calls to `pop` and `top` are valid |

Class shape:

```python
class MyStack:

    def __init__(self):
        ...

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

    def pop(self) -> int:
        ...

    def top(self) -> int:
        ...

    def empty(self) -> bool:
        ...
```

## Example

```python
myStack = MyStack()
myStack.push(1)
myStack.push(2)
myStack.top()
myStack.pop()
myStack.empty()
```

Output:

```python
None
None
2
2
False
```

After pushing `1` and then `2`, the stack looks like:

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

So:

```python
top() == 2
pop() == 2
empty() == False
```

## First Thought

A queue normally removes the oldest element first.

If we simply enqueue values:

```text
push 1
push 2
```

the queue becomes:

```text
front [1, 2] back
```

Calling queue pop would remove `1`.

But stack pop should remove `2`.

So we need to rearrange the queue so the newest element becomes the front.

## Key Insight

Make the front of the queue always represent the top of the stack.

After every `push`, rotate the queue so the newly inserted value moves to the front.

Example:

```text
queue before push(3): front [2, 1] back
```

Push `3`:

```text
front [2, 1, 3] back
```

Now rotate the old elements behind `3`:

```text
front [3, 2, 1] back
```

Now the queue front is the stack top.

Then:

| Stack operation | Queue operation |
|---|---|
| `pop()` | Pop from front |
| `top()` | Peek front |
| `empty()` | Check whether queue is empty |

## Algorithm: One Queue

Use one queue `q`.

For `push(x)`:

1. Let `size` be the current queue size.
2. Push `x` to the back.
3. Rotate the previous `size` elements:
   - pop from the front
   - push to the back

This moves `x` from the back to the front.

For the other operations:

- `pop()` removes from front
- `top()` returns front
- `empty()` checks whether the queue is empty

## Walkthrough

Start:

```text
q = []
```

Call:

```python
push(1)
```

Queue size before push is `0`.

Push `1`:

```text
q = [1]
```

No rotation needed.

Call:

```python
push(2)
```

Queue size before push is `1`.

Push `2`:

```text
q = [1, 2]
```

Rotate one old element:

```text
pop 1, push 1
q = [2, 1]
```

Now front is `2`.

Call:

```python
push(3)
```

Queue size before push is `2`.

Push `3`:

```text
q = [2, 1, 3]
```

Rotate two old elements:

```text
pop 2, push 2 -> [1, 3, 2]
pop 1, push 1 -> [3, 2, 1]
```

Now the stack order is correct:

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

## Correctness

The algorithm maintains this invariant:

```text
the front of the queue is always the top of the stack
```

Initially the queue is empty, so the invariant holds.

When `push(x)` is called, `x` is first added to the back of the queue. The algorithm then rotates all elements that were already in the queue behind `x`. After these rotations, `x` becomes the front element, and the older elements remain behind it in their previous stack order.

So the invariant still holds after every push.

Because the queue front is always the stack top:

- `pop()` correctly removes the top element
- `top()` correctly returns the top element
- `empty()` correctly reports whether the stack has no elements

Therefore the implementation behaves exactly like a stack.

## Complexity

Let `n` be the number of elements currently in the stack.

| Operation | Time | Space |
|---|---:|---:|
| `push` | `O(n)` | `O(1)` extra |
| `pop` | `O(1)` | `O(1)` |
| `top` | `O(1)` | `O(1)` |
| `empty` | `O(1)` | `O(1)` |

The queue itself stores `n` elements.

## Implementation

```python
from collections import deque

class MyStack:

    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        size = len(self.q)

        self.q.append(x)

        for _ in range(size):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q) == 0
```

## Code Explanation

Create one queue:

```python
self.q = deque()
```

Before pushing the new value, record how many old elements exist:

```python
size = len(self.q)
```

Add the new value to the queue:

```python
self.q.append(x)
```

Rotate the old elements behind the new value:

```python
for _ in range(size):
    self.q.append(self.q.popleft())
```

Now the new value is at the front.

Pop from the front:

```python
return self.q.popleft()
```

Read the front without removing it:

```python
return self.q[0]
```

Check emptiness:

```python
return len(self.q) == 0
```

## Two-Queue Implementation

Another common solution uses two queues.

On push:

1. Put the new value into the temporary queue.
2. Move all old values behind it.
3. Swap the queues.

```python
from collections import deque

class MyStack:

    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

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

        while self.q1:
            self.q2.append(self.q1.popleft())

        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        return self.q1.popleft()

    def top(self) -> int:
        return self.q1[0]

    def empty(self) -> bool:
        return len(self.q1) == 0
```

This has the same time complexity as the one-queue version, but uses another queue.

## Testing

```python
def run_tests():
    s = MyStack()

    s.push(1)
    s.push(2)

    assert s.top() == 2
    assert s.pop() == 2
    assert s.empty() is False

    s.push(3)
    assert s.top() == 3
    assert s.pop() == 3
    assert s.pop() == 1
    assert s.empty() is True

    s.push(9)
    assert s.top() == 9
    assert s.pop() == 9
    assert s.empty() is True

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Push `1`, push `2`, top | Confirms newest value is on top |
| Pop after two pushes | Confirms LIFO order |
| Push after pop | Confirms structure still works |
| Empty after all pops | Confirms empty state |
| Single element | Confirms basic stack behavior |