首页 > 代码库 > 微软100题系列之-----设计包含min函数的栈

微软100题系列之-----设计包含min函数的栈

题意:

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


思路:定义两个栈,一个用来记录数据的插入和删除,一个用来存储最小值的变化


代码如下:

template <class T>
class Stack
{
public:
    Stack(int len=100);

    T Min();
    T Pop();
    void Push(T val);
private:
    T top1,top2;
    T *stack1,*stack2; //stack2用来存储最小值的栈
};


template <class T>
Stack<T>::Stack(int len)
{
    top1 = top2 = -1;
    stack1 = new T[len] ;
    stack2 = new T[len] ;
}

template <class T>
T Stack<T>::Min()
{
    return stack2[top2];
}

template <class T>
T Stack<T>::Pop()
{
    T temp = stack1[top1--] ;
    if(stack2[top2] == temp)
        top2--;
    return temp;
}

template <class T>
void Stack<T>::Push(T val)
{
    stack1[++top1] = val ;
    if(top2 == -1)
        stack2[++top2] = val;
    else if(val <= stack2[top2])
        stack2[++top2] = val ;
}