2. Min Stack
Implement a stack with following functions:
-
push(val)push val into the stack -
pop()pop the top element and return it -
min()return the smallest number in the stack
All above should be in O(1) cost.
Example
Example 1:
Input:
push(1)
pop()
push(2)
push(3)
min()
push(1)
min()
Output:
1
2
1
Notice
min() will never be called when there is no number in the stack.
思路：
因为O（1），所以用两个栈操作，stack 和 minStack。
push（int num）: stack push; 如果minStack为空，minStack直接push，或者 num<=minStack的栈顶元素，minStack也push
pop(): stack pop; 如果minStack的栈顶值和stack栈顶值相等（Integer类判断两个值相等要用equals.()），minStack也pop.
min(): 返回minStack 栈顶值。
注意：
（1）push的时候，num == minStack.peek() 时，也要minStack.peek()。[line 12]
否则，有可能出现EmptyStackException：第一次pop()后，minStack为空了，再min()就会有异常。
push(1)
push(1)
push(1)
min()
pop()
min()
pop()
（2）equals 和 ==
==是一个关系运算符，如果比较的两端都为基本类型，则判断两者的值是否相等,（判断过程中还有不同基本类型的转化，这里不做讨论）。如果比较的两端都为引用类型的话，则比较两者所指向对象的地址是否相同
对于equals方法，首先，能调用这个方法肯定是一个对象，然后，如果这个对象所在的类重写了equals方法，则按照重写的方法进行比较，如果没有，则比较两者所指向对象的地址是否相同。
Integer类重写了equals方法，所以equals方法才是比较两个值是否相等，而不能用==（== 用来比较两个引用变量存储的地址是否相同，也就是是否指向同一个地址）
代码：
public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public void push(int number) {
stack.push(number);
if (minStack.empty() || minStack.peek() >= number) { //相等时，minStack也要push
minStack.push(number);
}
}
public int pop() {
if (stack.peek().equals(minStack.peek())) //比较栈顶值，只能用equals()
minStack.pop();
return stack.pop();
}
public int min() {
return minStack.peek();
}
}