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

모든 코드 는 G + 컴 파일 러 테스트 를 통 해 연습 기록 에 불과 합 니 다.
/ / 면접 문제 21: min 함 수 를 포함 하 는 스 택
/ / 제목: 스 택 의 데이터 구 조 를 정의 합 니 다. 이 유형 에서 스 택 의 최소 요 소 를 얻 을 수 있 는 min 함 수 를 실현 하 십시오.
//     이 스 택 에서 min / push / pop 을 호출 하 는 시간 복잡 도 는 모두 O (1) 입 니 다.

//   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());
}

ZhaiPillary
2016-12-25