LeetCode 225: Implement Stack using Queues

Problem Restatement

We need to implement a stack using only queues.

A stack follows LIFO order:

last in, first out

A queue follows FIFO order:

first in, first out

We need to implement the class MyStack with these operations:

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

Class shape:

class MyStack:

    def __init__(self):
        ...

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

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

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

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

Example

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

Output:

None
None
2
2
False

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

top -> 2
       1

So:

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

First Thought

A queue normally removes the oldest element first.

If we simply enqueue values:

push 1
push 2

the queue becomes:

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:

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

Push 3:

front [2, 1, 3] back

Now rotate the old elements behind 3:

front [3, 2, 1] back

Now the queue front is the stack top.

Then:

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:

q = []

Call:

push(1)

Queue size before push is 0.

Push 1:

q = [1]

No rotation needed.

Call:

push(2)

Queue size before push is 1.

Push 2:

q = [1, 2]

Rotate one old element:

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

Now front is 2.

Call:

push(3)

Queue size before push is 2.

Push 3:

q = [2, 1, 3]

Rotate two old elements:

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

Now the stack order is correct:

top -> 3, then 2, then 1

Correctness

The algorithm maintains this invariant:

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.

The queue itself stores n elements.

Implementation

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:

self.q = deque()

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

size = len(self.q)

Add the new value to the queue:

self.q.append(x)

Rotate the old elements behind the new value:

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

Now the new value is at the front.

Pop from the front:

return self.q.popleft()

Read the front without removing it:

return self.q[0]

Check emptiness:

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.

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

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