107ms java using two queues


  • 0
    S
    class MyStack {
    
    Queue<Integer> primaryQueue = new LinkedList<Integer>(); 
    Queue<Integer> bufferedQueue = new LinkedList<Integer>();
    Integer cachedTop = null; // little optimization 
    
    // Push element x onto stack.
    public void push(int x) {
        // push happens only primaryQueue
        primaryQueue.add(x);
        cachedTop = x; 
    }
    
    // Removes the element on top of the stack.
    public void pop() {
        if(empty()) return; 
        
        rearrangeElements(); 
        primaryQueue.poll();
    }
    
    // Get the top element.
    public int top() {
        if(cachedTop != null) return cachedTop; 
        
        cachedTop = primaryQueue.peek();
        return cachedTop; 
    }
    
    // Return whether the stack is empty.
    public boolean empty() {
        return (primaryQueue.size() ==0 && bufferedQueue.size() == 0); 
    }
    
    private void checkAndSwapQueues() {
        if(primaryQueue.size() == 0) { 
            Queue<Integer> temp = primaryQueue; 
            primaryQueue = bufferedQueue; 
            bufferedQueue = temp; 
        } 
    }
    
    private void rearrangeElements() {
        checkAndSwapQueues();
        // pop and push to buffered until got one last 
        while(primaryQueue.size() > 1) { 
            Integer e = primaryQueue.poll();
            bufferedQueue.add(e);
            cachedTop = e; 
        }        
    }
    

    }


Log in to reply
 

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