EasyStackDesignQueue

Implement Stack using Queues

1 approach, code in every language

Build a last-in-first-out (LIFO) stack whose entire internal storage is limited to standard queues. A queue only exposes first-in-first-out operations: enqueue a value at the back, dequeue the value at the front, peek at the front value, and check whether it is empty.

Implement the class MyStack with the following methods: push(x) adds element x to the top of the stack, pop() removes and returns the element on top, top() returns the top element without removing it, and empty() reports whether the stack currently holds no elements.

You may use one or more queues, but you may only interact with them through their standard queue operations.

Example 1

Input: operations = ["MyStack", "push", "push", "top", "pop", "empty"] args = [[], [1], [2], [], [], []]

Output: [null, null, null, 2, 2, false]

After pushing 1 then 2, the top is 2. pop removes and returns 2, leaving 1 in the stack so empty is false.

Example 2

Input: operations = ["MyStack", "push", "pop", "empty"] args = [[], [5], [], []]

Output: [null, null, 5, true]

A single element 5 is pushed then popped, so the stack ends up empty.

Constraints

1 <= x <= 9
At most 100 calls will be made to push, pop, top, and empty.
All calls to pop and top are valid: they are only made on a non-empty stack.

Single Queue with Rotation on Push

Use one queue and, right after enqueuing the new value, rotate the older elements behind it so the newest sits at the front.

Loading animation…

Intuition

A queue serves elements oldest-first, but a stack needs newest-first. The trick is to fix the ordering at push time so that reads are trivial. After enqueuing x at the back, we dequeue and re-enqueue every element that was already present, one at a time. That rotation carries x all the way to the front while preserving the relative order of the rest. From then on, the front of the queue is always the most recently pushed value, so pop and top become plain queue front operations.

Algorithm walkthrough

1Keep a single queue that always stores elements in stack order, newest at the front.
2For push(x), first enqueue x at the back of the queue.
3Then perform size minus one rotations: dequeue the front element and enqueue it again, which slides x forward until it reaches the front.
4For pop(), dequeue and return the front element, which is the most recently pushed value.
5For top(), return the front element without removing it; for empty(), report whether the queue has zero elements.
6Push costs O(n) because of the rotation, while pop, top, and empty are each O(1).

Implementation

from collections import deque

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

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            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

Time

O(n) for push because of the rotation; O(1) for pop, top, and empty.

Space

O(n) to hold the n elements currently in the stack.

Front-loading the work into push keeps every read operation constant time.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free