Implement Stack using Queues

Easy Stack Stack Basics Original on LeetCode

Implement Stack using Queues is a easy stack problem solved with the stack basics pattern. The best approach, optimal (single queue, rotate on push), runs in O(n) push, O(1) pop/top/empty time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (two queues, dig out the last element) up.

Problem

Build a last-in-first-out stack, MyStack, using only queues and their standard operations (add to the back, read or remove the front, size, is-empty). MyStack() creates an empty stack.

push(int x) places x on top of the stack. pop() removes the top element and returns it, and top() returns the top element without removing it. empty() returns true when the stack holds no elements and false otherwise.

Examples

Example 1

Input
MyStack(), push(4), push(7), top(), push(1), pop(), pop(), empty(), top()
Output
7, 1, 7, false, 4
Why
The most recent value always leaves first: 1 goes out before 7, and 4 is left on top.

Example 2

Input
MyStack(), empty(), push(3), pop(), empty()
Output
true, 3, true
Why
A new stack is empty; after pushing and popping 3 it is empty again.

Constraints

  • 1 <= x <= 9
  • At most 100 calls to push, pop, top and empty.
  • pop and top are only called on a non-empty stack.
  • Use only standard queue operations: add to the back, look at / remove from the front, size and is-empty.
  • Follow-up: can you do it with a single queue?

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 11 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.

ApproachTimeSpace
Brute force (two queues, dig out the last element)O(1) push, O(n) pop/topO(n)
Optimal (single queue, rotate on push)O(n) push, O(1) pop/top/emptyO(n)

1Brute force (two queues, dig out the last element)

TimeO(1) push, O(n) pop/topEach pop or top walks all n elements through the helper queue once.
SpaceO(n)The two queues hold n elements together.

Push simply appends to the main queue. To pop or read the top, move all but the last element into a helper queue, deal with the last one, then swap the roles of the two queues.

  1. push(x): add x to the back of main.
  2. pop(): move size - 1 elements from main to helper; remove the last one from main and remember it; swap main and helper; return the value.
  3. top(): same as pop, but also add the last element to helper before swapping so it stays stored.
  4. empty(): return whether main is empty.
class MyStack {
    private Queue<Integer> main = new ArrayDeque<>();
    private Queue<Integer> helper = new ArrayDeque<>();

    public MyStack() {}

    public void push(int x) {
        main.offer(x);
    }

    public int pop() {
        while (main.size() > 1) helper.offer(main.poll());
        int last = main.poll();
        Queue<Integer> tmp = main;
        main = helper;
        helper = tmp;
        return last;
    }

    public int top() {
        while (main.size() > 1) helper.offer(main.poll());
        int last = main.poll();
        helper.offer(last);
        Queue<Integer> tmp = main;
        main = helper;
        helper = tmp;
        return last;
    }

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

2Optimal (single queue, rotate on push)

TimeO(n) push, O(1) pop/top/emptyEach push rotates the n - 1 older elements once; the other operations touch only the front.
SpaceO(n)One queue holding the n elements.

Keep the queue ordered so its front is always the stack's top. When x is added at the back, move the size - 1 older elements from the front to the back one by one. After that rotation x is at the front, and the older elements follow in newest-to-oldest order.

  1. push(x): add x to the back; then repeat size - 1 times: remove the front and add it to the back.
  2. pop(): remove and return the front.
  3. top(): return the front without removing it.
  4. empty(): return whether the queue is empty.
class MyStack {
    private final Queue<Integer> q = new ArrayDeque<>();

    public MyStack() {}

    public void push(int x) {
        q.offer(x);
        for (int i = 0; i < q.size() - 1; i++) {
            q.offer(q.poll());
        }
    }

    public int pop() {
        return q.poll();
    }

    public int top() {
        return q.peek();
    }

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

Edge cases to test

  • empty on a brand-new stack
  • Pushing again after the stack was emptied
  • Interleaved pushes and pops, so new values must land on top of older ones

Hints

Hint 1

A queue gives you the oldest element. To reach the newest one, everything in front of it must be moved out of the way.

Hint 2

Moving elements from the front of a queue to its back keeps them in the same queue but rotates the order.

Hint 3

After adding x at the back, rotate the other size - 1 elements behind it. Now x is at the front, exactly where a stack's top should be.

FAQ

What is the best time complexity for Implement Stack using Queues?

Optimal (single queue, rotate on push) runs in O(n) push, O(1) pop/top/empty time and O(n) extra space. Each push rotates the n - 1 older elements once; the other operations touch only the front.

Which pattern does Implement Stack using Queues 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 Stack using Queues?

Yes. Brute force (two queues, dig out the last element) takes O(1) push, O(n) pop/top time and O(n) space. Push simply appends to the main queue.

Which edge cases should I test for Implement Stack using Queues?

empty on a brand-new stack; Pushing again after the stack was emptied; Interleaved pushes and pops, so new values must land on top of older ones.