微软面试100题（2）：包含Min功能的栈

设计包含min 函数的栈。
定义栈的数据结构，要求添加一个min 函数，能够得到栈的最小元素。
要求函数min、push 以及pop 的时间复杂度都是O(1)。

 

使用一个栈处理push,pop,额外使用一个栈，用来记录最小值。

a.当向原栈中push数据后,与最小值栈中的栈顶元素比较,如果新值小于等于最小值栈顶,则在最小值栈中push新值;否则不动

b.pop的时候,考虑pop出的值是否等于最小值栈顶元素，如果等于最小栈也pop,否则不动

c.min函数返回最小值栈的栈顶元素

 

C#实现如下

public class myStack{
    private Stack<int> stackMin;
    private Stack<int> stack;
    public myStack(){
        stackMin = new Stack<int>();
        stack = new Stack<int>();
    }
    public void Push(int tar){
        stack.Push(tar);
        if(stackMin.Count == 0){
            stackMin.Push(tar);
        }
        else{
            int cur = stackMin.Peak();
            if(tar<=cur)
                stackMin.Push(tar);
        }
    }
    public int Pop(){
        if(stack.Count == 0)
            throw new Exception("the stack is empty!");
        int cur = stack.Pop();
        if(cur==stack.Peak()){
            stackMin.Pop();
        }
        return cur;
    }
    public int Min(){
        if(stackMin.Count == 0)
            throw new Exception("the stack is empty!");
        return stackMin.Peak();
    }
}