검 지 Offer 의 면접 문제 21: min 함 수 를 포함 하 는 스 택

//   21:  min    
//  ：        ，                     min  。
//         ，  min/push/pop        O(1)。

template
class CStackMin
{
public:
    CStackMin(){}
    ~CStackMin()
    {
        Clear();
    }
    
public:
    void Push(const T& item)
    {
        m_stackValue.push(item);
        if (m_stackMin.empty())
        {
            m_stackMin.push(item);
        }
        else
        {
            if(item <= m_stackMin.top())
            {
                m_stackMin.push(item);
            }
        }
    }
    
    void Pop()
    {
        if(m_stackMin.empty())
        {
            return;
        }
        
        if(m_stackValue.top() == m_stackMin.top())
        {
            m_stackMin.pop();
        }
        
        m_stackValue.pop();
    }
    
    T Min() const
    {
        if(m_stackMin.empty())
        {
            return T();
        }
        
        return m_stackMin.top();
    }
    
private:
    void Clear()
    {
        while (!m_stackValue.empty())
        {
            m_stackValue.pop();
        }
        
        while (!m_stackMin.empty())
        {
            m_stackMin.pop();
        }
    }
    
private:
    stack m_stackValue;
    stack m_stackMin;
};

void TestStackMin()
{
    CStackMin stack;
    stack.Push(3);
    LogInfo("Min:%d",stack.Min());
    stack.Push(7);
    LogInfo("Min:%d",stack.Min());
    stack.Push(2);
    LogInfo("Min:%d",stack.Min());
    stack.Push(4);
    LogInfo("Min:%d",stack.Min());
    stack.Push(9);
    LogInfo("Min:%d",stack.Min());
    stack.Push(1);
    LogInfo("Min:%d",stack.Min());
    stack.Push(4);
    LogInfo("Min:%d",stack.Min());
    
    stack.Pop();
    LogInfo("Min:%d",stack.Min());
    stack.Pop();
    LogInfo("Min:%d",stack.Min());
    stack.Pop();
    LogInfo("Min:%d",stack.Min());
    stack.Pop();
    LogInfo("Min:%d",stack.Min());
    stack.Pop();
    LogInfo("Min:%d",stack.Min());
    stack.Pop();
    LogInfo("Min:%d",stack.Min());
    stack.Pop();
    LogInfo("Min:%d",stack.Min());
    stack.Pop();
    LogInfo("Min:%d",stack.Min());
}