Implement Queue using Stacks

Q: What is the best time complexity for Implement Queue using Stacks?

Optimal (input and output stacks, lazy transfer) runs in O(1) amortized per operation time and O(n) extra space. Each value is moved from `in` to `out` at most once, so n operations do O(n) work in total.

Q: Which pattern does Implement Queue using Stacks use?

It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.

Q: Is there a brute force solution for Implement Queue using Stacks?

Yes. Brute force (keep the front on top at all times) takes O(n) push, O(1) pop/peek/empty time and O(n) space. Keep the oldest element on top of the main stack.

Q: Which edge cases should I test for Implement Queue using Stacks?

Pushing after some pops: new values must still come out after the older ones; empty on a brand-new queue; Alternating push and pop many times.

Easy Stack Stack Basics Original on LeetCode

Reported atGoldman Sachs Walmart Global Tech

Implement Queue using Stacks is a easy stack problem solved with the stack basics pattern. The best approach, optimal (input and output stacks, lazy transfer), runs in O(1) amortized per operation time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (keep the front on top at all times) up.

Problem

Build a first-in-first-out queue, MyQueue, using only two stacks and their standard operations (push to the top, read or remove the top, size, is-empty). MyQueue() creates an empty queue.

push(int x) adds x at the back of the queue. pop() removes the element at the front and returns it, and peek() returns that front element without removing it. empty() returns true when the queue holds no elements and false otherwise.

Examples

Example 1

Input: MyQueue(), push(6), push(2), peek(), push(8), pop(), pop(), empty(), pop(), empty()
Output: 6, 6, 2, false, 8, true
Why: Values leave in the order they arrived: 6 first, then 2, then 8, after which the queue is empty.

Example 2

Input: MyQueue(), empty(), push(5), empty(), peek(), pop(), empty()
Output: true, false, 5, 5, true
Why: A fresh queue is empty; one push makes it non-empty until that value is popped.

Constraints

1 <= x <= 9
At most 100 calls to push, pop, peek and empty.
pop and peek are only called on a non-empty queue.
Use only standard stack operations: push to top, look at / pop from top, size and is-empty.
Follow-up: make each operation O(1) amortized.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (keep the front on top at all times)	`O(n) push, O(1) pop/peek/empty`	`O(n)`
Optimal (input and output stacks, lazy transfer)	`O(1) amortized per operation`	`O(n)`

1Brute force (keep the front on top at all times)

TimeO(n) push, O(1) pop/peek/emptyEach push moves all n stored elements twice.

SpaceO(n)The two stacks hold n elements together.

Keep the oldest element on top of the main stack. To push, move everything to a helper stack, push the new value at the bottom of the main stack, and move everything back. Then pop and peek are a single stack operation.

push(x): pop every element from main onto helper; push x on main; pop every element from helper back onto main.
pop(): pop from main. peek(): look at the top of main.
empty(): return whether main is empty.

class MyQueue {
    private final Deque<Integer> main = new ArrayDeque<>();
    private final Deque<Integer> helper = new ArrayDeque<>();

    public MyQueue() {}

    public void push(int x) {
        while (!main.isEmpty()) helper.push(main.pop());
        main.push(x);
        while (!helper.isEmpty()) main.push(helper.pop());
    }

    public int pop() { return main.pop(); }

    public int peek() { return main.peek(); }

    public boolean empty() { return main.isEmpty(); }
}

class MyQueue:
    def __init__(self):
        self.main = []
        self.helper = []

    def push(self, x: int) -> None:
        while self.main:
            self.helper.append(self.main.pop())
        self.main.append(x)
        while self.helper:
            self.main.append(self.helper.pop())

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

    def peek(self) -> int:
        return self.main[-1]

    def empty(self) -> bool:
        return not self.main

class MyQueue {
    stack<int> mainSt, helper;

public:
    MyQueue() {}

    void push(int x) {
        while (!mainSt.empty()) { helper.push(mainSt.top()); mainSt.pop(); }
        mainSt.push(x);
        while (!helper.empty()) { mainSt.push(helper.top()); helper.pop(); }
    }

    int pop() {
        int v = mainSt.top();
        mainSt.pop();
        return v;
    }

    int peek() { return mainSt.top(); }

    bool empty() { return mainSt.empty(); }
};

class MyQueue {
    constructor() {
        this.main = [];
        this.helper = [];
    }

    push(x) {
        while (this.main.length > 0) this.helper.push(this.main.pop());
        this.main.push(x);
        while (this.helper.length > 0) this.main.push(this.helper.pop());
    }

    pop() { return this.main.pop(); }

    peek() { return this.main[this.main.length - 1]; }

    empty() { return this.main.length === 0; }
}

2Optimal (input and output stacks, lazy transfer)

TimeO(1) amortized per operationEach value is moved from `in` to `out` at most once, so n operations do O(n) work in total.

SpaceO(n)The two stacks hold n elements together.

New values always go onto an in stack. Reads come from an out stack, whose top is the oldest value. Only when out is empty do you pour all of in into it; the pour reverses the order, so the oldest value lands on top. Every value is pushed and popped at most twice in total, which makes each operation O(1) amortized.

push(x): push x on in.
Helper move(): if out is empty, pop everything from in onto out.
pop(): move(), then pop from out. peek(): move(), then look at the top of out.
empty(): true when both stacks are empty.

class MyQueue {
    private final Deque<Integer> in = new ArrayDeque<>();
    private final Deque<Integer> out = new ArrayDeque<>();

    public MyQueue() {}

    public void push(int x) { in.push(x); }

    private void move() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) out.push(in.pop());
        }
    }

    public int pop() {
        move();
        return out.pop();
    }

    public int peek() {
        move();
        return out.peek();
    }

    public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}

class MyQueue:
    def __init__(self):
        self.inp = []
        self.out = []

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

    def _move(self) -> None:
        if not self.out:
            while self.inp:
                self.out.append(self.inp.pop())

    def pop(self) -> int:
        self._move()
        return self.out.pop()

    def peek(self) -> int:
        self._move()
        return self.out[-1]

    def empty(self) -> bool:
        return not self.inp and not self.out

class MyQueue {
    stack<int> in, out;

    void move() {
        if (out.empty()) {
            while (!in.empty()) { out.push(in.top()); in.pop(); }
        }
    }

public:
    MyQueue() {}

    void push(int x) { in.push(x); }

    int pop() {
        move();
        int v = out.top();
        out.pop();
        return v;
    }

    int peek() {
        move();
        return out.top();
    }

    bool empty() { return in.empty() && out.empty(); }
};

class MyQueue {
    constructor() {
        this.in = [];
        this.out = [];
    }

    push(x) { this.in.push(x); }

    move() {
        if (this.out.length === 0) {
            while (this.in.length > 0) this.out.push(this.in.pop());
        }
    }

    pop() {
        this.move();
        return this.out.pop();
    }

    peek() {
        this.move();
        return this.out[this.out.length - 1];
    }

    empty() { return this.in.length === 0 && this.out.length === 0; }
}

Edge cases to test

Pushing after some pops: new values must still come out after the older ones
empty on a brand-new queue
Alternating push and pop many times

Hints

Hint 1

Pouring one stack into another reverses the order. What does reversing a stack's order turn it into?

Hint 2

Use one stack for incoming values and one for outgoing values. When do you actually need to pour?

Hint 3

Only refill the outgoing stack when it is empty. Each value is then moved at most once.

FAQ

What is the best time complexity for Implement Queue using Stacks?

Optimal (input and output stacks, lazy transfer) runs in O(1) amortized per operation time and O(n) extra space. Each value is moved from `in` to `out` at most once, so n operations do O(n) work in total.

Which pattern does Implement Queue using Stacks use?

It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.

Is there a brute force solution for Implement Queue using Stacks?

Yes. Brute force (keep the front on top at all times) takes O(n) push, O(1) pop/peek/empty time and O(n) space. Keep the oldest element on top of the main stack.

Which edge cases should I test for Implement Queue using Stacks?

Pushing after some pops: new values must still come out after the older ones; empty on a brand-new queue; Alternating push and pop many times.