Implement Stack using Queues by@deft

Implement Stack using Queues

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` and`pop`) You must use only the standard operations of a queue, which means that only `push to back` and `peek/pop from front` are valid. Depending on 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.
image
Sergey Golitsyn HackerNoon profile picture

Sergey Golitsyn

Senior Software Engineer with 7+ YoE building massively scalable systems both from scratch and diving into a codebase

Credibility


Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (pushtoppop, 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 backpeek/pop from frontsize 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 pushpoptop, 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/

react to story with heart
react to story with light
react to story with boat
react to story with money
Sergey Golitsyn HackerNoon profile picture
by Sergey Golitsyn @deft.Senior Software Engineer with 7+ YoE building massively scalable systems both from scratch and diving into a codebase
Read my stories

Related Stories

L O A D I N G
. . . comments & more!