一个具有getMin()功能的栈

  实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

【要求】
  1.pop、push、getMin操作的时间复杂度都是O（1）。
  2.设计的栈类型可以使用现成的栈结构。

  代码如下：

#include <stack>
using namespace std;
template<class T>
class MyStack {
       stack<T> m_minStack;
       stack<T> m_normalStack;
public:
       T getMin() {
              if (m_minStack.empty() == true)
                     return T();
              return m_minStack.top();
       }
       void push(const T val) {
              if (m_normalStack.empty()) {
                     m_minStack.push(val);
              }
              else {
                     if (m_minStack.top() >= val) {
                           m_minStack.push(val);
                     }
              }
              m_normalStack.push(val);
       }
       T pop() {
              if (this->empty())
                     return T();
              if (m_normalStack.top() <= m_minStack.top())
                     m_minStack.pop();
              T ret = m_normalStack.top();
              m_normalStack.pop();
              return ret;
       }
       bool empty() {
              return m_normalStack.empty();
       }
};

  注意：这里之所以要用到2个栈，而不能只额外用一个 min临时变量的原因是因为要考虑pop操作。