包含min函数的栈

来源：牛客网、《剑指offer》

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。要求push pop min 操作的复杂度为O(1)。

考虑使用两个栈，一个数据栈，等同于普通的栈，实现push pop peek 等操作；另一个辅助栈实现min函数。

这题关键在于用辅助栈储存什么值。要保证辅助栈的top是最小值，pop之后的顶部仍然是最小值。也就是说辅助栈从上到下存储的应该是最小值->次小值->次次小值……

这里容易进入一个误区就是：难道辅助栈就是对数据栈的排序？如果真是这样，push的时候因为要排序不能满足O(1)；数据栈pop的时候，辅助栈要先查找数据栈pop出去的值然后再pop，也不满足O(1)。

当两个栈为空时，push进去的第一个值即为最小值；

push第二个元素时，若push的值<辅助栈顶元素（此处即第一个值），则将此值压进辅助栈；若push的值大于等于辅助栈顶元素，则将辅助栈顶元素再次push进去。

pop的时候，数据栈辅助栈均弹出顶元素。

java code:

 1 import java.util.Stack;
 2 
 3 public class TT {
 4     Stack<Integer> stack1 = new Stack<Integer>(); // 数据栈
 5     Stack<Integer> stack2 = new Stack<Integer>(); // 辅助栈 用于返回min值
 6 
 7 
 8     public void push(int node) {
 9         stack1.push(node);
10         if (stack2.empty()) {
11             stack2.push(node);
12         } else {
13             if (node < stack2.peek().intValue())
14                 stack2.push(node);
15             else stack2.push(stack2.peek());
16         }
17 
18     }
19 
20     public void pop() {
21         if (!stack1.empty())
22             stack1.pop();
23         if (!stack2.empty())
24             stack2.pop();
25     }
26 
27     public int top() {
28         if (!stack1.empty())
29             return stack1.peek().intValue();
30         else return 0;
31     }
32 
33     public int min() {
34         if (!stack2.empty())
35             return stack2.peek().intValue();
36         else return 0;
37     }
38 }

参考资料：《剑指offer》