面试题21：包含min函数的栈

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O（1）。

public class MinStack
{
    Stack<int> mainStack;
    //辅助栈
    Stack<int> subStack;
    /** initialize your data structure here. */
    public MinStack()
    {
        mainStack = new Stack<int>();
        subStack = new Stack<int>();
    }
    /// <summary>
    /// 栈压入元素
    /// </summary>
    /// <param name="x"></param>
    public void Push(int x)
    {
        mainStack.Push(x);
        if(subStack.Count<=0)
            subStack.Push(x);
        else
        {
            var min = subStack.Peek();
            if(x<=min)
                subStack.Push(x);
            else
            {
                subStack.Push(min);
            }
        }
    }
    /// <summary>
    /// 栈弹出元素
    /// </summary>
    public void Pop()
    {
        if (mainStack.Count > 0)
            mainStack.Pop();
        if (subStack.Count > 0)
            subStack.Pop();
    }
    /// <summary>
    /// 获取栈顶元素
    /// </summary>
    /// <returns></returns>
    public int Top()
    {
        if (mainStack.Count > 0)
            return mainStack.Peek();
        return 0;
    }
    /// <summary>
    /// 获取最小数据
    /// </summary>
    /// <returns></returns>
    public int Min()
    {
        if (subStack.Count > 0)
            return subStack.Peek();
        else
            return 0;
    }
}

思路：添加辅助栈，辅助栈中的元素与原来栈数据一一对应，但是辅助栈中保存的是对应原始栈相应的最小值。当新压入数据时，如果数据大于当前最小值（辅助栈栈顶数据），则辅助栈压入当前最小数据；否则，辅助栈压入新添加的数据。