C++算法题：递归和栈的算法

//相当于从下往上跳，最后剩一个（仅一种跳法）或两个（有两种跳法）+++
//函数功能 ： 跳台阶问题  
//函数参数 ： n为台阶个数  
//返回值 ：   总的跳法  
unsigned JumpSteps_Solution1(unsigned n)  
{  
    if(n <= 2)  
        return n;  
    else   
        return JumpSteps_Solution1(n - 1) + JumpSteps_Solution1(n - 2);  
} 

树的深度 = 1 + max{ 根节点左子树深度，根结点右子树深度}

struct SBinaryTreeNode // a node of the binary tree
{
      int               m_nValue; // value of node
      SBinaryTreeNode  *m_pLeft;  // left child of node
      SBinaryTreeNode  *m_pRight; // right child of node
};


//函数功能 ： 二元树的深度  
//函数参数 ： pNode指向树的结点  
//返回值 ：   深度  
int BinaryTreeDepth(BinaryTreeNode *pNode)  
{  
    if(pNode == NULL)  
        return 0;  
    else  
    {  
        int leftDepth = BinaryTreeDepth(pNode->m_pLeft);  
        int rightDepth = BinaryTreeDepth(pNode->m_pRight);  
        return (leftDepth > rightDepth) ? leftDepth+1 : rightDepth+1;  
    }  
}

思路：利用双栈来做。一个栈用于正常的入栈退栈，称为Stack1，另外一个用于保存栈的最小元素，称为Stack2。Stack2入栈时，将入栈元素与Stack2的栈顶元素比较，如果小于栈顶元素，则两个栈同时执行入栈操作。Stack1退栈时，如果退栈元素与Stack2的栈顶元素相等，则两个栈同时执行出栈操作。

template  
class MinStack  
{  
public:  
    MinStack();  
    ~MinStack();  
    bool Empty() const; //判断栈是否为空  
    void Push(T value); //压栈  
    void Pop();         //退栈  
    T& Top();  
    const T& Top() const;  
    const T& Min() const;  
private:  
    stack m_comStack; //正常栈  
    stack m_minStack; //最小栈  
};  
template  
MinStack::MinStack()  
{  
}  
template  
MinStack::~MinStack()  
{  
}  
template  
bool MinStack::Empty() const  
{  
    return m_comStack.empty();  
}  
template  
void MinStack::Push(T value)  
{  
    if(m_minStack.empty() || value <= m_minStack.top())  
        m_minStack.push(value);  
    m_comStack.push(value);  
}  
template  
void MinStack::Pop()  
{  
    if(m_minStack.top() == m_comStack.top())  
        m_minStack.pop();  
    m_comStack.pop();  
}  
template  
const T& MinStack::Min() const  
{  
    return m_minStack.top();  
}  
template  
T& MinStack::Top()  
{  
    m_comStack.top();  
}  
template  
const T& MinStack::Top() const  
{  
    m_comStack.top();  
}