Implement Queue using Stacks

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:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

• You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

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

• Time complexity: Amortized O(1)O(1), Worst-case O(n)O(n). In the worst case scenario when stack s2 is empty, the algorithm pops nn elements from stack s1 and pushes nn elements to s2, where nn is the queue size. This gives 2n2n operations, which is O(n)O(n). But when stack s2 is not empty the algorithm has O(1)O(1) time complexity. So what does it mean by Amortized O(1)O(1)? Please see the next section on Amortized Analysis for more information.
• Space complexity : O(1)O(1).