My Java Solution with Comments


  • 0
    A
    class MyStack {
    //Main two queue(s), alpha and beta.
    Queue<Integer> alpha = new LinkedList<Integer>(); // primary queue
    Queue<Integer> beta = new LinkedList<Integer>();  // auxiliary queue
    
    // Push element x onto stack.
    public void push(int x) {
        alpha.add(x); // always add element to primary
    }
    
    // Removes the element on top of the stack.
    public void pop() {
        getLastElement(); //discards the top element
    }
    
    // Get the top element.
    public int top() {
        int lastElement = getLastElement();
        push(lastElement); // top() does not remove the element, so we re-push it to the queue.
        return lastElement;
    }
    
    private int getLastElement(){
        while(alpha.size()>1){
            beta.add(alpha.remove());
        }
        int latestElement = alpha.remove(); // popped last element
        
        //swap alpha and beta - make auxiliary queue the primary queue
        Queue<Integer> temp = alpha;
        alpha = beta;
        beta = temp;
        
        return latestElement;
    }
    
    // Return whether the stack is empty.
    public boolean empty() {
        return alpha.size()==0;
        
    }
    

    }

    This question should really be on the all-time classic hits for data-structures.


Log in to reply
 

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