题目描述：

  定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

  解题思路：

  解法一：使用两个stack，一个为数据栈，另一个为辅助栈。数据栈用于存储所有数据，每次压栈的最小元素（之前的最小元素和新压入栈中的元素，二者的较小值）保存起来放入辅助栈。

  解法二：最小元素每一次都进栈，会有重复，也可以只有当进栈元素小于或等于之前的最小元素时，最小元素才进栈，而当弹出元素等于最小元素时，最小元素才出栈，从而节省一部分空间。

  解法三：定义一个组合变量，比如Node，包括数据和最小元素两个成员变量，从而节省一个栈，但是本质仍然没有变。

  举例：

  编程实现（Java）：

//解法一：

public class Solution {

    /*

    思路:需要一个辅助栈空间，对应保存当前数据栈的最小值

    */

    Stack<Integer> stack=new Stack<>();

    Stack<Integer> minStack = new Stack<>(); //辅助栈

    public void push(int node) {

        stack.push(node);

        if(minStack.empty())  //将当前最小值存入辅助栈

            minStack.push(node);

        else

            minStack.push(node > minStack.peek() ? minStack.peek(): node);

    }

    public void pop() { //两个都出栈

        if(!stack.empty()){

            stack.pop();

            minStack.pop();

        }

    }

    public int top() {

        return stack.peek();

    }

    public int min() {

        return minStack.peek();

    }

}

//解法二：

class MinStack {

    private Stack<Integer> dataStack;  //数据栈

    private Stack<Integer> minStack; //存放最小元素的栈

    /** initialize your data structure here. */

    public MinStack() {

        dataStack=new Stack<>();

        minStack=new Stack<>();

    }

    public void push(int x) {

        if(minStack.isEmpty() || x<=minStack.peek())

            minStack.push(x);

        dataStack.push(x);

    }

    public void pop() {

        if(!dataStack.isEmpty()){

            int x=dataStack.pop();

            if(x==minStack.peek())

                minStack.pop();

        }

    }

    public int top() {

        return dataStack.peek();

    }

    public int getMin() {

        return minStack.peek();

    }

}