Implement Queue using Stacks

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

Constraints:

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

Try this Problem on your own or check similar problems:

Implement Stack using Queues

Solution:

Java
JavaScript
Python
C++

class MyQueue {
    Stack<Integer> s1, s2;
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

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

    public int pop() {
        if(s2.isEmpty()) rebalance();
        return s2.pop();
    }

    public int peek() {
        if(s2.isEmpty()) rebalance();
        return s2.peek();
    }

    public boolean empty() {
        return s1.empty() && s2.empty();
    }

    private void rebalance(){
        while(!s1.empty()) s2.push(s1.pop());
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

var MyQueue = function () {
  this.s1 = [];
  this.s2 = [];
  this.rebalance = () => {
    while (this.s1.length !== 0) this.s2.push(this.s1.pop());
  };
};

/**
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
  this.s1.push(x);
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function () {
  if (this.s2.length === 0) this.rebalance();
  return this.s2.pop();
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function () {
  if (this.s2.length === 0) this.rebalance();
  return this.s2[this.s2.length - 1];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
  return this.s1.length === 0 && this.s2.length === 0;
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

class MyQueue:

    def __init__(self):
        self.s1 = []
        self.s2 = []


    def push(self, x: int) -> None:
        self.s1.append(x)

    def pop(self) -> int:
        if len(self.s2) == 0:
            self.rebalance()
        return self.s2.pop()

    def peek(self) -> int:
        if len(self.s2) == 0:
            self.rebalance()
        return self.s2[-1]

    def empty(self) -> bool:
        return len(self.s1) == 0 and len(self.s2) == 0

    def rebalance(self):
        while len(self.s1) != 0:
            self.s2.append(self.s1.pop())


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

class MyQueue {
private:
    stack<int> s1, s2;
    void rebalance() {
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
    }
public:
    MyQueue() {}

    void push(int x) {
        s1.push(x);
    }

    int pop() {
        if (s2.empty()) rebalance();
        int val = s2.top();
        s2.pop();
        return val;
    }

    int peek() {
        if (s2.empty()) rebalance();
        return s2.top();
    }

    bool empty() {
        return s1.empty() && s2.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

Time/Space Complexity:

Time Complexity: O(1)
Space Complexity: O(n)

Explanation:

Since we use two stacks we will have linear space complexity. The core of the implementation is rebalance function which takes all elements from the first stack and place them in the second stack. What do we get in the second stack if we're using LIFO stack data structure (last in first out), well we will get a reversed order, in other words at the top of our second stack we will have the element that was at the bottom of our first stack before rebalance function was called. So we know that elements in second stack are now in order of initial insertion (FIFO first in first out). It's easy to implement pop and peek, if the second stack is not empty we just return the top element, otherwise we first rebalance and then do pop or peek. empty will just check if both stacks are empty and return true if they are, otherwise it will return false. We get amortized O(1) time complexity, but what does amortized mean? Imagine you're doing push for n times, then you do pop n times what's the total time complexity of those operations? Well for push you would of course have O(n) since s1.push(x); is O(1), but for pop you would have first rebalance which will take O(n), but all the next pop operation will take O(1) leading again to the same total time complexity of O(n).

Example 1:​

Constraints:​

Solution:​

Time/Space Complexity:​

Explanation:​

Example 1:

Constraints:

Solution:

Time/Space Complexity:

Explanation: