[Google Interview] No. 02 - Stack with Function min()

Problem: Define a stack, in which we can get its minimum number with a function min. In this stack, the time complexity of min(), push() and pop() are all O(1).



My Code:
template.h

#include <stack>

template <class T>

class StackWithMin

{

public:

    StackWithMin(){};

    ~StackWithMin(){};

    void push(T value);

    void pop();

    T min() const;

    T top(){return fdata.top();};

private:

    std::stack<T> fdata;

    std::stack<T> fmin;

};

template <class T>

void StackWithMin<T>::push(T value)

{

    fdata.push(value);

    if (fmin.size() <= 0)

    {

        fmin.push(value);

        return;

    }

    if (value < fmin.top())

    {

        fmin.push(value);

    }

    else

    {

        fmin.push(fmin.top());

    }

}

template <class T>

void StackWithMin<T>::pop()

{

    fmin.pop();

    fdata.pop();

}

template <class T>

T StackWithMin<T>::min() const

{

    return fmin.top();

}

stack.cpp

#include "template.h"

void print (StackWithMin<char> *data)

{

    printf("%d::%d\n", data->top(), data->min());

}

int main(int argc, char **argv)

{

    StackWithMin<char> testData;

    testData.push(3);

    print (&testData);

    testData.push(4);

    print (&testData);

    testData.push(2);

    print (&testData);

    testData.push(1);

    print (&testData);

    testData.pop();

    print (&testData);

    testData.pop();

    print (&testData);

    testData.push(0);

    print (&testData);

    return 0;

}

Result:

3::3

4::3

2::2

1::1

2::2

4::3

0::0

ref: http://codercareer.blogspot.tw/2011/09/no-02-stack-with-function-min.html