CC_3_2

MinStack.java

// Cracking the Coding Interview
// 3.2 How would you design a stack which, in addition to push and pop, 
// also has a function min which returns the minimum element? 
// Push, pop and min should all operate in O(1) time.
import java.util.Stack;

class MinStack {
	private Stack<Integer> s;
	private Stack<Integer> minValues;

	public MinStack() {
		s = new Stack<Integer>();
		minValues = new Stack<Integer>();
	}

	public void push(Integer element) {
		s.push(element);
		if (minValues.empty() || element <= minValues.peek()) {
			minValues.push(element);
			
		} 
		s.push(element);
	}

	public Integer pop() {
		if (minValues.peek() < s.peek()) {
			return s.pop();
		} else {
			minValues.pop();
			return s.pop();
		}
	} 
	public Integer min() {
		return minValues.peek();
	}

}