Simple trick to avoid O(n) pushing time using two stacks


  • 0
    G

    Many have used the method of pushing all elements from one to another and pushing them back. Actually, pushing back is not necessary.

    Java

    private Stack<Integer> stack = new Stack<Integer>();
    private Stack<Integer> queue = new Stack<Integer>();
    
    private void organize(){
    	//negative times a negative is a positive!
    	//pushing a stack into another stack makes it a queue
    	while( !stack.isEmpty() ){
    		queue.push(stack.pop());
    	}
    }
    public void push(int x){
    	stack.push(x);
    }
    
    public void pop(){
    	if(queue.isEmpty())	organize();
    	queue.pop();
    }
    
    public int peek(){
    	if(queue.isEmpty())	organize();
    	return queue.peek();
    }
    
    public boolean empty(){
    	return stack.isEmpty()&&queue.isEmpty();
    }

  • 0

    That other method is quadratic, not exponential.


  • 0
    G

    Oh thank you, I have mixed up total runtime and worst case runtime.
    Was like if you push n times, that would be n! of time. How silly was I!


Log in to reply
 

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