author: Sergei Golitsyn

link: https://leetcode.com/problems/implement-queue-using-stacks/

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

Notes:

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Solution

In this problem, I will show you only one solution. The main trick will be in pop and peak operations. But hold on. Let’s do it step by step. First of all, we have to prepare a class and needed data structures:

static class MyQueue {

    Stack<Integer> current;
    Stack<Integer> tmp;

    public MyQueue() {
        current = new Stack<>();
        tmp = new Stack<>();
    }
static class MyQueue {

        Stack<Integer> current;
        Stack<Integer> tmp;

        public MyQueue() {
            current = new Stack<>();
            tmp = new Stack<>();
        }
}

And now, let’s add a push method:

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

Simple and clear, just add an element into the stack.

And what about pop? For pop operation, we

have to move all elements from the current stack to the tmp stack

And before it, we should check out tmp stack. If tmp stack contains an elements we can simply return an element from this stack.

public int pop() {
    if (!tmp.isEmpty()) {
        return tmp.pop();
    }
    while (!current.isEmpty()) {
        tmp.push(current.pop());
    }
    return tmp.pop();
}

Let’s try to draw a picture.

  1. push 1. → 1

  2. push 2. → 2, 1

  3. push 3. → 3, 2, 1

  4. pop. → move to tmp -→ cur: 2, 1, tmp: 3

                                          cur: 1,     tmp: 2, 3

                                      cur:         tmp: 1, 2, 3

  5. do you see it? after moving elements, all elements in the tmp stack are in the correct order.

Ahh, I was a bit shocked, but it is true. If you move elements from one stack into another, you will have elements in insert order, like in a queue.

Now, let’s implement peek function:

public int peek() {
    if (!tmp.isEmpty()) {
        return tmp.peek();
    }
    while (!current.isEmpty()) {
        tmp.push(current.pop());
    }
    return tmp.peek();
}

Same logic as in the pop method.

And finally isEmpty method. Don’t forget that we have to check two queues.

public boolean empty() {
    if (!tmp.isEmpty()) {
        return tmp.isEmpty();
    }
    return current.isEmpty();
}

Complexity Analysis