Leetcode 155 Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Solution 1: Use 2 stack, one stock the regular operation, the other one only store the min value.

 class MinStack {  
   Deque<Integer> stack1=new LinkedList<>();  
   Deque<Integer> stack2=new LinkedList<>();  
   public void push(int x) {  
     stack1.push(x);  
     if (stack2.isEmpty() || x<=stack2.peek()) stack2.push(x);  
     else stack2.push(stack2.peek());  
   }  
   public void pop() {  
     stack2.pop();  
     stack1.pop();  
   }  
   public int top() {  
     return stack1.peek();  
   }  
   public int getMin() {  
     return stack2.peek();  
   }  
 }