LeetCode 225 - Implement Stack using Queues

The problem asks us to implement a stack data structure while using only queue operations internally. A stack follows the Last-In-First-Out, or LIFO, principle. This means the most recently inserted element must be removed first.

leetcodeeasystackdesignqueue

LeetCode Problem 225

Difficulty: 🟢 Easy
Topics: Stack, Design, Queue

Solution

Problem Understanding

The problem asks us to implement a stack data structure while using only queue operations internally. A stack follows the Last-In-First-Out, or LIFO, principle. This means the most recently inserted element must be removed first. In contrast, a queue follows the First-In-First-Out, or FIFO, principle, where elements leave in the same order they entered.

We must design a MyStack class that supports the standard stack operations:

  • push(x) inserts an element onto the top of the stack
  • pop() removes and returns the top element
  • top() returns the current top element without removing it
  • empty() checks whether the stack contains any elements

The challenge comes from the restriction that we are only allowed to use queue operations. We cannot directly use a built-in stack. Valid queue operations are:

  • insert at the back
  • remove from the front
  • inspect the front element
  • check size
  • check whether empty

The input in LeetCode is represented as a sequence of method calls. For example:

["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

means:

  1. Create a new stack
  2. Push 1
  3. Push 2
  4. Read the top element
  5. Pop the top element
  6. Check whether the stack is empty

The expected output corresponds to the return value of each operation.

The constraints are very small. At most 100 operations will be performed. This means efficiency is not extremely critical, but the goal is still to design a correct and elegant solution that simulates stack behavior using queues.

An important guarantee is that every pop() and top() call is valid. We never need to handle popping from an empty stack.

Several edge cases are important:

  • Pushing only one element and then popping it
  • Multiple consecutive pushes before any pops
  • Calling top() multiple times without modifying the stack
  • Ensuring empty() correctly reflects the state after all elements are removed

The main difficulty is preserving LIFO behavior while using FIFO containers internally.

Approaches

Brute Force Approach

A straightforward way to simulate a stack with queues is to maintain all elements in insertion order and, whenever we need to perform pop() or top(), repeatedly move elements between two queues until only the last inserted element remains accessible.

For example, suppose the queue contains:

1 -> 2 -> 3

where 3 is the logical stack top.

To pop the top element, we repeatedly dequeue from the first queue and enqueue into the second queue until only one element remains. That final element is the stack top.

This works because the last remaining element is exactly the most recently inserted value. After removing it, we swap the queues and continue.

The brute-force method is correct because it explicitly reconstructs stack behavior every time a removal happens. However, it is inefficient because every pop() or top() operation may require moving almost all elements between queues.

Optimal Approach

A more elegant solution is to make the queue always maintain stack order after every push().

The key observation is that queues preserve relative ordering, so if we rotate the queue immediately after insertion, we can place the newest element at the front. Then the queue's front always represents the stack top.

For example:

Push 1
Queue: [1]

Push 2
Queue after insertion: [1, 2]
Rotate once:
Queue: [2, 1]

Push 3
Queue after insertion: [2, 1, 3]
Rotate twice:
Queue: [3, 2, 1]

Now the queue front always behaves like the top of a stack.

This makes pop() and top() extremely simple because the correct element is always at the front.

Approach Time Complexity Space Complexity Notes
Brute Force Push: O(1), Pop: O(n), Top: O(n) O(n) Moves elements between two queues during removal
Optimal Push: O(n), Pop: O(1), Top: O(1) O(n) Rotates queue after each insertion so top stays at front

Algorithm Walkthrough

  1. Initialize a single queue to store stack elements.

The queue will always maintain the stack's top element at the front. This allows direct access for pop() and top() operations. 2. When pushing a new element, insert it at the back of the queue.

At this moment, the newest element is at the end, but a stack requires it to become the top. 3. Rotate the queue after insertion.

Suppose the queue size becomes k after insertion. We remove the first k - 1 elements one by one and append them back to the queue.

This moves the newly inserted element from the back to the front. 4. For pop(), remove and return the front element.

Because of the rotation step, the queue front is always the logical stack top. 5. For top(), simply return the front element without removing it. 6. For empty(), check whether the queue contains any elements.

Why it works

The core invariant is that the queue front always stores the current stack top.

After each push(), we rotate the queue so the newly inserted element moves to the front. Since stacks require the most recently inserted element to be removed first, placing the newest value at the front ensures that normal queue dequeue operations behave exactly like stack pops.

Because this invariant is maintained after every insertion, all future pop() and top() operations automatically produce correct stack behavior.

Python Solution

from collections import deque
from typing import Deque

class MyStack:

    def __init__(self):
        self.queue: Deque[int] = deque()

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

        # Rotate the queue so the new element becomes the front
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

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

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

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

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

The implementation uses Python's deque from the collections module because it efficiently supports queue operations from both ends.

Inside __init__, we create a single queue that stores all stack elements.

The push() method first inserts the new element at the back of the queue. Since this element should become the stack top, we rotate all older elements behind it. The loop executes len(queue) - 1 times, moving the previous front element to the back each time.

The pop() method removes from the front because the queue front always represents the stack top.

The top() method directly reads the front element without modifying the queue.

The empty() method checks whether the queue length is zero.

This implementation exactly follows the invariant established in the algorithm walkthrough.

Go Solution

type MyStack struct {
    queue []int
}

func Constructor() MyStack {
    return MyStack{
        queue: []int{},
    }
}

func (this *MyStack) Push(x int) {
    this.queue = append(this.queue, x)

    // Rotate previous elements behind the new element
    size := len(this.queue)
    for i := 0; i < size-1; i++ {
        front := this.queue[0]
        this.queue = this.queue[1:]
        this.queue = append(this.queue, front)
    }
}

func (this *MyStack) Pop() int {
    top := this.queue[0]
    this.queue = this.queue[1:]
    return top
}

func (this *MyStack) Top() int {
    return this.queue[0]
}

func (this *MyStack) Empty() bool {
    return len(this.queue) == 0
}

/**
 * Your MyStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Empty();
 */

The Go implementation uses a slice to simulate a queue.

Appending to the slice corresponds to enqueueing at the back. Removing the first element is done using slicing:

this.queue = this.queue[1:]

Unlike Python's deque, Go slices do not provide constant-time front removal internally because elements are logically shifted through slicing semantics. However, given the small constraints, this implementation is completely acceptable.

Go does not require explicit handling for integer overflow here because all values are very small.

Worked Examples

Example 1

Input:

["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

Step-by-step trace

Operation Queue State Return Value
Initialize [] null
push(1) [1] null
push(2) [2, 1] null
top() [2, 1] 2
pop() [1] 2
empty() [1] false

Detailed push(2) rotation

Before rotation:

[1, 2]

Rotate once:

  • Remove 1
  • Append 1

Result:

[2, 1]

Now the newest element is at the front, which correctly represents the stack top.

Complexity Analysis

Measure Complexity Explanation
Time Push: O(n), Pop: O(1), Top: O(1), Empty: O(1) Push rotates all previous elements
Space O(n) The queue stores all stack elements

The only expensive operation is push(). After inserting a new element, we rotate all older elements behind it. If the stack currently contains n elements, this requires n - 1 queue operations.

All other operations are constant time because the stack top is always stored at the queue front.

The space complexity is linear because every inserted element must be stored in the queue.

Test Cases

from collections import deque
from typing import Deque

class MyStack:

    def __init__(self):
        self.queue: Deque[int] = deque()

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

        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

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

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

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

# Provided example
stack = MyStack()
stack.push(1)
stack.push(2)
assert stack.top() == 2  # newest element should be on top
assert stack.pop() == 2  # pop should remove newest element
assert stack.empty() is False  # one element still remains

# Single element case
stack = MyStack()
stack.push(5)
assert stack.top() == 5  # only element should be top
assert stack.pop() == 5  # popping should remove the element
assert stack.empty() is True  # stack should now be empty

# Multiple pushes and pops
stack = MyStack()
stack.push(1)
stack.push(2)
stack.push(3)
assert stack.pop() == 3  # LIFO order
assert stack.pop() == 2  # next newest element
assert stack.pop() == 1  # oldest element removed last
assert stack.empty() is True  # all elements removed

# Interleaved operations
stack = MyStack()
stack.push(10)
stack.push(20)
assert stack.pop() == 20  # newest removed first
stack.push(30)
assert stack.top() == 30  # latest push becomes top
assert stack.pop() == 30  # remove latest element
assert stack.pop() == 10  # remaining oldest element
assert stack.empty() is True  # stack fully emptied

# Multiple top calls
stack = MyStack()
stack.push(7)
stack.push(8)
assert stack.top() == 8  # top should not remove element
assert stack.top() == 8  # repeated top should be stable
assert stack.pop() == 8  # value should still exist

# Boundary value test
stack = MyStack()
stack.push(1)
stack.push(9)
assert stack.top() == 9  # largest allowed value on top
Test Why
Basic example Verifies standard stack behavior
Single element Ensures minimal case works correctly
Multiple pushes and pops Confirms proper LIFO ordering
Interleaved operations Validates state consistency after mixed operations
Multiple top calls Ensures top() does not modify the stack
Boundary values Confirms constraints are handled properly

Edge Cases

One important edge case is pushing only a single element and immediately popping it. Many incorrect implementations accidentally leave stale state behind after removal. In this implementation, the queue becomes empty naturally after the front element is removed, so empty() correctly returns True.

Another important case is repeated calls to top() without popping. Since top() should only inspect the stack and not modify it, an incorrect implementation might accidentally remove elements while reading them. Here, top() directly accesses the queue front without altering the queue structure, so repeated calls always return the same value.

A third edge case involves multiple consecutive pushes before any pops occur. Without proper queue rotation, the oldest element would remain at the front and stack behavior would break. The rotation step after every insertion guarantees that the newest element always moves to the front, preserving correct LIFO ordering regardless of how many pushes occur in sequence.