包含min函数的栈

题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
牛客网上的题目，直接po代码，自定义了栈结构

import javax.management.RuntimeErrorException;
public class Solution {
    int val;
    Solution next;
    Solution head;
    public void push(int node) {
        Solution newhead = new Solution();
        newhead.next = head;
        newhead.val = node;
        head = newhead;
    }
    public void pop() {
        if(head == null) 
          throw new RuntimeException("栈为空");
        Solution tmp = head.next;
    //    System.out.println(head.val);
        head = tmp;
    }
    public int top() {
        return head.val;        
    }
    public int min() {
            int min = Integer.MAX_VALUE;
            Solution orihead = head;
        while(head!= null) {
                 min = Math.min(min, head.val);
                 head = head.next;
        }
        head = orihead;
        return min;
    }
}

本以为这只是一道考察自己实现栈的题目，但是打开《剑指 offer》以后打开了一扇新世界的大门，《剑指 offer》上的题目要求略有不同：
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O（1）。

去掉了top函数，但是要求时间复杂度均为O（1），上面程序min的时间复杂度为O（n），很明显不符合要求。

很自然地联想到，为什么不添加一个 int min，当每次push的时候与min进行比较并更新min呢。这种方法在只有push的时候是可行的，但是如果执行了pop语句，将最小值pop出之后，我们怎样将min进行更新呢？很明显这时候需要再次扫描全栈，因为我们没有保存次小元素，时间复杂度必定不满足。

由此我们可以得到该问题的解决方案，保存次小、次次小……元素。

import java.util.Stack;
public class Solution {
    Stack<Integer> data = new Stack<Integer>();
    Stack<Integer> min = new Stack<Integer>();
    public void push(int node) {
           data.push(node);
           if(min.size() == 0)
               min.push(node);
           else if(node < min.peek())
               min.push(node);
           else 
               min.push(min.peek());
    }
    public void pop() {
            if(data.size() > 0) {
               data.pop();
               min.pop();
            }
    }
    public int top() {
            if(data.size() > 0)
                return data.peek();
            return 0;
    }
    public int min() {
            if(min.size() > 0)
                  return min.peek();
            return 0;       
    }
}

经过查看源码发现peek()函数不是通过遍历来寻找栈顶，时间复杂度为O（1），所以上述程序符合要求。