【C/C++练习题】栈中添加min方法

《剑指Offer》面试题30：包含min函数的栈

1 题目

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)。

2 问题分析

构造一个辅助栈，保证辅助栈空间的栈顶元素始终是数据栈中的最小元素。那么当程序对栈进行压栈or弹栈操作时，对应的辅助栈也要进行操作。

3 代码

      #include <stack>
      #include <assert.h>
      #include <iostream>
      //问题.实现一个包含min函数的栈
      using namespace std;
      template <typename T>
      class StackWithMin
      {
      public:
         StackWithMin() {}
         virtual ~StackWithMin() {}
         // T& top();
         // const T& top() const;
         void push(const T& value);
         void pop();
         const T& min() const;
         // bool empty() const;
         // size_t size() const;
      private:
          std::stack<T>   m_data;     // 数据栈，存放栈的所有元素
          std::stack<T>   m_min;      // 辅助栈，存放栈的最小元素
      };
      template <typename T>
      void StackWithMin<T>::push(const T& value)      //实现push方法
      {
         //1.value压入数据栈
          m_data.push(value);
         //2.将当前最小数值压入辅助栈(第一个数值，直接压入辅助栈中)
         if(m_min.size() == 0 || value < m_min.top())
              m_min.push(value);
         else
              m_min.push(m_min.top());
      }
      template <typename T>
      void StackWithMin<T>::pop()                 //实现pop方法
      {
         //1.检查栈是否为空
         assert(m_data.size() > 0 && m_min.size() > 0);
         //2.将数值弹出
          m_data.pop();
          m_min.pop();
      }
      template <typename T>
      const T& StackWithMin<T>::min() const           //实现min方法
      {
         //检查栈是否为空
         assert(m_data.size() > 0 && m_min.size() > 0);
         //返回最小数值
         return m_min.top();
      }
      int main(int argc, char* argv[])
      {
          StackWithMin<int> stack;
          stack.push(3);
          stack.push(4);
          stack.push(2);
          stack.push(3);
          cout << stack.min() << endl;
          stack.pop();
          stack.pop();
          cout << stack.min() << endl;
         return 0;
      }
  
 

4 运行

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/99294385