Why is this Java solution with 2 stacks slow?


  • 0
    H

    class MyQueue {
    private Deque<Integer> stack = new ArrayDeque<Integer>();
    private Deque<Integer> rev = new ArrayDeque<Integer>();

    // Push element x to the back of queue.
    public void push(int x) {
        while(!stack.isEmpty()){
            rev.push(stack.pop());
        }
        rev.push(x);
    }
    
    // Removes the element from in front of queue.
    public void pop() {
        while(!rev.isEmpty()){
            stack.push(rev.pop());
        }
        stack.pop();
    }
    
    // Get the front element.
    public int peek() {
        while(!rev.isEmpty()){
            stack.push(rev.pop());
        }
        return stack.peek();
    }
    
    // Return whether the queue is empty.
    public boolean empty() {
        return stack.isEmpty()&&rev.isEmpty();
    }
    

    }

    This code took 252 ms and is showing up as slower than 99% of the java solutions. I also tried the making the pop and peek O(1) and push O(2n) too, but that is still slower than 98% of the java solutions.

    Anyone care to enlighten me how to make it faster?

    Thanks!


  • 0
    L

    It's not a smart way to do while loop first in all the operations pop() peek() and push(), you can modify them to do while loop only when necessary. And another point is the speed on OJ is very unstable, it fluctuates heavily with same submission, nevermind


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.