Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

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

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty.
• All the calls to pop and top are valid.

Follow-up: Can you implement the stack using only one queue?

Solution

Here will be two amazing variants. And you can discuss with the interviewer which variant is the best and discuss all pros and cons.

In the first variant we are going to use Two Queues, push - O(1), pop O(n).

Ok, Lets start. Our class looks like:

class MyStack {

        private Queue<Integer> current;
        private Queue<Integer> tmp;

        public MyStack() {
            current = new ArrayDeque<>();
            tmp = new ArrayDeque<>();
        }
}

Then let’s implement push operation. For it, we just need to push the element into the queue

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

Pop operation can be tricky. Firstly we have to check the current queue. If it is empty, we can throw err or return -1 for example. Then we have to move all elements except one to the tmp queue. After it we remember the last element in a current queue and finally swap the queues.

public int pop() {
    if (current.isEmpty()){
        return -1;
    }
    int size = current.size();
    for (int i = 0; i < size - 1; i ++){
        tmp.add(current.poll());
    }
    int ret = current.poll();
    current = tmp;
    return ret;
}

Let’s draw it. For example:

1) we have in currentQ elements [3, 2, 1] -→ move to temp

2) currentQ [3, 2], tmpQ = [1]

3) currentQ [3], tmpQ = [2, 1]

4) remember 3

5) currentQ = tmpQ = [2, 1]

6) return 3

Kinda the same algorithm we use for top operation:

public int top() {
    if (current.isEmpty()){
        return -1;
    }
    int size = current.size();
    for (int i = 0; i < size - 1; i ++){
        tmp.add(current.poll());
    }
    int ret = current.peek();
    tmp.add(current.poll());
    current = tmp;
    return ret;
}

And a simple method to check if our stack is empty:

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

Looks like wisdom to me.

In the second solution, we use only one Queue, but the push operation will take - O(n) time and pop O(1).

class MyStack2 {

    private Queue<Integer> current;

    public MyStack2() {
        current = new ArrayDeque<>();
    }
}

In this approach, the main trick will be in the push method:

public void push(int x) {
    current.add(x);
    int size = current.size();

    for (int i = 0; i < size-1; i ++){
        current.add(current.poll());
    }
}

We push a new element to the end of the queue. Then we move all elements step by step to the end.

For example:

1) push(1) → current add 1 = [1]

2) push(2) → current add [2, 1] → move [1, 2]

3) push(3) → current add [3, 1, 2] → move [2, 3, 1] → move [1, 2, 3]

And… and that is it =)

All other operations use the current queue

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

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

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

Oh, do you like it? leave add your comments below.

link: https://leetcode.com/problems/implement-stack-using-queues/