LeetCode 232. Implement Queue using Stacks

Question

• 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.

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

class MyQueue {

    Stack<Integer> queue = new Stack<>();
    Stack<Integer> stack = new Stack<>();
    public void push(int x){
        stack.push(x);
    }
    public int pop(){
        peek();
        return queue.pop();
    }
    public int peek(){
        if(queue.empty())
            while(!stack.empty())
                queue.push(stack.pop());
        return queue.peek();
    }
    public boolean empty(){
        return stack.empty() && queue.empty();
    }
}

Complexity:

Time complexity: O(1)

Space complexity: O(n)