EasyStackDesignQueue

Implement Queue using Stacks

1 approach, code in every language

Build a first-in-first-out (FIFO) queue whose entire internal storage is limited to standard stacks. A stack only exposes the usual last-in-first-out operations: push a value on top, pop the top value, look at the top value, and check whether it is empty.

Implement the class MyQueue with the following methods: push(x) adds element x to the back of the queue, pop() removes and returns the element at the front, peek() returns the front element without removing it, and empty() reports whether the queue currently holds no elements.

Your implementation may use one or more stacks, but you are not allowed to reach into the middle of any stack. Every access must go through the top of a stack.

Example 1

Input: operations = ["MyQueue", "push", "push", "peek", "pop", "empty"] args = [[], [1], [2], [], [], []]

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

After pushing 1 then 2, peek returns the front element 1. pop removes and returns 1. The queue still holds 2, so empty is false.

Example 2

Input: operations = ["MyQueue", "push", "pop", "empty"] args = [[], [7], [], []]

Output: [null, null, 7, true]

A single element 7 is pushed and immediately popped, leaving the queue empty.

Constraints

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

Two Stacks with Amortized Transfer

Keep an input stack for pushes and an output stack for pops; move elements over only when the output stack runs dry.

Loading animation…

Intuition

A single stack reverses order, so newly pushed items sit on top while the queue front is buried at the bottom. If you pour one stack into another, the order flips a second time and the oldest element ends up on top. That is exactly the queue front. Rather than transferring on every operation, we only refill the output stack when it is empty, so each element is moved at most once from input to output. That lazy transfer gives amortized O(1) cost per call even though a single pop can occasionally take O(n).

Algorithm walkthrough

1Maintain two stacks: input receives every pushed value, and output serves every pop or peek.
2For push(x), simply place x on top of the input stack in O(1).
3For peek(), if the output stack is empty, pop everything from input and push it onto output, reversing the order so the queue front is on top.
4Return the top of the output stack for peek(), or remove and return that top for pop().
5For empty(), the queue has no elements only when both the input and output stacks are empty.
6Because each value is transferred from input to output exactly once, the total work across n operations is O(n), giving amortized constant time.

Implementation

class MyQueue:
    def __init__(self):
        self.input = []
        self.output = []

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

    def pop(self) -> int:
        self.peek()
        return self.output.pop()

    def peek(self) -> int:
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]

    def empty(self) -> bool:
        return not self.input and not self.output

Time

Amortized O(1) per operation; a single pop or peek can be O(n) when it triggers a transfer.

Space

O(n) to store the n elements currently held across the two stacks.

Each element is moved from the input stack to the output stack at most once, so n operations cost O(n) total.

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